Tengo una lista de cientos de cadenas únicas en C++, necesito verificar si existe un valor en esta lista, pero preferiblemente rápido como un rayo.Búsqueda rápida a través de una lista ordenada de cadenas en C++
estoy usando un currenly hash_set con std :: cuerdas (ya que no pude conseguir que funcione con const char *) de esta manera:
stdext::hash_set<const std::string> _items;
_items.insert("LONG_NAME_A_WITH_SOMETHING");
_items.insert("LONG_NAME_A_WITH_SOMETHING_ELSE");
_items.insert("SHORTER_NAME");
_items.insert("SHORTER_NAME_SPECIAL");
stdext::hash_set<const std::string>::const_iterator it = _items.find("SHORTER_NAME"));
if(it != _items.end()) {
std::cout << "item exists" << std::endl;
}
¿Alguien más tiene una buena idea para una búsqueda más rápida método sin construir una tabla hash completa?
La lista es una lista fija de cadenas que no cambiará. Contiene una lista de nombres de elementos que se ven afectados por un determinado error y deben repararse sobre la marcha cuando se abre con una versión más nueva.
He creado hashtables antes de usar Aho-Corasick, pero no estoy dispuesto a agregar demasiada complejidad.
Me sorprendió el número de respuestas. Terminé probando algunos métodos para su rendimiento y terminé usando una combinación de respuestas de Kirkus y Rob K. Intenté una búsqueda binaria antes, pero creo que tuve un pequeño error al implementarla (qué tan difícil puede ser ...).
Los resultados fueron impactantes ... Pensé que tenía una implementación rápida usando un hash_set ... bueno, al final no lo hice. He aquí algunas estadísticas (y el código eventual):
de búsqueda aleatoria de 5 llaves existentes y 1 llave inexistente, 50.000 veces
Mi algoritmo original tuvo un promedio de 18,62 segundo
Una búsqueda de lineair tomó en promedio 2,49 segundos
Una búsqueda binaria tomó en promedio 0,92 segundos.
Una búsqueda utilizando una tabla hash perfecta generada por gperf tomó en promedio 0,51 segundos.
Aquí está el código que uso ahora:
bool searchWithBinaryLookup(const std::string& strKey) {
static const char arrItems[][NUM_ITEMS] = { /* list of items */ };
/* Binary lookup */
int low, mid, high;
low = 0;
high = NUM_ITEMS;
while(low < high) {
mid = (low + high)/2;
if(arrAffectedSymbols[mid] > strKey) {
high = mid - 1;
}
else if(arrAffectedSymbols[mid] < strKey) {
low = mid + 1;
}
else {
return true;
}
}
return false;
}
NOTA: Este es Microsoft VC++, así que no estoy usando el std :: hash_set de SGI.
Hice algunas pruebas esta mañana usando gperf como VardhanDotNet sugerido y esto es un poco más rápido de hecho.
Hmm ... Supongo que mi implementación actual es lo suficientemente rápida pero, sin embargo, probaré a gperf solo por la experiencia y el material de comparación. – Huppie