Dlaczego ciągi są tak wolne?

23

Od czasu mojej pierwszej klasy programowania w liceum słyszałem, że operacje na sznurkach są wolniejsze - tj. Droższe - niż mityczna „średnia operacja”. Dlaczego sprawia, że ​​są tak wolne? (To pytanie pozostawiono celowo szerokie.)

Wyskakuje
źródło
11
Jeśli wiesz, że te „przeciętne operacje” są mityczne, czy możesz przynajmniej powiedzieć nam, jakie są niektóre z nich? Biorąc pod uwagę, że zadajesz tak niejasne pytanie, trudno zaufać swojemu twierdzeniu, że te nieokreślone operacje są naprawdę mityczne.
seh
1
@seh, niestety nie mogę na to odpowiedzieć. Kilka razy pytałem ludzi, które struny są wolniejsze, po prostu wzruszają ramionami i mówią „są po prostu wolne”. Poza tym, gdybym miał bardziej szczegółowe informacje, byłoby to pytanie dla SO, a nie dla programistów; to już trochę granica.
Wyskakuje
O co chodzi ? Jeśli powiedziane ciągi są rzeczywiście wolne, czy przestaniesz ich używać?
Tulains Córdova
Zapomnij o tym. Jeśli ktoś powie ci takie bzdury, pytaniem jest: „Naprawdę? Czy to prawda? Czy powinniśmy wtedy użyć int-array?”
Ingo

Odpowiedzi:

47

„Średnia operacja” ma miejsce na prymitywach. Ale nawet w językach, w których łańcuchy są traktowane jak prymityw, nadal są tablicami pod maską, a wykonywanie czegokolwiek z udziałem całego łańcucha zajmuje czas O (N), gdzie N jest długością łańcucha.

Na przykład dodanie dwóch liczb zwykle wymaga 2-4 instrukcji ASM. Łączenie („dodawanie”) dwóch ciągów wymaga nowego przydziału pamięci i jednej lub dwóch kopii ciągu obejmujących cały ciąg.

Niektóre czynniki językowe mogą go pogorszyć. Na przykład w C ciąg znaków jest po prostu wskaźnikiem do tablicy znaków zakończonej znakiem null. Oznacza to, że nie wiesz, ile to trwa, więc nie ma sposobu na optymalizację pętli kopiowania ciągów za pomocą operacji szybkiego przenoszenia; musisz skopiować jeden znak na raz, aby można było przetestować każdy bajt dla terminatora zerowego.

Mason Wheeler
źródło
4
A niektóre języki sprawiają, że jest znacznie lepiej: kodowanie Delphi długości łańcucha na początku tablicy sprawia, że ​​konkatenacja łańcucha jest bardzo szybka.
Frank Shearar,
4
@gablin: Pomaga to również w szybszym kopiowaniu łańcucha. Kiedy znasz rozmiar z przodu, nie musisz kopiować jednego bajta na raz i sprawdzać każdy bajt pod kątem pustego terminatora, dzięki czemu możesz używać pełnego rozmiaru dowolnego rejestru, w tym SIMD, do przenoszenia danych, dzięki czemu do 16 razy szybciej.
Mason Wheeler,
4
@mathepic: Tak, i to jest w porządku, o ile cię to zajmie, ale kiedy zaczniesz wchodzić w interakcje z libc lub innym zewnętrznym kodem, oczekuje on char*, a nie strbuf, i wracasz do kwadratu 1. Jest tylko tyle można to zrobić, gdy w języku pojawia się zły projekt.
Mason Wheeler,
6
@mathepic: Oczywiście bufwskaźnik tam jest. Nigdy nie chciałem sugerować, że nie jest dostępny; raczej, że jest to konieczne. Każdy kod, który nie wie o twoim zoptymalizowanym, ale niestandardowym typie łańcucha, w tym rzeczy tak fundamentalne jak standardowa biblioteka , wciąż musi polegać na powolnym, niebezpiecznym char*. Możesz nazwać ten FUD, jeśli chcesz, ale to nie oznacza, że ​​to nieprawda.
Mason Wheeler,
7
Ludzie, jest kolumna Joela Spolsky'ego na temat Franka Shearera: Back to Basics
user16764
14

To jest stary wątek i myślę, że inne odpowiedzi są świetne, ale coś przeoczają, więc oto moje (późne) 2 centy.

Syntaktyczna powłoka cukrowa kryje złożoność

Problem z łańcuchami polega na tym, że są obywatelami drugiej kategorii w większości języków i w rzeczywistości przez większość czasu tak naprawdę nie są częścią samej specyfikacji językowej: są to konstrukcje implementowane przez bibliotekę z okazjonalnym składniowym powlekaniem cukrem na górze aby uczynić je mniej uciążliwym w użyciu.

Bezpośrednią konsekwencją tego jest to, że język ukrywa bardzo dużą część swojej złożoności z dala od twojego wzroku, a ty płacisz za podstępne skutki uboczne, ponieważ masz w zwyczaju uważać je za atomową istotę niskiego poziomu, tak jak inne pierwotne typy (jak wyjaśniono w najczęściej głosowanej odpowiedzi i inne).

Szczegóły dotyczące wdrożenia

Dobra tablica Ol '

Jednym z elementów tej leżącej u podstaw „złożoności” jest to, że większość implementacji łańcuchów uciekłaby się do użycia prostej struktury danych z pewną ciągłą przestrzenią pamięci do reprezentowania łańcucha: dobra tablica ol.

Ma to sens, ponieważ chcesz, aby dostęp do łańcucha jako całości był szybki. Ale to oznacza potencjalnie straszne koszty, gdy chcesz manipulować tym ciągiem. Dostęp do elementu pośrodku może być szybki, jeśli wiesz, jakiego indeksu szukasz, ale szukanie elementu na podstawie warunku nie jest.

