programa lenguaje fuente estructuras estructura ejercicios ejemplos codigos codigo basicos arreglo anidadas c++ vector data-structures hashmap

lenguaje - C++ estructura de datos más rápida para múltiples búsquedas



estructuras anidadas en c (9)

A menos que esté haciendo cientos de millones de búsquedas por segundo, no podrá notar la diferencia. Si ESTÁ haciendo cientos de millones de búsquedas por segundo, intente con un árbol de raíces. Es muy caro en la memoria pero con este pequeño conjunto de datos que no debería importar.

Una vez que lo escribas, perfilalo.

Codificación en C ++. Necesito una estructura de datos para un conjunto de cadenas ordenadas. Insertaré todas las cadenas en una sola vez y no la actualizaré, pero buscaré cadenas muy a menudo. Todo lo que necesito para ver si existe una cadena de dar en la estructura o no. Estoy esperando que la lista sea de alrededor de 100 cadenas. ¿Cuál sería una estructura más rápida? Estaba pensando en hashmap al principio, pero vi en algún lugar que para una cantidad tan pequeña de elementos, una búsqueda binaria sobre un vector funcionaría mejor (ya que están ordenados).

Use std::unordered_set<std::string> , que es muy adecuado para su caso. Puede tener un std::set<std::string> si también necesita iterarlos en orden.

Si después de hacer un perfil descubres que dedicas todo tu tiempo a consultar la estructura de datos, entonces será el momento de hacer otra pregunta (con el código preciso que utilizarás).

La mejor (y única) forma de decir qué estructura es la más rápida para una determinada situación es compararla / medirla con diferentes estructuras de datos. Luego elige el más rápido.

O en otras palabras: medir tu código te da una ventaja sobre aquellas personas que piensan que son demasiado inteligentes para medir. ;)

Para listas más bien pequeñas, como los 100 elementos que mencionas en tu pregunta, no importa mucho qué estructura / algoritmo utilizas, porque el tiempo ganado es probablemente insignificante, a menos que tu programa realice esa búsqueda muy a menudo.

Esta es una pregunta interesante porque está muy cerca del concepto de JAVA String Pool. Java usa JNI llamada método nativo correspondiente que es implementado por C ++

El grupo de cadenas es la implementación particular de la JVM del concepto de prácticas de cadenas :

En ciencias de la computación, el internamiento de cadenas es un método para almacenar solo una copia de cada valor de cadena distinto, que debe ser inmutable. Las cadenas de internados hacen que algunas tareas de procesamiento de cadenas sean más eficientes en tiempo o espacio a costa de requerir más tiempo cuando la cadena se crea o se interna. Los valores distintos se almacenan en un grupo interno de cadena.

Veamos cómo implementar String pool dentro de Java 7

/** * Returns a canonical representation for the string object. * <p> * A pool of strings, initially empty, is maintained privately by the * class <code>String</code>. * <p> * When the intern method is invoked, if the pool already contains a * string equal to this <code>String</code> object as determined by * the {@link #equals(Object)} method, then the string from the pool is * returned. Otherwise, this <code>String</code> object is added to the * pool and a reference to this <code>String</code> object is returned. * <p> * It follows that for any two strings <code>s</code> and <code>t</code>, * <code>s.intern()&nbsp;==&nbsp;t.intern()</code> is <code>true</code> * if and only if <code>s.equals(t)</code> is <code>true</code>. * <p> * All literal strings and string-valued constant expressions are * interned. String literals are defined in section 3.10.5 of the * <cite>The Java&trade; Language Specification</cite>. * * @return a string that has the same contents as this string, but is * guaranteed to be from a pool of unique strings. */ public native String intern();

Cuando se invoca el método interno, si el grupo ya contiene una cadena igual a este objeto String como lo determina el objeto igual, se devuelve la cadena del grupo. De lo contrario, este objeto se agrega al grupo y se devuelve una referencia a este objeto de cadena.

