tag - C++: ¿Contenedor eficiente para grandes cantidades de datos de búsqueda?

qué es un fragmento de contenedor en tag manager

Question

Estoy implementando una versión basada en texto de Scrabble para un proyecto universitario.

Mi diccionario es bastante grande, con un peso aproximado de 400.000 palabras ( std::string ).

La búsqueda de una palabra válida apestará, a lo grande, en términos de eficiencia si busco un vector<string> (O (n)). ¿Hay buenas alternativas? Tenga en cuenta, estoy inscrito en el primer año. ¡Nada DEMASIADO complejo!

¡Gracias por tu tiempo!

Francisco

Answer 1

¿Cuál es el propósito de su estructura de datos? ¿Qué tipo de cosas quieres hacer con eso?

• ¿Comprobar si una palabra completa como "tempestad" está en la lista?
• ¿Encontrar todas las palabras de siete letras que comienzan y terminan con "t"?
• ¿Encontrar todas las palabras de siete letras que comienzan y terminan con "t" que se pueden hacer con un conjunto dado de letras?

La primera pregunta es todo lo que necesita si está implementando algún tipo de árbitro para un grupo de jugadores humanos, es decir, alguna entidad para verificar las palabras propuestas contra el diccionario oficial. Las estructuras de datos básicas como std::map , std::set , std::vector , ya sugeridas por otros, son suficientes para este propósito.

La segunda y tercera pregunta son las que necesita respuesta si está escribiendo un jugador. Aquí es posible que desee considerar 26 conjuntos para cada posición de letra, cada conjunto contiene las palabras con una letra dada en una posición determinada. Necesitará un código adicional para calcular las intersecciones cuando sea necesario, y tal vez comparar las palabras con las letras disponibles en su estante.

Actualización : en un comentario sobre la pregunta original, el OP dejó en claro que solo tiene que verificar si hay una palabra en el diccionario. Esta es la primera pregunta que formulé anteriormente, y cualquiera de las estructuras de datos eficientes estándar está bien.

Answer 2

Hice algunos perfiles y obtuve los siguientes resultados (MSVS 2008, / O2, versión de lanzamiento, lanzamiento de .exe por separado).

EDITAR - Ahora me doy cuenta de que, de hecho, me arreglé mi primera prueba, porque no dividí la prueba de construcción y búsqueda. Aunque no cambió a los "ganadores", hice algunas pruebas nuevas. Entonces, aquí están los resultados cuando los dividimos.

Primero, si casi no hay solicitudes de búsqueda incorrectas (4 millones de buenos intentos de búsqueda) .

[ RUN      ] Containers.DictionaryPrepare
[       OK ] Containers.DictionaryPrepare (234 ms)
[ RUN      ] Containers.VectorPrepare
[       OK ] Containers.VectorPrepare (704 ms)
[ RUN      ] Containers.SetPrepare
[       OK ] Containers.SetPrepare (593 ms)
[ RUN      ] Containers.MultisetPrepare
[       OK ] Containers.MultisetPrepare (578 ms)
[ RUN      ] Containers.UnorderedSetPrepare
[       OK ] Containers.UnorderedSetPrepare (266 ms)
[ RUN      ] Containers.UnorderedMultisetPrepare
[       OK ] Containers.UnorderedMultisetPrepare (375 ms)
[ RUN      ] Containers.VectorSearch
[       OK ] Containers.VectorSearch (4484 ms)
[ RUN      ] Containers.SetSearch
[       OK ] Containers.SetSearch (5469 ms)
[ RUN      ] Containers.MultisetSearch
[       OK ] Containers.MultisetSearch (5485 ms)
[ RUN      ] Containers.UnorderedSet
[       OK ] Containers.UnorderedSet (1078 ms)
[ RUN      ] Containers.UnorderedMultiset
[       OK ] Containers.UnorderedMultiset (1250 ms)
[----------] 11 tests from Containers (20516 ms total)

Este perfil muestra que debe usar variaciones de contenedor "normales" en lugar de "multi", y debe elegir unordered_set . Es genial para construir tiempo y tiempo de operaciones de búsqueda.

Aquí están los resultados para otro caso (supongo que no se trata de su aplicación, sino solo para que lo sea), cuando la cantidad de búsquedas incorrectas es igual a la cantidad de búsquedas buenas (y es igual a 2 millones) . El ganador sigue siendo el mismo.

También tenga en cuenta que, para el diccionario de diccionarios estáticos, el rendimiento es mejor (aunque necesita más tiempo para la inicialización), que el set , pero bueno, será un problema si tiene que agregar elementos.

[ RUN      ] Containers.DictionaryPrepare
[       OK ] Containers.DictionaryPrepare (235 ms)
[ RUN      ] Containers.VectorPrepare
[       OK ] Containers.VectorPrepare (718 ms)
[ RUN      ] Containers.SetPrepare
[       OK ] Containers.SetPrepare (578 ms)
[ RUN      ] Containers.MultisetPrepare
[       OK ] Containers.MultisetPrepare (579 ms)
[ RUN      ] Containers.UnorderedSetPrepare
[       OK ] Containers.UnorderedSetPrepare (265 ms)
[ RUN      ] Containers.UnorderedMultisetPrepare
[       OK ] Containers.UnorderedMultisetPrepare (375 ms)
[ RUN      ] Containers.VectorSearch
[       OK ] Containers.VectorSearch (3375 ms)
[ RUN      ] Containers.SetSearch
[       OK ] Containers.SetSearch (3656 ms)
[ RUN      ] Containers.MultisetSearch
[       OK ] Containers.MultisetSearch (3766 ms)
[ RUN      ] Containers.UnorderedSet
[       OK ] Containers.UnorderedSet (875 ms)
[ RUN      ] Containers.UnorderedMultiset
[       OK ] Containers.UnorderedMultiset (1016 ms)
[----------] 11 tests from Containers (15438 ms total)

