contenedor para la búsqueda rápida de nombres

Question

Quiero almacenar cadenas y emitir cada una con un número de identificación único (un índice estaría bien). Solo necesitaría una copia de cada cadena y necesito una búsqueda rápida. Compruebo si la cadena existe en la tabla con la suficiente frecuencia que noto un golpe de rendimiento. ¿Cuál es el mejor contenedor para usar para esto y cómo busco si la cadena existe?

Answer 1

Sugeriría tr1 :: unordered_map. Se implementa como un hashmap por lo que tiene una complejidad esperada de O (1) para las búsquedas y el peor caso de O (n). También hay una implementación de impulso si su compilador no es compatible con tr1.

#include <string> 
#include <iostream> 
#include <tr1/unordered_map> 

using namespace std; 

int main() 
{ 
    tr1::unordered_map<string, int> table; 

    table["One"] = 1; 
    table["Two"] = 2; 

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0; 
} 

Answer 2

suena como una matriz funcionaría muy bien donde el índice es el índice en la matriz. Para verificar si existe, solo asegúrese de que el índice esté dentro de los límites de la matriz y que su entrada no sea NULA.

EDITAR: si ordena la lista, siempre puede utilizar una búsqueda binaria que debe tener una búsqueda rápida.

EDIT: Además, si desea buscar una cadena, siempre se puede utilizar un std::map<std::string, int> también. Esto debería tener algunas velocidades de búsqueda decentes.

Answer 3

Pruebe std :: map.

Answer 4

¿Las cadenas para buscar se encuentran disponibles estáticamente? Es posible que desee mirar a un perfect hashing function

Answer 5

más sencilla es utilizar std :: mapa.

funciona así:

#include <map> 
using namespace std; 

... 

    map<string, int> myContainer; 
    myContainer["foo"] = 5; // map string "foo" to id 5 
    // Now check if "foo" has been added to the container: 
    if (myContainer.find("foo") != myContainer.end()) 
    { 
     // Yes! 
     cout << "The ID of foo is " << myContainer["foo"]; 
    } 
    // Let's get "foo" out of it 
    myContainer.erase("foo") 

Answer 6

En primer lugar que debe ser capaz de cuantificar sus opciones. También nos ha informado que el patrón de uso principal que le interesa es búsqueda, no la inserción.

Let N sea el número de cadenas que se espera que se tenga en la tabla, y dejar C ser el número medio de caracteres en cualquier cadena dada presentes en dicha tabla (o en las cadenas que se compara con la mesa).

1. En el caso de un enfoque basado en hash, para cada búsqueda que paga los costes siguientes:

   • O(C) - calcular el hash de la cadena que está a punto de mirar hacia arriba
   • entre O(1 x C) y O(N x C), donde 1..N es el costo que espera al atravesar el depósito basado en la clave hash, aquí multiplicado por C para volver a verificar los caracteres en cada cadena en contra de la búsqueda de claves
   • tiempo total: entre O(2 x C) y O((N + 1) x C)

2. En el caso de un enfoque basado enstd::map (que utiliza árboles rojo-negro), para cada búsqueda que paga la costes siguientes:

   • tiempo total: entre O(1 x C) y O(log(N) x C) - donde O(log(N)) es el coste máximo recorrido del árbol, y O(C) es el tiempo que 0 genérica less<> aplicación's se necesita para volver a comprobar su clave de búsqueda durante el recorrido del árbol

En el caso de los grandes valores de N y en ausencia de una función hash que garantiza menos de log (n) las colisiones, o si solo quiere ir a lo seguro, , es mejor utilizar un enfoque basado en árbol (std::map). Si N es pequeño, por todos los medios, utilizar un enfoque basado en hash (. Al mismo tiempo asegurándose de que la colisión de hash es baja)

Antes de tomar cualquier decisión, sin embargo, también se debe verificar:

• http://meshula.net/wordpress/?p=183
• http://wyw.dcweb.cn/mstring.htm

Answer 7

Google sparse hash quizá

Answer 8

probar esto:

alt text http://adrinael.net/containerchoice.png