optimizar la búsqueda a través de una gran matriz js string?

Question

si tengo una gran matriz de cadenas de JavaScript que tiene más de 10 000 elementos, ¿cómo puedo buscar rápidamente a través de ella?

Ahora mismo tengo una matriz de cadenas javascript que almacena la descripción de un trabajo, y yo "M que permite al usuario filtro dinámico de la lista devuelta a medida que escribe en un cuadro de entrada.

Así que decir que tengo una matriz de cadenas de este modo:
var descArr = {"flipping burgers", "pumping gas", "delivering mail"};

y el usuario desea buscar:? "p"

¿Cómo voy a ser capaz de buscar una matriz de cadenas que tiene 10000 + descripciones en ella rápidamente Obviamente, no puedo ordenar la matriz de descripción ya que son descripciones, por lo que la búsqueda binaria está desactivada. Y dado que el usuario puede buscar por "p" o "pi" o cualquier combinación de letras, esta búsqueda parcial significa que no puedo usar matrices asociativas (es decir, searchDescArray["pumping gas"]) para acelerar la búsqueda.

¿Alguna idea a alguien?

Answer 1

Como los motores de expresiones regulares en los navegadores actuales están volviendo loco en términos de velocidad, ¿qué hay de hacerlo de esa manera? En lugar de una matriz, pase una cuerda gigante y separe las palabras con un identificador. Ejemplo:

• cadena "flipping burgers""pumping gas""delivering mail"
• Regex: "([^"]*ping[^"]*)"

Con el interruptor /g para el mundial de obtener todos los partidos. Asegúrese de que el usuario no busque su separador de cadenas.

Usted puede incluso agregar un id en la cadena con algo como:

• cadena "11 flipping burgers""12 pumping gas""13 delivering mail"

• Regex: "(\d+) ([^"]*ping[^"]*)"

• Ejemplo: http://jsfiddle.net/RnabN/4/ (30,000 cuerdas, límite de los resultados a 100)

Answer 2

Puede que esta no sea una respuesta para usted, ya que estoy haciendo algunas suposiciones sobre su configuración, pero si tiene un código del lado del servidor y una base de datos, sería mucho mejor hacer una llamada AJAX para obtener el reduzca la lista de resultados y use una base de datos para filtrar (ya que son muy buenos en este tipo de cosas).

Además del beneficio de la base de datos, también se beneficiaría al no generar tantos datos (10000 variables) en un front-end basado en web; si solo devuelve los que necesita, entonces ahorrará un poco de ancho de banda

Answer 3

Sugiero probar una función JS preparada, por ejemplo, el autocomplete de jQuery. Es rápido y tiene muchas opciones para configurar.

Mira la jQuery autocomplete demo

Answer 4

No hay forma de acelerar un n inicial búsqueda en matriz sin realizar algunos cambios. Puede acelerar las búsquedas consecutivas almacenando los resultados en caché y asignándolos dinámicamente a patrones.

1.) Ajuste su formato de datos. Esto hace que las búsquedas iniciales sean algo más rápidas. Básicamente, precache.

var data = { 
    a : ['Ant farm', 'Ant massage parlor'], 
    b : ['Bat farm', 'Bat massage parlor'] 
    // etc 
} 

2.) Configurar la mecánica de la memoria caché.

var searchFor = function(str, list, caseSensitive, reduce){ 
    str = str.replace(/(?:^\s*|\s*$)/g, ''); // trim whitespace 
    var found = []; 
    var reg = new RegExp('^\\s?'+str, 'g' + caseSensitive ? '':'i'); 
    var i = list.length; 
    while(i--){ 
     if(reg.test(list[i])) found.push(list[i]); 
     reduce && list.splice(i, 1); 
    } 
} 

var lookUp = function(str, caseSensitive){ 
    str = str.replace(/(?:^\s*|\s*$)/g, ''); // trim whitespace 
    if(data[str]) return cache[str]; 
    var firstChar = caseSensitive ? str[0] : str[0].toLowerCase(); 
    var list = data[firstChar]; 
    if(!list) return (data[str] = []); 
    // we cache on data since it's already a caching object. 
    return (data[str] = searchFor(str, list, caseSensitive)); 
} 

3.) Utilice la siguiente secuencia de comandos para crear un objeto precaché. Te sugiero que lo ejecutes una vez y uses JSON.stringify para crear un objeto de caché estático. (O hacerlo en el backend)

// we need lookUp function from above, this might take a while 
var preCache = function(arr){ 
    var chars = "abcdefghijklmnopqrstuvwxyz".split(''); 
    var cache = {}; 
    var i = chars.length; 
    while(i--){ 
     // reduce is true, so we're destroying the original list here. 
     cache[chars[i]] = searchFor(chars[i], arr, false, true); 
    } 
    return cache; 
} 

Probablemente un poco más código, entonces lo esperado, pero optimización de su rendimiento y no viene de forma gratuita.

Answer 5

No puedo reproducir el problema, he creado una implementación ingenua, y la mayoría de los navegadores realizan la búsqueda entre 10000 15 cadenas de caracteres en un solo dígito de milisegundos. No puedo probar en IE6, pero no lo creo más de 100 veces más lento que los navegadores más rápidos, que aún serían prácticamente instantáneos.

Inténtelo usted mismo: http://ebusiness.hopto.org/test/stacktest8.htm (Tenga en cuenta que el tiempo de la creación no es relevante para el tema, que está ahí sólo para obtener algunos datos para trabajar.)

Una cosa que podría hacer el mal está tratando de hacer que todo resultados, eso sería un trabajo enorme cuando el usuario solo ingresó una sola letra o una combinación de letras común.