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.)

„Ś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.

^{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ć:

• Czy nie jest wystarczające łączenie ciągów pojedynczo?

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ą.

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.

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