Jeśli ciągi są niezmienne w .NET, to dlaczego Substring zajmuje O (n) czas?


451

Biorąc pod uwagę, że ciągi są niezmienne w .NET, zastanawiam się, dlaczego zostały zaprojektowane tak, że string.Substring()zajmuje O ( substring.Length) zamiast O(1)?

tj. jakie były kompromisy, jeśli w ogóle?


3
@Mehrdad: Podoba mi się to pytanie. Czy możesz mi powiedzieć, jak możemy ustalić O () danej funkcji w .Net? Czy to jasne, czy powinniśmy to obliczyć? Dziękuję
odiseh,

1
@odiseh: Czasami (jak w tym przypadku) jasne jest, że ciąg jest kopiowany. Jeśli tak nie jest, możesz albo przejrzeć dokumentację, przeprowadzić testy porównawcze, albo spróbować zajrzeć do kodu źródłowego .NET Framework, aby dowiedzieć się, co to jest.
user541686,

Odpowiedzi:


423

AKTUALIZACJA: Bardzo podobało mi się to pytanie, właśnie je blogowałem. Zobacz struny, niezmienność i trwałość


Krótka odpowiedź brzmi: O (n) to O (1), jeśli n nie rośnie. Większość ludzi wyodrębnia małe podciągi z małych strun, więc to, jak złożoność rośnie asymptotycznie, jest całkowicie nieistotne .

Długa odpowiedź brzmi:

Niezmienna struktura danych zbudowana w taki sposób, że operacje na instancji pozwalają na ponowne użycie pamięci oryginału z niewielką ilością (zwykle O (1) lub O (lg n)) kopiowania lub nowego przydziału nazywane jest „trwałym” niezmienna struktura danych. Ciągi w .NET są niezmienne; twoje pytanie brzmi „dlaczego nie są uparte”?

Ponieważ, gdy spojrzysz na operacje, które są zwykle wykonywane na łańcuchach w programach .NET, po prostu utworzenie zupełnie nowego łańcucha jest pod każdym istotnym względem wcale nie gorsze . Koszt i trudność zbudowania złożonej trwałej struktury danych nie zwraca się.

Ludzie zwykle używają „podciągów” do wydobywania krótkiego ciągu - powiedzmy, dziesięciu lub dwudziestu znaków - z nieco dłuższego ciągu - może kilkuset znaków. Masz wiersz tekstu w pliku oddzielanym przecinkami i chcesz wyodrębnić trzecie pole, które jest nazwiskiem. Linia będzie miała może kilkaset znaków, nazwa będzie miała kilkadziesiąt. Przydział ciągów i kopiowanie pamięci z pięćdziesięciu bajtów jest zadziwiająco szybkie na współczesnym sprzęcie. To, że tworzenie nowej struktury danych, która składa się ze wskaźnika do środka istniejącego łańcucha i długości jest również zadziwiająco szybkie, nie ma znaczenia; „wystarczająco szybki” jest z definicji wystarczająco szybki.

Wyekstrahowane substraty są zazwyczaj małe i mają krótki okres użytkowania; śmieciarz wkrótce je odzyska, a przede wszystkim nie zajmowali dużo miejsca na hałdzie. Zatem stosowanie trwałej strategii zachęcającej do ponownego użycia większości pamięci również nie jest wygrane; wszystko, co zrobiłeś, sprawiło, że twój śmieciarz stał się wolniejszy, ponieważ teraz musi martwić się obsługą wskaźników wewnętrznych.

Gdyby operacje podciągania, które ludzie zwykle wykonywali na łańcuchach, były zupełnie inne, wówczas sensowne byłoby podejście trwałe. Gdyby ludzie zazwyczaj mieli łańcuchy o milionach znaków i wydobywali tysiące nakładających się podciągów o rozmiarach w zakresie stu tysięcy znaków, a te podłańcuchy żyły długo na stosie, to byłoby sensowne, aby stosować trwałe podciągi podejście; byłoby marnotrawstwem i głupotą tego nie robić. Ale większość programistów zajmujących się biznesem nie robi nic, nawet niejasno, jak tego rodzaju rzeczy. .NET nie jest platformą dostosowaną do potrzeb projektu Human Genome; Programiści zajmujący się analizą DNA muszą codziennie rozwiązywać problemy z tymi charakterystykami wykorzystania łańcucha; szanse są dobre, że nie. Nieliczni, którzy tworzą własne trwałe struktury danych, które ściśle pasują do ich scenariuszy użytkowania.