Nawet zwrócenie rozmiaru łańcucha może być kosztowne, jeśli Twój język nie buforuje długości łańcucha i musi go przejrzeć, aby policzyć znaki.

Z podobnych powodów dodawanie elementów do łańcucha będzie kosztowne, ponieważ najprawdopodobniej będziesz musiał ponownie przydzielić trochę pamięci na tę operację.

Różne języki mają różne podejście do tych problemów. Na przykład Java zezwoliła na uczynienie swoich ciągów niezmiennymi z kilku ważnych powodów (długość buforowania, bezpieczeństwo wątków), a ze względu na swoje zmienne odpowiedniki (StringBuffer i StringBuilder) zdecyduje się przydzielić rozmiar za pomocą większych fragmentów, aby nie musieć przydzielać za każdym razem, ale raczej nadzieję na najlepsze scenariusze. Ogólnie działa dobrze, ale wadą jest czasami płacenie za wpływ pamięci.

Obsługa Unicode

Ponadto, i znowu wynika to z faktu, że syntaktyczna powłoka cukrowa twojego języka ukrywa to przed tobą, aby grać ładnie, często nie sądzisz, że chodzi o obsługę Unicode (szczególnie, dopóki tak naprawdę nie jest to potrzebne i uderzył w tę ścianę). Niektóre języki, z myślą o przyszłości, nie implementują ciągów znaków z podstawowymi tablicami prostych 8-bitowych prymitywów znaków. Wypiekali w UTF-8 lub UTF-16 lub w obsłudze, jaką masz dla Ciebie, a konsekwencją jest znacznie większe zużycie pamięci, które często nie jest potrzebne, i dłuższy czas przetwarzania na przydzielenie pamięci, przetwarzanie ciągów, i zaimplementuj całą logikę, która idzie w parze z manipulowaniem punktami kodu.


Rezultatem tego wszystkiego jest to, że kiedy robisz coś równoważnego w pseudokodzie, aby:

hello = "hello,"
world = " world!"
str = hello + world

Może nie być - pomimo wszelkich starań, które twórcy języków włożyli, aby zachowali się tak, jak Ty - z wyjątkiem:

a = 1;
b = 2;
shouldBeThree = a + b

Jako kontynuację możesz przeczytać:

Haylem
źródło
Dobry dodatek do bieżącej dyskusji.
Abel,
Właśnie zdałem sobie sprawę, że jest to najlepsza odpowiedź, ponieważ mityczne oświadczenie można zastosować do wszystkiego takiego, jak szyfrowanie RSA jest powolne. Jedynym powodem umieszczenia łańcucha w tym zawstydzającym miejscu jest to, że operator plus podał łańcuchy w większości języków, co sprawia, że ​​początkujący nie są świadomi kosztów związanych z operacją.
Codism
@Abel: dzięki, wydawało mi się, że jest miejsce na bardziej ogólne szczegóły.
haylem
@Codism: dzięki, cieszę się, że ci się podobało. Naprawdę uważam, że można to zastosować w wielu przypadkach, w których ukrywanie jest tylko kwestią złożoności (i tego, że nie zwracamy już tak dużej uwagi na szczegóły niższego poziomu, aż w końcu będziemy musieli, ponieważ natrafimy na jakieś wąskie gardło lub mur z cegły ).
haylem,
1

Wyrażenie „średnia operacja” jest prawdopodobnie skrótem dla pojedynczej operacji teoretycznej maszyny z przechowywanym programem o losowym dostępie . Jest to teoretyczna maszyna, której zwykle używa się do analizy czasu działania różnych algorytmów.

Zwykle przyjmuje się, że operacje ogólne to ładowanie, dodawanie, odejmowanie, przechowywanie, rozgałęzianie. Może też przeczytaj, wydrukuj i zatrzymaj.

Ale większość operacji na łańcuchach wymaga kilku z tych podstawowych operacji. Na przykład powielenie łańcucha zwykle wymaga operacji kopiowania, a zatem szeregu operacji, które są proporcjonalne do długości łańcucha (to znaczy, że jest „liniowy”). Znalezienie podłańcucha w innym ciągu ma również złożoność liniową.

James Youngman
źródło
1

Zależy to całkowicie od operacji, sposobu reprezentowania ciągów i istniejących optymalizacji. Jeśli łańcuchy mają długość 4 lub 8 bajtów (i są wyrównane), niekoniecznie byłyby wolniejsze - wiele operacji byłoby tak samo szybkich jak operacje podstawowe. Lub, jeśli wszystkie ciągi mają 32-bitowy lub 64-bitowy skrót, wiele operacji będzie również tak samo szybkich (chociaż koszty haszowania płacisz z góry).

Zależy to również od tego, co rozumiesz przez „powolny”. Większość programów przetwarza łańcuchy dość szybko na to, co jest potrzebne. Porównywanie ciągów może nie być tak szybkie, jak porównywanie dwóch liczb całkowitych, ale tylko profilowanie ujawni, co oznacza „wolne” dla twojego programu.

Kevin Hsu
źródło
0

Pozwól, że odpowiem na twoje pytanie. Dlaczego wypowiedzenie ciągu słów zajmuje więcej czasu niż wypowiedzenie pojedynczego słowa?

ChaosPandion
źródło
2
Niekoniecznie.
user16764
3
Supercalifragilisticexpialidocious
Spoike
s / word / sylable / g
Caleb
Pozwól, że odpowiem na twoje pytanie-odpowiedź pytaniem: dlaczego nie powiesz, co znaczy twoja odpowiedź? W końcu nie jest jasne, jak można to interpretować jako odnoszące się do jakiegoś systemu wykonawczego.
PJTraill,