¿Cómo encontrar una palabra en la lista de palabras grande (vocabulario) con el consumo de memoria de descenso y el tiempo de búsqueda?

Problema

[A continuación se muestra una descripción de lo que la aplicación debe hacer en virtud de lo que restringe ]

Quiero una estructura de datos que busque si una string existe en una lista de 250.000 palabras, mientras que utiliza sólo una cantidad justa de RAM y mantener el tiempo que se tarda en cargar esta estructura de datos en RAM pequeño (digamos 0-8 segundos) . El tiempo que se tarda en encontrar una palabra también debe ser rápido (digamos de 0 a 0,5 segundos), pero el uso del carnero es más importante. También debería ser posible crear varios juegos (más sobre lo que este juego se trata en el título "uso") sin necesidad de más memoria significativa.

También sería muy valioso saber qué palabras comienzan con una string , pero no lo suficiente para sacrificar el tiempo de carga en muchos segundos.


Utilizar

Es para un juego Android sin conexión. Limitada ram está disponible. La cantidad máxima de RAM que una Aplicación puede usar de acuerdo a esta entrada es entre 16-32mb RAM dependiendo del dispositivo. Mi aplicación vacía de Android ya utiliza cerca de 17 MB (utilizando el Monitor de memoria en Android Studio). Mi dispositivo android tapa el uso de RAM en 26mb, dejándome a unos 8mb de espacio libre para toda mi Activity .


Opciones que he intentado

Todos parecen condenados de diferentes maneras.

  1. Hashmap : lee todas las palabras en un objeto hash-map.

    1.1 inicializar velocidad: lento para leer cada palabra en el Hash-mapa con 23 segundos.

    1.2 uso de ram: utiliza cantidad significativa de RAM, aunque se me olvidó cuánto exactamente.

    1.3 velocidad de búsqueda: Encontrar si una palabra existió en la lista fue rápida, por supuesto.

    1.4 reducir las posibles palabras (opcional): lento, necesita pasar por todo el hash-map y borrar uno por uno. También porque está usando la eliminación, los juegos múltiples no podrán ser jugados usando la misma instancia del hash-mapa. Demasiada memoria se tomaría al agregar más juegos, por lo que la reducción de las posibles palabras para ello imposible.

  2. Trie – Implementar un RadixTree & Puedes ver mi implementación aquí.

    2.1 inicializar velocidad: lento para leer cada palabra en el RadixTree con 47 segundos.

    2.2 uso de ram: utiliza cantidad significativa de RAM, tanto que Android está suspendiendo hilos un par de veces.

    2.3 Velocidad de búsqueda: Buscar si una palabra existió en la lista era rápida.

    2.4 Reducción de palabras posibles (opcional): Ultra rápido ya que sólo se necesita una referencia a un nodo en el árbol para encontrar todas las palabras posibles como sus hijos. Usted puede jugar un montón de juegos con la reducción de las posibles palabras, ya que un juego extra requiere sólo una referencia a un nodo en el árbol!

  3. Scanner – Repasa secuencialmente el archivo de palabras

    3.1 inicializar velocidad: ninguno.

    3.2 uso de ram: ninguno.

    3.3 velocidad de búsqueda: unos 20 segundos.

    3.4 reducir las posibles palabras (opcional): no se puede hacer de manera realista.

Código simple:

 String word; String wordToFind = "example"; boolean foundWord = false; while (wordFile.hasNextLine()) { word = wordFile.nextLine(); if(word.equals(wordToFind)) { foundWord = true; break; } } test.close(); 

Opciones que pensé:

  1. Long-binary-search-tree: Convertir la lista de palabras en una lista de s long , luego leerlas y hacer una búsqueda binaria en ellas.

    1.1 inicializar velocidad: probablemente el mismo que un hash-mapa o poco menos con unos 20 segundos. Sin embargo, espero que llamar a Array.sort () no toma demasiado tiempo, ninguna idea hasta el momento.

    1.2 uso de ram: si solo cuentas 12 letras o menos con un alfabeto de 26 letras necesitas 5 bits (2 ^ 5 = 32) para codificar una cadena. Una matriz de largos necesitaría entonces 250,000 * 8 bits = alrededor de 2mb. Que no es demasiado.

    1.3 velocidad de búsqueda: Arrays.binarySearch ()

    1.4 reducir las palabras posibles (opcional): Es posible reducir las palabras posibles, pero no estoy seguro de cómo hacerlo. De acuerdo con un comentario sobre este post .

  2. Hashmap con almacenamiento : crea una función de hash que asigna una palabra a un número de índice del archivo de lista de palabras. A continuación, acceder al archivo en esta ubicación específica y mirar desde aquí para encontrar si existe una palabra. Puede hacer uso del orden del alfabeto para determinar si todavía puede encontrar la palabra ya que la lista de palabras está en orden natural.

    2.1 inicializar la velocidad: no es necesario (ya que tengo que poner cada palabra en el índice de la derecha de antemano.)

    2.2 uso de ram: ninguno.

    2.3 velocidad de búsqueda: rápido.

    2.4 reducir las posibles palabras (opcional): no es posible.


Preguntas específicas que tengo

  1. ¿Son las opciones que he pensado en las opciones de "Opciones que he pensado en" opciones viables o hay cosas que me perdí aún que les haría imposible implementar?
  2. ¿Hay opciones que no he pensado que son mejores / iguales en el rendimiento?

Comentarios finales

He estado atrapado en esto durante aproximadamente una semana ahora. Así que cualquier nueva idea es más que bienvenida. Si alguno de mis supuestos anteriores son incorrectos, también me complacería oír hablar de ellos.

Hice este post de esta manera para que otros puedan aprender de ellos también, ya sea viendo mis errores o viendo lo que funciona en las respuestas.

Esto suena como un uso ideal para un filtro de flor . Si está dispuesto a permitir que el riesgo de que algo sea falsamente considerado una palabra, puede condensar su lista de palabras en una cantidad de memoria tan pequeña o tan grande como usted está dispuesto a hacerlo.

Tuve este mismo problema y terminó yendo con un "en-disco" trie. Es decir, codifico la estructura de datos en un solo archivo usando desplazamientos de bytes en lugar de punteros (empacando los nodos en orden inverso, siendo el nodo "root" el último escrito).

Es rápido de cargar simplemente leyendo el archivo en una matriz de bytes, con trie traversal usando valores de desplazamiento de la misma manera que los punteros.

Mi conjunto de palabras 200K se ajusta en 1.7 MB (sin comprimir) con un valor de 4 bytes en cada nodo de terminación de palabra.

  • Android: ¿cuáles son las diferencias entre el montón de poca profundidad y el de retención
  • Cómo tomar instantánea de montón de Xamarin.Android's Mono VM?
  • Medición del rendimiento en Android
  • Vaciado de memoria en el ejemplo práctico
  • Fuga de memoria, Spring para Android
  • ¿Por qué Android 4.0 / Ice Cream Sandwich asigna tanta memoria heap?
  • ¿Hay una manera de compactar memoria en android para bajar la marca de agua alta?
  • Rendimiento de la clase de la clase estática vs no estática de la clase estática de Android
  • Android - BitmapFactory.decodeByteArray - OutOfMemoryError (OOM)
  • Xamarin pérdida de memoria Android con actividad simple
  • Java.lang.OutOfMemoryError: tamaño de mapa de bits supera el presupuesto de VM - Android
  • FlipAndroid es un fan de Google para Android, Todo sobre Android Phones, Android Wear, Android Dev y Aplicaciones para Android Aplicaciones.