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

Dokładnie Ponieważ ciągi znaków są niezmienne, .Substring musi wykonać kopię co najmniej części oryginalnego ciągu znaków. Wykonanie kopii N bajtów powinno zająć O (n) czas.

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

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

Rozważmy w. Net, wielomegabajtowy ciąg znaków, na który ktoś wywołuje .SubString(n, n+3) (dla dowolnego n w środku Sznurka).

Teraz, cały łańcuch nie może być zbierany śmieci tylko dlatego, że jedno odniesienie jest trzymane na 4 znaki? To wygląda na niedorzeczne marnowanie miejsca.

Ponadto, śledzenie odwołań do podłańcuchów (które mogą być nawet wewnątrz podłańcuchów) i próba skopiowania w optymalnym czasie, aby uniknąć pokonania GC (jak opisano powyżej), sprawia, że koncepcja jest koszmarna. O wiele prostsze i bardziej niezawodne jest kopiowanie na .SubString i utrzymywanie prostego niezmiennego model.

EDIT: Oto dobra mała lektura o niebezpieczeństwie utrzymywania odniesień do podłańcuchów w większych łańcuchach.

Java (w przeciwieństwie do. Net) zapewnia dwa sposoby działania Substring(), możesz rozważyć, czy chcesz zachować tylko odniesienie, czy skopiować cały podłańcuch do nowej lokalizacji pamięci.

Prosta .substring(...) dzieli wewnętrznie używaną tablicę char z oryginalnym obiektem String, który następnie za pomocą {[3] } można skopiować do nowej tablicy, w razie potrzeby (aby uniknąć utrudnień w zbieraniu śmieci oryginalnej tablicy).

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

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

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

Jeśli podłańcuch jest co najmniej o połowę mniejszy od rodzica, można odwołać się do niego. W przeciwnym razie można zrobić kopię. Pozwala to uniknąć wycieku dużej ilości pamięci, jednocześnie zapewniając znaczne korzyści.

Żadna z odpowiedzi nie rozwiązała problemu bracketingu, który polega na tym, że ciągi znaków 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').

Łańcuch "Hello there" jest więc 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śli przypisany do char* w instrukcji fixed - wskaźnik wskazywałby na 0x48.)

Ta struktura pozwala na szybkie wyszukiwanie długości łańcucha (przydatne w wielu jest to możliwe dzięki temu, że nie jest to możliwe, ponieważ nie jest to możliwe, ponieważ nie jest to możliwe.

Kiedy robisz Substring(0, 5) zasada "oh, ale obiecałem, że będzie znak null po ostatnim znaku" mówi, że musisz zrobić kopię. Nawet jeśli masz podłańcuch na końcu, to nie ma miejsca, aby umieścić długość bez uszkodzenia innych zmiennych.

Czasami jednak naprawdę chcesz porozmawiać o " środku Sznurka", i niekoniecznie zależy ci na zachowaniu P/Invoke. Ostatnio dodana struktura ReadOnlySpan<T> może zostać użyta do uzyskania podłańcucha bez kopiowania:

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

ReadOnlySpan<char> "substring" przechowuje długość niezależnie i nie gwarantuje, że po końcu wartości znajduje się "\0". Może być używany na wiele sposobów "jak ciąg", ale nie jest "ciągiem", ponieważ nie ma ani właściwości BStr, ani CSTR (a tym bardziej obu). Jeśli nigdy (bezpośrednio) P / wywołasz to nie ma zbyt wiele różnica (chyba że API, które chcesz wywołać nie ma przeciążenia ReadOnlySpan<char>).

ReadOnlySpan<char> nie może być używany jako pole typu odniesienia, więc jest też ReadOnlyMemory<char> (s.AsMemory(0, 5)), co jest pośrednim sposobem posiadania ReadOnlySpan<char>, więc istnieją te same różnice-od-string.

Niektóre z odpowiedzi / komentarzy do poprzednich odpowiedzi mówiły o marnotrawstwie, aby garbage collector musiał trzymać ciąg milionów znaków wokół, podczas gdy nadal mówisz o 5 znakach. To jest dokładnie takie zachowanie można uzyskać przy podejściu ReadOnlySpan<char>. Jeśli robisz tylko krótkie obliczenia, podejście ReadOnlySpan jest prawdopodobnie lepsze. Jeśli musisz utrzymywać go przez jakiś czas i zachowasz tylko niewielki procent oryginalnego ciągu, prawdopodobnie lepiej będzie wykonać odpowiedni podłańcuch (aby odciąć nadmiar danych). Gdzieś pośrodku znajduje się punkt przejściowy, ale zależy to od konkretnego zastosowania.