Autocompletar super rápido usando la búsqueda binaria en el archivo clasificado (300000 líneas)

Lo que buscas se llama TRIE

http://forums.sun.com/thread.jspa?threadID=5295936

En informática, un trie, o árbol de prefijos, es una estructura de datos de árbol ordenada que se utiliza para almacenar una matriz asociativa donde las claves son normalmente cadenas. A diferencia de un árbol de búsqueda binario, ningún nodo del árbol almacena la clave asociada con ese nodo; en cambio, su posición en el árbol muestra qué clave está asociada. Todos los descendientes de un nodo tienen un prefijo común de la cadena asociada con ese nodo, y la raíz está asociada con la cadena vacía. Los valores normalmente no están asociados con cada nodo, solo con hojas y algunos nodos internos que corresponden a las claves de interés.

¿Por qué no utiliza un DB de SQLite en lugar de un archivo de texto?
No creo que puedas hacer nada mejor en cuanto a velocidad que una base de datos portátil en tu situación.

Trie es la respuesta obvia, y ya se ha mencionado, pero además tr13 biblioteca podría ser lo que está viendo. Es un recolector de basura amigable (solo matriz de bytes sin procesar o buffer de bytes), compacto y definitivamente lo suficientemente rápido para su caso. Las claves son típicamente cadenas UTF-8, aunque pueden ser secuencias de bytes. Valores de la misma manera, aunque también hay alternativa para ints de longitud variable (vints) utilizado para obtener muy compacto String-to-int lookups (especialmente para smallish conjunto de ints).

Una estrategia podría ser reducir los resultados utilizando el RandomAccessFile y la búsqueda binaria. Luego, una vez que las entradas posibles sean lo suficientemente pequeñas, cargue esa porción en la memoria y realice una búsqueda en memoria.

Esto mejorará el rendimiento, ya que como tipo de usuario puede buscar rápidamente la misma parte del archivo que ha cargado en la memoria.

mira esto http://es.wikipedia.org/wiki/Binary_search_algorithm

en un archivo ordenado tiene un peor caso de búsqueda binaria de O (log (n)) la siguiente mejor sería una especie de hashmapping que va O (1) aunque esto es complicado para palabras parciales y producirá una enorme tabla de mapeo.

Preprocese sus posibilidades en un árbol de búsqueda con antelación, en lugar de hacerlo en tiempo de ejecución.

Un problema importante con el almacenamiento de una palabra por línea es que no hay acceso aleatorio para líneas en tiempo constante (acceder a la línea X consiste en contar X caracteres de nueva línea desde el principio del archivo) para que su búsqueda binaria sufra.

Lo que usted necesita en esta situación específica (autocompletar) es un Árbol de Prefijo o una variación de él (combinando varios nodos en uno, o transformando subárboles más pequeños que un cierto tamaño en una lista ordenada de palabras).

100ms es mucho tiempo. La mayor preocupación serían las actualizaciones de pantalla, creo.

Si desea evitar una base de datos real, esto es bastante fácil de hacer con un archivo de índice simple, además de su archivo principal.

Podría almacenar los primeros N bytes (4 tal vez?) De la cadena y un desplazamiento de archivo en el archivo principal en un índice cada 32 registros o así, y la búsqueda binaria a través de eso. A continuación, podría buscar de forma lineal hasta 32 registros después de una búsqueda binaria que bastante cerca.

Puede ajustar la frecuencia de índice de 32 registros a lo que tenga sentido dado su longitud de cadena promedio y el tamaño de una sola lectura en su medio. Si tuviera 512 bytes de sistema de archivos y 8 bytes de cadenas medias, entonces haría un índice cada 64 registros, etc. No tiene mucho sentido tener más de un registro de índice por tamaño mínimo de lectura de disco.

El archivo de índice se podría generar fácilmente, y entonces podría administrar el archivo principal con un editor de texto simple.

Sugeriría para ver si usted puede utilizar una biblioteca estándar para este propósito. Tal vez apache lucene se puede utilizar en teléfonos android. Si es así, puede crear un índice (prefijo de palabra -> un id de una palabra en android sql lite). Aquí está una discusión sobre un tipo de algoritmo que lucene está usando .

Hilo antiguo, pero ESTO ES LO QUE NECESITA: Stringsearch library

Lo usé para mi aplicación 'Wordlist Pro' para Android y es muy rápido.

También podría hacer algo como esto (abajo es un archivo preprocesado):

 aa - line 1 ab - line 17 . . zz - line 299819 

Si el usuario ingresa algo que comienza con aa, yo leería las líneas 1 a 17 y buscaría secuencialmente en ellas