Typowe strlen() przechodzenie z pierwszego znaku do znalezienia \0. Wymaga to przemierzania każdej postaci. W sensie algorytmu, jego O (N).szybszy strlen?
Czy jest jakiś szybszy sposób to zrobić, gdy dane wejściowe są niejasno zdefiniowane. Podobny: długość będzie mniejsza niż 50, a długość będzie wynosić około 200 znaków.
Pomyślałem o wyszukiwaniu bloków i wszystkich, ale nie otrzymałem żadnej optymalizacji.
W rzeczywistości, glibc's implementation z strlen jest interesującym przykładem podejścia wektoryzacji.Jest to osobliwe, ponieważ nie używa instrukcji wektorowych, ale znajduje sposób na użycie zwykłych instrukcji na 32 lub 64-bitowych słowach z bufora.
bardzo sprytnie! –
Z drugiej strony, przynajmniej na x86/x86_64 i gcc, po prostu otrzymasz wbudowany kompilator. – LnxPrgr3
Tak, musisz podać inną nazwę, jeśli chcesz się upewnić, że używana wersja jest twoja. Jeśli zamierzasz to zrobić, możesz równie dobrze upewnić się, że wszystkie ciągi, przez które zostanie przekazana twoja wersja, są wyrównane do słów (jeśli to możliwe) i całkowicie usunąć początkową pętlę char-by-char. –
Pewnie. Śledź długość podczas pisania na łańcuchu.
+1: Horta pascal! –
+1: Hooray Fortran (i nie zezwalamy na zmianę w jakikolwiek sposób po deklaracji) –
zrobiłem duże ulepszenia na strcat przy użyciu tej techniki – Mandrake
Krótka odpowiedź: nie.
Dłuższa odpowiedź: czy naprawdę sądzisz, że gdyby istniał szybszy sposób sprawdzania długości napisów dla łańcuchów C typu barebone, coś tak powszechnie używane, jak biblioteka ciągów C, nie zostałoby już włączone?
Bez dodatkowej wiedzy na temat napisu, musisz sprawdzić każdy znak. Jeśli chcesz zachować te dodatkowe informacje, możesz utworzyć struct, który przechowuje długość jako pole w strukturze (oprócz faktycznej tablicy znaków/wskaźnika dla ciągu znaków), w którym to przypadku możesz wtedy utworzyć długość wyszukiwanie czasu stałego, ale musiałby aktualizować to pole za każdym razem, gdy modyfikowałeś ciąg znaków.
Następnie będziemy mieli ciągi Pascal na nowo. :) – wadesworld
Ale prawdopodobnie mielibyśmy mniej przepełnień bufora (gdyby były wbudowane w język lub używane konsekwentnie) - co byłoby dobre! –
Oczywiście, jeśli twój ciąg ma znaną minimalną długość, możesz rozpocząć wyszukiwanie w tej pozycji.
Poza tym nic nie można zrobić; jeśli próbujesz zrobić coś sprytnego i znaleźć bajt, musisz sprawdzić każdy bajt między początkiem łańcucha a tym punktem, aby upewnić się, że nie było wcześniejszego \0.
Nie można powiedzieć, że strlen nie może być zoptymalizowany. Może być poddawany potokom, a przy każdym porównywaniu może być przetwarzany na kawałki wielkości słów lub wektorów. W przypadku większości architektur niektóre kombinacje tych i innych podejść spowodują znaczne przyspieszenie w stosunku do wartości naiwnej pętli porównania bajtów. Oczywiście na najbardziej dojrzałych platformach system strlen jest już zaimplementowany przy użyciu tych technik.
Możesz spróbować użyć wektoryzacji. Nie jestem pewien, czy kompilator będzie w stanie go wykonać, ale zrobiłem to ręcznie (przy użyciu właściwości wewnętrznych). Ale może ci pomóc tylko dla długich łańcuchów.
Stosuj ciągi stl, jest to bardziej bezpieczne, a klasa std :: string zawiera jego długość.
W jaki sposób wektoryzacja może pomóc? Nawet jeśli bufor miał, powiedzmy 4 KB, nie ma gwarancji co do zawartości ciągu po pierwszym pustym miejscu, więc jeśli wektoryzacja rozpoczęła 4 operacje (wątki?) Na granicach 1 KB, nie wiadomo, od czego zaczyna się ta trójka pojawi się niezerowe przesunięcie. Przypuszczam, że wynik musiałby być minimalnym z 4 zwracanych wartości - gdzie niezerowe przesunięcie wątków musiałoby dodać swoją pozycję początkową do zwróconej długości. –
Myślę, że Elalfer proponuje przypisanie każdego kolejnego bajtu do wektora, który ma być sprawdzony jako całość, a następnie przewijanie skanu ciągów długości wektora. To z pewnością zadziała, zakładając, że masz architekturę opartą na wektorach. –
@ Jonathan Vectorization nie używa wątków! Wektoryzacja oznacza użycie modelu programowania SIMD do równoczesnego sprawdzania kolejnych bajtów dla zera. http://en.wikipedia.org/wiki/SIMD Pomaga to, aby wyrównanie wektorowe zawsze dopasowywało je do jednej strony. Ta implementacja zwykle przepełnia bufor, ale nie jest przechwytywany przez MMU. Znajdujemy te łagodne przepełnienia bufora w analizatorze, nad którym pracuję. Zobacz także http://tsunanet.net/~tsuna/strlen.c.html dla imponującej implementacji C bez specjalnych instrukcji wektorowych. –
Jack
strlen prace szukają końcówka '\ 0', oto implementacja zaczerpnięte z OpenBSD:
size_t
strlen(const char *str)
{
const char *s;
for (s = str; *s; ++s)
;
return (s - str);
}
Teraz uważają, że wiesz, że długość wynosi około 200 znaków, jak powiedziałeś. Powiedzmy, że zaczynasz od 200 i zapętlasz w górę i w dół dla "\ 0". Znalazłeś jeden w 204, co to znaczy? Że łańcuch ma długość 204 znaków? NIE! Może się to skończyć wcześniej z innym "\ 0" i wszystko, co zrobiłeś, to wyglądać poza granicami.
Dzięki za odpowiedź. Jak już powiedziałem, długość jest niejasno przepowiedziana i może nie kończyć się po znaku 200. Ponadto, jeśli zaczynamy czytać po 200 znaków, możemy czytać nieprawidłowy ciąg znaków (jeśli string zakończył się około 100 znaków ...) – Jack
Link mówi samo: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/strlen.c?annotate=1.7 – Jack
Uzyskaj procesor Core i7.
Core i7 dostarczany jest z zestawem instrukcji SSE 4.2. Firma Intel dodała cztery dodatkowe instrukcje wektorowe, aby przyspieszyć działanie strlen i powiązanych zadań wyszukiwania.
Oto kilka ciekawych myśli o nowej instrukcji:
Dzięki za odpowiedź. Jak mówi George Verghese, sprzętowe wsparcie zawsze pomaga :) – Jack
pewien. 'return 4;'. Gwarantowana błyskawica! Numer został wybrany przez rzetelny rzut kostką. – Geo
@Geo [Cute] (https://xkcd.com/221/), ale to nie implementuje 'strlen' dla znacznej większości danych wejściowych. – imallett