Na przykład mój zespół pisze programy, które w czasie pisania analizują kod C # i VB podczas pisania. Niektóre z tych plików kodu są ogromne i dlatego nie możemy wykonywać operacji na łańcuchach O (n) w celu wyodrębnienia podciągów lub wstawienia lub usunięcia znaków. Zbudowaliśmy kilka trwałych niezmiennych struktur danych do reprezentowania zmian w buforze tekstowym, które pozwalają nam szybko i skutecznie ponownie wykorzystać większość istniejących danych łańcuchowych oraz istniejących analiz leksykalnych i składniowych po typowej edycji. Był to trudny problem do rozwiązania, a jego rozwiązanie było ściśle dostosowane do konkretnej dziedziny edycji kodu C # i VB. Byłoby nierealistyczne oczekiwanie, że wbudowany typ ciągu rozwiąże dla nas ten problem.


47
Interesujące byłoby kontrastowanie z tym, jak robi to Java (a przynajmniej robiła to w pewnym momencie w przeszłości): Podciąg zwraca nowy ciąg, ale wskazuje ten sam znak char [] co większy ciąg - oznacza to, że większy znak [] nie można już zbierać śmieci, dopóki podciąg nie wyjdzie poza zakres. Zdecydowanie wolę implementację .net.
Michael Stum

13
Widziałem całkiem sporo tego rodzaju kodu: string contents = File.ReadAllText(filename); foreach (string line in content.Split("\n")) ...lub innych jego wersji. Mam na myśli przeczytanie całego pliku, a następnie przetworzenie różnych części. Ten rodzaj kodu byłby znacznie szybszy i wymagałby mniej pamięci, gdyby ciąg był trwały; zawsze będziesz miał dokładnie jedną kopię pliku w pamięci zamiast kopiować każdą linię, a następnie części każdej linii podczas jej przetwarzania. Jednak, jak powiedział Eric - nie jest to typowy przypadek użycia.
konfigurator

18
@configurator: Ponadto w .NET 4 metoda File.ReadLines dzieli plik tekstowy na linie bez konieczności wcześniejszego wczytywania go do pamięci.
Eric Lippert,

8
@Michael: Java Stringjest zaimplementowana jako trwała struktura danych (nie jest to określone w standardach, ale wszystkie znane mi implementacje to robią).
Joachim Sauer

33
Krótka odpowiedź: tworzona jest kopia danych, aby umożliwić odśmiecanie oryginalnego ciągu znaków .
Qtax,

121

Właśnie dlatego, że ciągi są niezmienne, .Substringmuszą wykonać kopię przynajmniej części oryginalnego ciągu. Wykonanie kopii n bajtów powinno zająć O (n) czasu.

Jak myślisz, jak skopiowałbyś kilka bajtów w stałym czasie?


EDYCJA: Mehrdad sugeruje, aby w ogóle nie kopiować łańcucha, ale zachować odniesienie do jego fragmentu.

Zastanów się w .Net, łańcuchu wielu megabajtów, do którego ktoś dzwoni .SubString(n, n+3)(dla dowolnego n w środku łańcucha).

Teraz ciąg ENTIRE nie może być Garbage Collective tylko dlatego, że jedno odwołanie zawiera 4 znaki? To wydaje się absurdalne marnowanie przestrzeni.

Ponadto śledzenie odniesień do podciągów (które mogą być nawet wewnątrz podciągów) i próba kopiowania w optymalnych momentach, aby uniknąć pokonania GC (jak opisano powyżej), sprawia, że ​​koncepcja jest koszmarem. Kopiowanie .SubStringi utrzymanie prostego niezmiennego modelu jest o wiele prostsze i bardziej niezawodne .


