strlen más rápido?

Question

típico strlen() atraviesa desde el primer carácter hasta que encuentra \0. Esto requiere que atraviese cada personaje. En sentido algorítmico, es O (N).

¿Hay alguna manera más rápida de hacerlo cuando la entrada está vagamente definida? Me gusta: la longitud sería menor que 50, o la longitud sería de alrededor de 200 caracteres.

Pensé en bloques de búsqueda y todo pero no obtuve ninguna optimización.

Answer 1

En realidad, glibc's implementation de strlen es un ejemplo interesante del enfoque de vectorización.Es peculiar ya que no usa instrucciones vectoriales, pero encuentra una manera de usar solo instrucciones ordinarias en palabras de 32 o 64 bits del búfer.

Answer 2

Sure. Mantenga un registro de la longitud mientras escribe en la cadena.

Answer 3

La respuesta corta: no.

La respuesta más larga: ¿realmente crees que si hubiera una manera más rápida de verificar la longitud de cadena para las cadenas de C barebones, algo tan comúnmente utilizado como la biblioteca de cadenas C ya no lo habría incorporado?

Sin algún tipo de conocimiento adicional sobre una cadena, debe verificar cada carácter. Si está dispuesto a mantener esa información adicional, puede crear un struct que almacene la longitud como un campo en la estructura (además de la matriz de caracteres real/puntero para la cadena), en cuyo caso podría hacer la longitud búsqueda de tiempo constante, pero tendría que actualizar ese campo cada vez que modificó la cadena.

Answer 4

Obviamente, si su cadena tiene una longitud mínima conocida, puede comenzar su búsqueda en esa posición.

Más allá de eso, no hay nada que puedas hacer; Si intenta hacer algo inteligente y encuentra un byte \0, aún necesita verificar cada byte entre el inicio de la cadena y ese punto para asegurarse de que no haya habido un \0 anterior.

Eso no quiere decir que strlen no se puede optimizar. Se puede canalizar y se puede procesar procesadores de tamaño de palabra o vector con cada comparación. En la mayoría de las arquitecturas, una combinación de estos y otros enfoques producirán una aceleración sustancial de factor constante sobre un circuito ingenuo de comparación de bytes. Por supuesto, en las plataformas más maduras, el sistema strlen ya está implementado usando estas técnicas.

Answer 5

Puede intentar usar la vectorización. No estoy seguro si el compilador podrá realizarlo, pero lo hice manualmente (usando intrínsecos). Pero podría ayudarte solo para cadenas largas.

Use stl strings, es más seguro y std :: string class contiene su longitud.

Answer 6

Jack,

strlen obras de buscar la terminación '\ 0', aquí es una implementación tomada de OpenBSD:

size_t 
strlen(const char *str) 
{ 
     const char *s; 

     for (s = str; *s; ++s) 
       ; 
     return (s - str); 
} 

Ahora, tenga en cuenta que usted sabe la longitud es de unos 200 caracteres, como tu dijiste. Digamos que comienzas en 200 y bucle arriba y abajo para un '\ 0'. Has encontrado uno en 204, ¿qué significa? ¿Que la cuerda tiene 204 caracteres de largo? ¡NO! Podría terminar antes con otro '\ 0' y todo lo que hizo fue mirar fuera de límites.

Answer 7

Obtenga un procesador Core i7.

Core i7 viene con el conjunto de instrucciones SSE 4.2. Intel agregó cuatro instrucciones vectoriales adicionales para acelerar las tareas de búsqueda relacionadas con strlen y relacionadas.

Aquí están algunas ideas interesantes sobre las nuevas instrucciones:

http://smallcode.weblogs.us/oldblog/2007/11/