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

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?

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.

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.

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.

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.

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