EDYCJA: Oto dobra lektura na temat niebezpieczeństwa przechowywania odniesień do podciągów w większych ciągach.


5
+1: Dokładnie moje myśli. Wewnętrznie prawdopodobnie używa, memcpyco wciąż oznacza O (n).
leppie

7
@abelenky: Chyba może w ogóle nie kopiując? Już tam jest, dlaczego warto to skopiować?
user541686,

2
@ Mehrdad: JEŻELI jesteś po występie. W takim przypadku po prostu idź niebezpiecznie. Następnie możesz uzyskać char*podciąg.
leppie

9
@ Mehrdad - możesz się tam spodziewać zbyt wiele, nazywa się StringBuilder i dobrze jest budować ciągi. To nie nazywa się StringMultiPurposeManipulator
MattDavey

3
@SamuelNeff, @Mehrdad: Ciągi w .NET nieNULLzakończone. Jak wyjaśniono w poście Lipperta , pierwsze 4 bajty zawierają długość łańcucha. Właśnie dlatego, jak zauważa Skeet, mogą one zawierać \0postacie.
Elideb

33

Java (w przeciwieństwie do .NET) zapewnia dwa sposoby działania Substring(), możesz zastanowić się, czy chcesz zachować tylko odwołanie, czy skopiować cały podciąg w nowej lokalizacji pamięci.

Prosty .substring(...)dzieli wewnętrznie używaną chartablicę z oryginalnym obiektem String, który następnie new String(...)można w razie potrzeby skopiować do nowej tablicy (aby uniknąć utrudnienia wyrzucania elementów bezużytecznych).

Myślę, że ten rodzaj elastyczności jest najlepszą opcją dla programisty.


50
Nazywasz to „elastycznością” Nazywam to „Sposób na przypadkowe wstawienie trudnego do zdiagnozowania błędu (lub problemu z wydajnością) do oprogramowania, ponieważ nie zdawałem sobie sprawy, że muszę się zatrzymać i pomyśleć o wszystkich miejscach, w których ten kod może być wywoływany z (w tym tych, które zostałyby wynalezione tylko w następnej wersji) tylko po to, aby uzyskać 4 znaki ze środka łańcucha ”
Nir

3
downvote wycofane ... Po nieco bardziej uważnym przejrzeniu kodu wygląda na to, że podciąg w java odwołuje się do wspólnej tablicy, przynajmniej w wersji openjdk. A jeśli chcesz zapewnić nowy ciąg, jest na to sposób.
Don Roby

11
@Nir: Nazywam to „uprzedzeniem status quo”. Dla ciebie sposób Java robi to obarczony ryzykiem, a jedyny sensowny wybór to sposób .Net. W przypadku programistów Java sytuacja jest odwrotna.
Michael Borgwardt,

7
Zdecydowanie wolę .NET, ale brzmi to tak, jakby Java miała rację. Jest to przydatne, że deweloper będzie wolno mieć dostęp do naprawdę O (1) podłańcuchów metodą (bez toczenia własny typ string, które utrudniają współpracę z każdej innej bibliotece, a nie będzie tak skuteczny jak wbudowany w roztworze ). Rozwiązanie Javy jest prawdopodobnie mało wydajne (wymaga co najmniej dwóch obiektów sterty, jednego dla oryginalnego ciągu, a drugiego dla podłańcucha); języki obsługujące wycinki skutecznie zastępują drugi obiekt parą wskaźników na stosie.
Qwertie

10
Od JDK 7u6 nie jest to już prawdą - teraz Java zawsze kopiuje zawartość String dla każdego .substring(...).
Xaerxess,

12

Java służyła do odwoływania się do większych ciągów, ale:

Java zmieniła również swoje zachowanie na kopiowanie , aby uniknąć wycieku pamięci.

Wydaje mi się, że można to poprawić: dlaczego po prostu nie kopiować warunkowo?