Código de prueba:

TEST(Containers, DictionaryPrepare) {
   EXPECT_FALSE(strings_initialized);
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      strings.push_back(generate_string());
   }
}

TEST(Containers, VectorPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      vec.push_back(strings[i]);
   }
   sort(vec.begin(), vec.end());
}

TEST(Containers, SetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      set.insert(strings[i]);
   }
}

TEST(Containers, MultisetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      multiset.insert(strings[i]);
   }
}

TEST(Containers, UnorderedSetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      uo_set.insert(strings[i]);
   }
}

TEST(Containers, UnorderedMultisetPrepare) {
   for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) {
      uo_multiset.insert(strings[i]);
   }
}

TEST(Containers, VectorSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      std::binary_search(vec.begin(), vec.end(), strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      std::binary_search(vec.begin(), vec.end(), NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, SetSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      set.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      set.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, MultisetSearch) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      multiset.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      multiset.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, UnorderedSet) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      uo_set.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      uo_set.find(NONEXISTENT_ELEMENT);
   }
}

TEST(Containers, UnorderedMultiset) {
   for (size_t i = 0; i < TOTAL_SEARCHES; ++i) {
      uo_multiset.find(strings[rand() % TOTAL_ELEMENTS]);
   }
   for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) {
      uo_multiset.find(NONEXISTENT_ELEMENT);
   }
}

Answer 3

Me gustaría repetir la sugerencia de Ken de usar un Trie, y además sugerir que podría reducir drásticamente el tamaño del trie al permitir que se asemejara más a una máquina de estados finitos para prefijos y sufijos comunes. Por ejemplo
"nación",
"nacional",
"nacionalizar",
"nacionalización",
"nacionalizar",
"desnacionalizar",
Podrían todos compartir una estructura común. Tendrías que preocuparte por palabras dudosas, como
"nacionalizacionalización"
Utilicé esto hace años en un programa de corrección de ortografía.

Answer 4

Si el vector está ordenado, puede usar binary_search para probar si una palabra dada existe en el diccionario.

Answer 5

Si quisiera buscar algo que esté en la biblioteca estándar, podría usar std::set con la palabra como la clave. Eso te daría tiempo de búsqueda logarítmica.

Como su diccionario es presumiblemente estático (es decir, creado una vez y no modificado), también puede usar un std::vector , clasificarlo usando std::sort y luego usar std::binary_search en el vector ordenado para encontrar una palabra. Esto también daría tiempo de búsqueda logarítmica, y posiblemente sería más eficiente en espacio que un set .

Si desea implementar su propia estructura de datos, un trie sería una buena opción.

Answer 6

Sugiero usar la longitud de la palabra y las primeras letras como los dos primeros elementos de la búsqueda. Deje que los datos se organicen para soportar este algoritmo.

Primero, definamos un contenedor para todas las palabras que tienen la misma longitud:

typedef std::vector<std::string> Word_Container;

Esta estructura de datos se ordenará de modo que se pueda utilizar una búsqueda binaria.

A continuación, se creará una tabla de índice. La tabla de índice tendrá la forma < longitud de palabra, puntero al contenedor de palabra >:

typedef std::map<unsigned int, Word_Container *> Index_Table;

Y, finalmente, tener una matriz de tablas de índice, utilizando la primera letra de la palabra como índice:

Index_Table alpha_array[26]; // ASCII A - Z.

El algoritmo es entonces:
Calcular índice en alpha_array :
index = word[0] - ''A'';

Use el índice para obtener la tabla de índice asociada:
Index_Table& table = alpha_array[index];

Use la longitud de la palabra como la clave para la búsqueda en la tabla, para obtener el contenedor de palabras:
Word_Container * p_word_container = table[word.length()];

Contenedor de búsqueda para la palabra exacta:

bool found = false;
if (p_word_container)
{
    found = std::binary_search(p_word_container->begin(), p_word_container->end(), word);
}

Existen métodos más eficientes, pero complejos, para buscar una palabra en un diccionario. El algoritmo anterior tiene el beneficio de un rápido "escape" puntos donde la palabra no existe. Este concepto puede extenderse a las tablas de base de datos.

Answer 7

Un árbol en.wikipedia.org/wiki/Trie o radix le daría tiempos de búsqueda y tiempos de inserción que son lineales en la longitud de la cadena que está buscando.

(Tenga en cuenta que lo mejor que puede hacer con cualquier algoritmo de búsqueda es lineal en la longitud de la cadena que está buscando, porque la comparación de cadenas de hashing es lineal en la longitud de la cadena; por lo tanto, el componente del tiempo de ejecución es lineal en la la longitud de la cadena generalmente se deja fuera de los tiempos de ejecución para búsqueda binaria, árboles binarios o búsqueda lineal.)

Estas soluciones probablemente sean excesivas si aún no las tiene en su biblioteca.

Answer 8

Use un std::tr1::unordered_set , y eso le da una búsqueda constante de tiempo. (Lineal en la longitud de la cadena, según mi otra respuesta.)

Answer 9

std :: set es natural para esto porque requiere casi 0 trabajos además de usar un vector. Aun así, te enseñaré algo que normalmente no aprendes hasta que eres un profesional. No optimizado prematuramente. Apuesto a una computadora moderna que una búsqueda de diccionario lineal en un vector de cadena de 40K toma .001 segundos.

En un conjunto, es O (log n) y probablemente toma .00001 segundos.

Cualquier cosa que no esté en el STL es una pérdida total de tiempo. No gaste $ 10 de trabajo en un problema de 10 centavos.