0
174
VisualizaçõesBusque alfabetos en una matriz de cadenas de manera eficiente usando javascript
Tengo una variedad de productos como se muestra a continuación.
const totalProducts = ['washing machine', 'sewing machine', 'refrigerator', 'desk'] Si un usuario escribe cualquier palabra en el campo de entrada, quiero obtener todos los productos coincidentes de la matriz. por ejemplo, si el usuario escribe 'ma', esperaría que el resultado contuviera ['washing machine', 'sewing machine']
Para lograr el resultado deseado, hago este código a continuación
var result = totalProducts.filter((product) => product.includes('ma'));Sé que este código anterior funciona para obtener el resultado deseado. pero supongamos que la matriz totalProducts tiene una longitud de más de 1000. ¿Mi método anterior dará el resultado de manera eficiente como debería?
¿O hay una mejor manera de buscar y mejorar el rendimiento de mi código?
3 Respostas
Responde à pergunta0
Dado que .filter() e .includes() son ambos de tiempo constante (o(n)), la complejidad de tiempo total es O(2n).
La única forma que se me ocurre para mejorar el rendimiento del código sería almacenar en caché (o almacenar) la matriz de resultados filtrados y luego filtrar aún más esa matriz a menos que el usuario retroceda.
0
a veces, cuando sus datos son demasiado grandes, se quedan sin posibilidades de obtener métodos más eficientes, lo que sugiero es filtrar sus datos en su backend y agregar una rueda como retroalimentación visual para el usuario. también se debe usar el rebote de su oyente onKeyDown para evitar inundar su servidor con solicitudes http para cada pulsación de tecla.
0
Es un intercambio entre el espacio y el tiempo. De hecho, existe un enfoque más rápido, pero la matriz debe procesarse de antemano para crear un índice, que ocupa memoria. Si crea un árbol de sufijos con un índice de cada cadena en una hoja, simplemente puede encontrar el subárbol apropiado y enumerar todos los índices que contiene.
Permítanme usar un ejemplo más pequeño, por el tamaño de esta respuesta. Supongamos que tiene "pit,spit,pot,spot". Un árbol de sufijos de esas cadenas es
(Gracias a este sitio por la visualización). Si desea encontrar las cadenas que contienen "po", comenzando desde la raíz, tome el nodo "p", luego el nodo "o" (aquí colapsado en "ot$" nodo). El subárbol debajo contiene enlaces a las cadenas #3 y #4 (este sitio las indexa desde 1), es decir, "pot" y "spot". (Este sitio también señala que la subcadena comienza en la posición 1 para "pot" y en la posición 2 para "spot", pero esta información no es necesaria para su propósito).
Como puede ver, el proceso de encontrar las cadenas coincidentes es muy rápido; pero el árbol de sufijos requerido sería mucho más grande que la lista original. Si desea restringir la búsqueda para que solo coincida con el inicio de las palabras (por ejemplo, "ma" coincidiría con "lavadora", pero no con "chi"), puede reducir el tamaño del árbol.
Sin embargo, las ganancias serían, para la mayoría de los propósitos, insignificantes para una sola búsqueda; esto probablemente solo sea necesario si necesita realizar la búsqueda repetidamente, rápido. Para una matriz de miles de elementos y una sola búsqueda de vez en cuando, su enfoque original es casi seguro lo suficientemente bueno. El enfoque del árbol de sufijos es más rápido, pero para el caso de uso en el OP, una exageración y un caso de optimización prematura.