Java use JNI call método nativo StringTable.intern implementado por C ++

/ openjdk7 / jdk / src / share / native / java / lang / String.c

Java_java_lang_String_intern(JNIEnv *env, jobject this) { return JVM_InternString(env, this); }

/ openjdk7 / hotspot / src / share / vm / prims / jvm.h

/* * java.lang.String */ JNIEXPORT jstring JNICALL JVM_InternString(JNIEnv *env, jstring str);

/ openjdk7 / hotspot / src / share / vm / prims / jvm.cpp

// String support /////////////////////////////////////////////////////////////////////////// JVM_ENTRY(jstring, JVM_InternString(JNIEnv *env, jstring str)) JVMWrapper("JVM_InternString"); JvmtiVMObjectAllocEventCollector oam; if (str == NULL) return NULL; oop string = JNIHandles::resolve_non_null(str); oop result = StringTable::intern(string, CHECK_NULL); return (jstring) JNIHandles::make_local(env, result); JVM_END

/ openjdk7 / hotspot / src / share / vm / classfile / symbolTable.cpp

oop StringTable::intern(Handle string_or_null, jchar* name, int len, TRAPS) { unsigned int hashValue = java_lang_String::hash_string(name, len); int index = the_table()->hash_to_index(hashValue); oop string = the_table()->lookup(index, name, len, hashValue); // Found if (string != NULL) return string; // Otherwise, add to symbol to table return the_table()->basic_add(index, string_or_null, name, len, hashValue, CHECK_NULL); }

/ openjdk7 / hotspot / src / share / vm / classfile / symbolTable.cpp

oop StringTable::lookup(int index, jchar* name, int len, unsigned int hash) { for (HashtableEntry<oop>* l = bucket(index); l != NULL; l = l->next()) { if (l->hash() == hash) { if (java_lang_String::equals(l->literal(), name, len)) { return l->literal(); } } } return NULL; }

Si desea obtener más información acerca de cómo los ingenieros de Oracle modifican la lógica de agrupamiento de cadenas en Java 7, el enlace le será útil. Informe de errores: haga que el tamaño de la tabla de cadenas sea configurable . El conjunto de cadenas se implementa como una capacidad fija tiene un mapa con cada segmento que contiene una lista de cadenas con el mismo código de código. El tamaño del grupo predeterminado es 1009.

Para su pregunta, puede escribir un programa de prueba para comparar con este método para acumular la estructura de datos y determinar cuál es mejor.

La pregunta es un tanto vaga, pero el algoritmo de coincidencia de cadenas más rápido es una máquina de estados finitos, es decir, un algoritmo aho-corasick. Es la generalización del algoritmo de correspondencia e Knuth-Morris-Pratt. Si solo desea una búsqueda simple, puede probar un trie ternario o un trie comprimido (árbol de raíces) si el espacio es importante o incluso la búsqueda binaria.

Suponiendo que se trata de CPU "de tamaño completo" 1 , una búsqueda binaria a través de cadenas, incluso con solo 100 elementos, es bastante lenta , en relación con otras soluciones al menos. Es posible que sufra varios errores de trazado de las bifurcaciones en cada búsqueda, y probablemente termine examinando cada carácter en la cadena de entrada varias veces (ya que necesita strcmp repetidamente en cada nodo en la búsqueda binaria).

Como alguien ya señaló, la única forma real de saber es medir , pero para hacerlo, ¡todavía debe ser capaz de averiguar cuáles son los candidatos en primer lugar! Además, no siempre es posible medir en un escenario realista , ya que tal vez ni siquiera conozca ese escenario (imagínese, por ejemplo, diseñar una función de biblioteca que se use ampliamente en muchos casos diferentes).

Finalmente, comprender lo que probablemente sea rápido te permite eliminar candidatos que sabes que funcionarán mal y te permite verificar los resultados de tus pruebas con tu intuición: si algo es mucho más lento de lo que esperabas, vale la pena verificar por qué (el compilador hacer algo estúpido), y si algo es mucho más rápido , tal vez es hora de actualizar su intuición.

Por lo tanto, trataré de dar un vistazo a lo que va a ser rápido, suponiendo que la velocidad realmente importa aquí, y puede pasar algún tiempo validando una solución compleja. Como línea de base, una implementación directa probablemente tomará 100 ns, y una realmente optimizada tal vez 10 ns. Entonces, si gastas 10 horas de ingeniería en esto, tendrás que llamar a esta función 400 mil millones de veces solo para recuperar tus 10 horas 5 . Cuando se tiene en cuenta el riesgo de errores, la complejidad del mantenimiento y otros gastos generales, se va a querer asegurar de llamar a esta función muchos trillones de veces antes de tratar de optimizarla. Tales funciones son raras, pero ciertamente existen 4 .

Dicho esto, se está perdiendo una gran cantidad de información que se necesitaría para ayudar a diseñar una solución muy rápida, como por ejemplo:

  1. ¿Su entrada a la función de búsqueda es std::string o const char * o algo más?
  2. ¿Cuál es la longitud media y máxima de la cuerda?
  3. ¿La mayoría de tus búsquedas serán exitosas o no?
  4. ¿Puedes aceptar algunos falsos positivos?
  5. ¿Se conoce el conjunto de cadenas en tiempo de compilación, o está bien con una fase de inicialización larga?

Las respuestas anteriores pueden ayudarlo a dividir el espacio de diseño como se describe a continuación.

Filtros Bloom

Si por (4) puede aceptar un número (controlable) de falsos positivos 2 , o por (3) la mayoría de sus búsquedas no tendrán éxito, entonces debería considerar un Filtro Bloom . Por ejemplo, podría usar un filtro de 1024 bits (128 bytes) y usar un hash de 60 bits de la cadena para indexarlo con 6 funciones de 10 bits. Esto da una tasa <1% de falsos positivos.

Esto tiene la ventaja de que, aparte del cálculo hash, es independiente de la longitud de las cadenas y no depende del comportamiento de coincidencia (por ejemplo, una búsqueda que se base en la comparación de cadenas repetidas será más lenta si las cadenas tienden a tener un largo prefijos comunes).

Si puede aceptar falsos positivos, ya está listo, pero en el caso de que necesite que sea siempre correcto pero espere que la mayoría de las búsquedas no sean exitosas, lo usa como filtro: si el filtro bloom devuelve falso (el caso habitual) ya ha terminado , pero si devuelve verdadero, debe verificar dos veces en una de las estructuras siempre correctas que se describen a continuación. Entonces, el caso común es rápido, pero siempre se devuelve la respuesta correcta.

Perfect Hash

Si se conoce el conjunto de ~ 100 cadenas en tiempo de compilación, o si está bien haciendo un trabajo pesado de una sola vez para preprocesar las cadenas, podría considerar un hash perfecto. Si tiene un conjunto de búsqueda conocido en tiempo de compilación, puede simplemente gperf las cadenas en gperf y gperf una función de hash y una tabla de búsqueda.

Por ejemplo, acabo de alimentar 100 palabras aleatorias en inglés 3 en gperf y generó una función hash que solo necesita ver dos caracteres para distinguir de forma única cada palabra, como esta:

static unsigned int hash (const char *str, unsigned int len) { static unsigned char asso_values[] = { 115, 115, 115, 115, 115, 81, 48, 1, 77, 72, 115, 38, 81, 115, 115, 0, 73, 40, 44, 115, 32, 115, 41, 14, 3, 115, 115, 30, 115, 115, 115, 115, 115, 115, 115, 115, 115, 16, 18, 4, 31, 55, 13, 74, 51, 44, 32, 20, 4, 28, 45, 4, 19, 64, 34, 0, 21, 9, 40, 70, 16, 0, 115, 115, 115, 115, 115, 115, 115, 115, /* most of the table omitted */ }; register int hval = len; switch (hval) { default: hval += asso_values[(unsigned char)str[3]+1]; /*FALLTHROUGH*/ case 3: case 2: case 1: hval += asso_values[(unsigned char)str[0]]; break; } return hval; }

Ahora su función hash es rápida y probablemente esté bien pronosticada (si no tiene demasiadas cadenas de longitud 3 o menos). Para buscar una cadena, simplemente gperf en la tabla hash (también generada por gperf ), y compara lo que obtienes con la cadena de entrada.

Bajo algunas suposiciones razonables, esto va a ser lo más rápido que puedas: clang genera código como este:

in_word_set: # @in_word_set push rbx lea eax, [rsi - 3] xor ebx, ebx cmp eax, 19 ja .LBB0_7 lea ecx, [rsi - 1] mov eax, 3 cmp ecx, 3 jb .LBB0_3 movzx eax, byte ptr [rdi + 3] movzx eax, byte ptr [rax + hash.asso_values+1] add eax, esi .LBB0_3: movzx ecx, byte ptr [rdi] movzx edx, byte ptr [rcx + hash.asso_values] cdqe add rax, rdx cmp eax, 114 ja .LBB0_6 mov rbx, qword ptr [8*rax + in_word_set.wordlist] cmp cl, byte ptr [rbx] jne .LBB0_6 add rdi, 1 lea rsi, [rbx + 1] call strcmp test eax, eax je .LBB0_7 .LBB0_6: xor ebx, ebx .LBB0_7: mov rax, rbx pop rbx ret

Es un montón de código, pero con una cantidad razonable de ILP. La ruta crítica es a través de los 3 accesos dependientes a la memoria (buscar el valor char en str -> buscar el valor hash para char en la tabla de funciones hash -> buscar la cadena en la tabla hash real), se puede esperar que esto tome tal vez 20 ciclos típicamente (más el tiempo strcmp por supuesto).

Trie

La solución compsci "clásica" a este problema es el trie . El trie podría ser un enfoque razonable para su problema, especialmente muchas coincidencias no exitosas pueden rechazarse rápidamente dentro de los primeros caracteres (esto depende en gran parte del contenido del conjunto de coincidencias y de las cadenas que está comprobando).

Querrías una implementación rápida para hacer que esto funcione. En general, creo que este enfoque estará limitado por los accesos de memoria dependientes en serie; cada nodo probablemente sea visitado en una especie de enfoque de persecución de puntero, por lo que sufrirá una gran cantidad de latencia de acceso L1.

Optimizando strcmp

Casi todas las soluciones anteriores dependen de strcmp en algún momento; la excepción es el filtro de floración que permite falsos positivos. Así que quiere asegurarse de que esta parte de su código sea rápida.

En particular, los compiladores a veces pueden strcmp versiones " strcmp " de strcmp lugar de llamar a la función de la biblioteca: en prueba rápida icc hizo la creación, pero clang y gcc optaron por llamar a la función de la biblioteca. No hay una regla simple para la cual uno sea más rápido, pero en general las rutinas de la biblioteca a menudo se optimizan con SIMD y pueden ser más rápidas para cadenas largas, mientras que las versiones impresas evitan la sobrecarga de llamadas de función y pueden ser más rápidas para cadenas cortas. Puedes probar ambos enfoques y obligar a los compiladores a hacer lo que es más rápido en tu caso.

Aún mejor, puede aprovechar su control de las entradas para hacerlo mucho mejor: si puede asegurarse de que, por ejemplo, las cadenas de entrada serán nulas, de modo que su longitud sea múltiplo de 8, entonces podrá haga lo mismo para las cadenas de referencia en su tabla hash (o cualquier otra estructura) y podría comparar las cadenas de 8 bytes a la vez. Esto no solo acelera enormemente el emparejamiento, sino que también reduce drásticamente los errores de trazado de las ramificaciones porque, en esencia, cuantifica el comportamiento de los bucles (todas las cadenas de 1 a 8 caracteres repiten una vez, etc.).

1 Aquí me refiero a las CPU de escritorio, servidor, computadora portátil o incluso las modernas CPUs de teléfonos inteligentes y las MCU de dispositivos no integrados o algo por el estilo.

2 Permitir falsos positivos significa que está bien si su "está en conjunto" a veces devuelve verdadero incluso cuando la cadena de entrada no está en el conjunto. Tenga en cuenta que nunca se equivoca al revés: siempre devuelve verdadero cuando la cadena está en el conjunto; no hay falsos negativos .

3 Específicamente, awk ''NR%990==0'' /usr/share/dict/american-english > words .

4 Por ejemplo, ¿cuántas veces strcmp se ha llamado a strcmp en la historia de la informática? ¿Cuánto tiempo se ahorraría si fuera 1 ns más rápido?

5 Eso equivale a igualar de alguna manera el tiempo de CPU con el tiempo de ingeniería, que probablemente está apagado en un factor de más de 1000x: Amazon AWS cobra aproximadamente $ 0.02 por hora de CPU, y un buen ingeniero puede esperar quizás $ 50 por hora (en el primer mundo). Entonces, por ese (¡muy duro!) Tiempo de ingeniería métrica es 2500x más valioso que el tiempo de CPU. Entonces quizás necesite cuadrillones de llamadas para 10 horas de trabajo para pagar ...

Depende de cuán diferentes sean sus cadenas o qué forma particular tengan.

Creo que un hashmap es una buena idea, si estás dispuesto a tomar en la memoria los gastos generales. Para solo alrededor de 100 cadenas, el primer carácter es suficiente:

String* myStrings[256];

Simplemente mira el primer carácter de tu cadena para determinar en qué matriz podría estar.

Si sus cadenas son lo suficientemente heterogéneas (es decir, generalmente no comienzan con la misma letra), la ganancia es teóricamente de 256x de velocidad. La pérdida es adicional de 257 punteros (257 * 64 = 16448 bits) en la memoria. Puede compensar un poco por esa pérdida eliminando el primer carácter de las cadenas almacenadas reales.

Si decide escalar hasta 2 caracteres o más, las ventajas y los inconvenientes son exponenciales.

String* myStrings[256][256][256];

Sin embargo, si sus cadenas son especiales y no pueden, por ejemplo, comenzar con ningún carácter o contener ningún carácter, entonces puede reducir el conjunto y asignar los caracteres usados ​​a un espacio.

char charToSlot[256]; String* myStrings[3];

Por ejemplo, en este caso, si sus cadenas solo pueden comenzar con los caracteres 100, 235 y 201, entonces charToSlot [100] = 0, charToSlot [235] = 1 y charToSlot [201] = 2.

Buscar el índice es un poco más lento, pero el impacto de la memoria es mínimo. Eso podría ayudarte si las cadenas que manipulas solo pueden contener el alfabeto en minúsculas. Entonces tu estructura ideal para un personaje sería:

char charToSlot[256]; String* myStrings[26];

Y se puede escalar más fácilmente:

char charToSlot[256]; String* myStrings[26][26][26];

Si no quiere hacer suposiciones sobre sus cadenas de caracteres (es decir, puede contener cualquier cosa), entonces podría implementar alguna indexación dinámica (los índices se agregan tan pronto como se necesiten, y la matriz necesita ser reasignada constantemente).

char charToSlot[256]; String**** myStrings;

Otro truco, si sus cadenas varían en longitud y son bastante pequeñas (5-30 de longitud), podría agregar un índice adicional que nuevamente multiplicaría la velocidad buscando solo las cuerdas con la misma longitud.

String* myStrings[30][256][256]...

Si cree que esas soluciones son demasiado pesadas, entonces puede adoptar un enfoque más estadístico. Podría dar la misma rama a varios caracteres. Por ejemplo, ''a'', ''b'', ''c'' y ''d'' bajarían todos de la misma manera, y tendrías 4 veces menos bifurcaciones. Luego llegaría a la lista y verificaría nuevamente, char por char, si una cadena es igual, con mayores posibilidades de obtener lo que desea.

Por ejemplo, si las cadenas pueden contener los 256 caracteres, pero no desea 256, sino 8 ramas, tendría:

String* myStrings[8];

Y para cualquier personaje, simplemente lo dividiría por 32 (muy rápido) para elegir la rama. Esta es probablemente la solución que recomendaría para su problema, ya que solo tiene unas 100 cadenas y probablemente no quiera una gran matriz.

También este escala más bien:

String* myStrings[8][8][8][8]...

Pero las matrices almacenadas podrían tener 32 veces más cadenas y el contenido no es determinista.

Nuevamente, todo depende de las propiedades particulares de sus cadenas y, más importante, de la cantidad de cadenas que tiene. Para una base de datos de cadenas realmente grande, a nadie le importaría ni siquiera un Terabit de cartografía si mejora la velocidad de búsqueda por un factor gigantesco y elimina el 99.99% de las iteraciones.

Trie es la mejor solución para ti. Digo esto porque no tienes muchas cuerdas, así que ir por este camino sería mejor. Puedes ver mi implementación de trie aquí en mi enlace github
https://github.com/prem-ktiw/Algorithmic-Codes/blob/master/Trie/char_trie.cpp
El código está bien comentado y le permitirá insertar una cadena en tiempo lineal, y buscar también en tiempo lineal. No hay problemas de colisión como se ve en hash.
La asignación dinámica se ha utilizado para que la memoria no sea un problema.
Lo único es que no puede tener múltiples copias duplicadas de la misma cadena en mi implementación, y no hay ningún registro de cuántas copias hay en el trie.
Me gustaría saber de usted sobre esto, en caso de que se necesite ayuda.

Puede probar la matriz de índice binario , es el campo de miembro de estructura de índice de biblioteca de c.

El blog tutorial está aquí https://minikawoon.quora.com/How-to-search-data-faster-on-big-amount-of-data-in-C-C++

Muestra: -

Paso 1. define tu estructura

typedef struct { char book_name[30]; char book_description[61]; char book_categories[9]; int book_code; } my_book_t; // 160000 size, 10 index field slot bin_array_t *all_books = bin_array_create(160000, 10);

Paso 2. Agregar índice

if (bin_add_index(all_books, my_book_t, book_name, __def_cstr_sorted_cmp_func__) && bin_add_index(all_books, my_book_t, book_categories, __def_cstr_sorted_cmp_func__) && bin_add_index(all_books, my_book_t, book_code, __def_int_sorted_cmp_func__) ) {

Paso 3. Inicializó sus datos

my_book_t *bk = malloc(sizeof(my_book_t)); strcpy(bk->book_name, "The Duck Story")); .... ... bin_array_push(all_books, bk );

Paso 4. Resultado de búsqueda eq, lt (menor que), gt (mayor que)

int data_search = 100; bin_array_rs *bk_rs= (my_book_t*) ba_search_eq(all_books, my_book_t, book_code, &data_search); my_book_t **bks = (my_book_t**)bk_rs->ptrs; // Convert to pointer array // Loop it for (i = 0; i < bk_rs->size; i++) { address_t *add = bks[i]; .... }

Paso 5. Búsqueda múltiple y unión interna o unión

// Join Solution bin_array_rs *bk_rs=bin_intersect_rs( bin_intersect_rs(ba_search_gt(...), ba_search_lt(...), true), bin_intersect_rs(ba_search_gt(...), ba_search_lt(....), true), true); // Union Solution bin_array_rs *bk_rs= bin_union_rs( bin_union_rs(ba_search_gt(...), ba_search_lt(...), true), bin_union_rs(ba_search_gt(...), ba_search_lt(....), true), true);

Lea el documento para obtener más detalles sobre cómo buscar y liberar memoria después de la búsqueda.