Jeśli podciąg ma co najmniej połowę rozmiaru elementu nadrzędnego, można odwołać się do elementu nadrzędnego. W przeciwnym razie można po prostu wykonać kopię. Pozwala to uniknąć wycieku dużej ilości pamięci, a jednocześnie zapewnia znaczne korzyści.


Zawsze kopiowanie pozwala usunąć wewnętrzną tablicę. Zmniejsza o połowę liczbę przydziałów sterty, oszczędzając pamięć w typowym przypadku krótkich ciągów. Oznacza to również, że nie musisz przeskakiwać dodatkowej pośredniczości dla każdego dostępu do postaci.
CodesInChaos

2
Myślę, że ważną rzeczą, którą należy wziąć z tego, jest to, że Java faktycznie zmieniła się z używania tej samej bazy char[](z różnymi wskaźnikami na początku i na końcu) na tworzenie nowej String. To wyraźnie pokazuje, że analiza kosztów i korzyści musi wykazywać preferencję dla tworzenia nowego String.
Filogeneza

2

Żadna z odpowiedzi tutaj nie dotyczyła „problemu braketingu”, co oznacza, że ​​ciągi w .NET są reprezentowane jako kombinacja BStr (długość przechowywana w pamięci „przed” wskaźnikiem) i CStr (ciąg kończy się na „\ 0”).

Ciąg „Hello there” jest zatem reprezentowany jako

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(jeżeli jest przypisany do char*w fixed-statement wskaźnik będzie wskazywać na 0x48).

Ta struktura pozwala na szybkie wyszukiwanie długości łańcucha (przydatne w wielu kontekstach) i umożliwia przekazywanie wskaźnika w interfejsie P / Invoke do interfejsów API Win32 (lub innych), które oczekują łańcucha zakończonego zerem.

Kiedy robisz Substring(0, 5)„och, ale obiecałem, że po ostatnim znaku będzie znak zerowy”, mówi, że musisz zrobić kopię. Nawet jeśli masz podłańcuch na końcu, nie byłoby miejsca na umieszczenie długości bez uszkodzenia innych zmiennych.


Czasami jednak naprawdę chcesz mówić o „środku ciągu” i niekoniecznie zależy ci na zachowaniu P / Invoke. Ostatnio dodaneReadOnlySpan<T> strukturę można wykorzystać do uzyskania podciągu bez kopii:

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

The ReadOnlySpan<char>„Podciąg” sklepów długość niezależnie, i to nie gwarantuje, że istnieje „\ 0” po zakończeniu wartości. Można go używać na wiele sposobów „jak ciąg”, ale nie jest to „ciąg”, ponieważ nie ma ani cech BStr, ani CStr (a tym bardziej obu). Jeśli nigdy (bezpośrednio) P / Invoke, nie ma dużej różnicy (chyba że interfejs API, który chcesz wywołać, nie ma ReadOnlySpan<char>przeciążenia).

ReadOnlySpan<char>nie może być użyty jako pole typu referencyjnego, więc istnieje również ReadOnlyMemory<char>(s.AsMemory(0, 5) ), który jest pośrednim sposobem na posiadanie ReadOnlySpan<char>, więc istnieją takie same różnice-od- stringistnienia.

Niektóre odpowiedzi / komentarze do poprzednich odpowiedzi mówiły o tym, że zbędne jest, aby śmieciarz musiał przechowywać ciąg znaków o długości miliona znaków, podczas gdy ty nadal mówisz o 5 znakach. Właśnie takie zachowanie można uzyskać dzięki temu ReadOnlySpan<char>podejściu. Jeśli wykonujesz tylko krótkie obliczenia, podejście ReadOnlySpan jest prawdopodobnie lepsze. Jeśli musisz go zachować przez jakiś czas, a zamierzasz zachować tylko niewielki procent oryginalnego ciągu, wykonanie poprawnego podciągu (w celu usunięcia nadmiaru danych) jest prawdopodobnie lepsze. Gdzieś pośrodku jest punkt przejścia, ale zależy to od konkretnego użycia.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.