Tengo un código para realizar búsquedas de ficheros a partir de un directorio dado, y busco alguna idea para mejorar la velocidad del algoritmo. El código es java, aunque da igual el lenguaje en que me den la idea (si es que alguno me facilita el código)

Básicamente, lo que se hace es, para un directorio, listar todos los archivos (una función del api de java lo hace), y recorrer esa lista filtrando esos archivos: si es uno de los que buscamos, lo añadimos al resultado; si es un directorio realizamos la misma operación (listar y filtrar).

El algoritmo está basado en hilos, de forma que el listado recursivo lo realizan varios hilos de la siguiente forma: partiendo del hilo inicial creado, la tarea que realiza es listar el directorio y filtrar el contenido, teniendo en cuenta que si se encuentra un directorio, el hilo crea un nuevo hilo que realiza la misma tarea.

Ya de por sí, esto plantea ciertos problemas, como la posible explosión de hilos que puede haber, con la consiguiente ralentización del sistema (alguna prueba muy bruta he hecho, y creedme que llegué a pensar que se paraba la máquina).
Supongo que no habrá otra cosa que limitar de alguna forma el número máximo de hilos que se pueden estar ejecutando a la vez, cosa que creo que no plantea un problema dado que no hay hilos que esperen a que acabe algún otro hilo. Supongo que habrá que reducir la velocidad (todos los hilos deberán comprobar el número de hilos que se están ejecutando antes de lanzar otro)

De todas formas, me tocará modificar el algoritmo para evitar posibles bloqueos. (si está limitado a 5 hilos, y hay 5 hilos esperando crear otro hilo.... FAIL!)

A ver si a alguien se le ocurre alguna maravillosa idea...

No creo que sea lo que buscas pero la nueva versión (1.7) de java creo que va a permitir hacer eso facilmente

http://java.sun.com/docs/books/tutorial ... /walk.html

Podría ser interesante comparar el método que tengo implementado actualmente con ese.
Supongo que cuando saquen la nueva versión acabaré por hacer una solución de compromiso si es que mi rendimiento es sensiblemente peor, que será detectar la versión de java instalada, y emplear uno u otro algoritmo dependiendo de la versión.

A falta de hacer unas pruebas más duras con mi algoritmo (que espero que no explote algo), por el momento me quedo con el mio.

Gracias por la información, lo probaré.

Saludos Akodo.

Pues lo que se me ocurre que pudieras hacer es lo siguiente:

Si tienes una carpeta de inicio, pudieras considerar que es la raiz de un arbol, y cada carpeta que contiene, una rama a comprobar, algo asi:



Cada letra de es un directorio. Si haces un "barrido vertical", iniciarias con la D de hasta arriba, luego checarias la D del segundo nivel, la de la izquierda, luego con la D del tercel nivel, la de hasta la izquierda, luego te regresarias a la primera D del segundo nivel y brincarias a la segunda D del tercer nivel, te regresarias a la primera D del segundo nivel y luego volverias a la primera D del nivel 1, luego inciarias en la segunda D del segundo nivel y de hay brincas a la tercera D del tercer nivel, te devuelves a la segunda D del segundo nivel y brincas a la cuarta D del tercer nivel.

Esto no es precisamente muy eficiente.

Lo que se me ocurre hacer es que realices una búsqueda por niveles. ¿Como?



Asi, por ejemplo, vas analizando por niveles, es mas o menos igual de rápido que la búsqueda vertical, pero al menos es mas pareja y como detenerte? Cuando al llegar a el paso 1 la cola este vacía.

Más o menos eso es lo que estoy haciendo, aunque utilizando varios hilos.
El hilo "padre" por llamarlo de algún modo, realiza una búsqueda por nivel, de forma que si encuentra un directorio se lo encarga a un "hijo" que busque en ese directorio de esa misma forma, con lo que el padre sigue buscando en ese mismo nivel.

Tal como lo tengo implementado, el planteamiento es similar al tuyo, con la salvedad de que, en lugar de tener una cola explícita de directorios, la cola es implícita al tener hilos esperando su ejecución.

De todas formas, también me he dado cuenta de cierta problemática con los "softlinks" (lo que viene a ser un "ln -s"). El caso es que, no me pregunten por qué, ni cómo, pero resulta que en un directorio tengo un bucle. Para ser más concretos:
dir1
|------ enlace a dir
Para que quede más concreto, tengo un enlace apuntando a su carpeta contenedora, lo que me lleva al problema de cómo detectar estos bucles, evidentemente de forma eficiente.
Hay que extender el ejemplo puesto, ya que puede que el enlace apunte a la carpeta padre del padre del enlace (retrocediendo 2 ó más veces en el árbol de directorios)

El caso es que, para estos caso, el algoritmo que tengo funciona. No sé cómo, pero funciona. Aseguro la ejecución se mete en ese bucle (resultando nombres de directorio como /home/pppp/algo/cfg/cfg/cfg/cfg/cfg/cfg) y no sé cómo se para, pero por suerte se para.

De todas formas, tendré que hacer chequeos de rendimiento para comprobar que no explota el ordenador, que ya me ha pasado por hacer el bruto (no es literal). Que se pare el ordenador (o casi) y que no puedas hacer nada durante varios minutos (me costó lo suyo matar el proceso) no es para nada agradable.

Mmmm... Pues lo primero que se me podria ocurrir (y que me di cuenta que no es presisamente lo mejor) es que hicieras una lista un tanto... extraña de todo aquello con lo que te has encontrado. Si se llegase a devolver por un enlace, obviamente, algun contenido debe de repetirse.

Lo que se me vino a la mente y que creo que no es la mejor opcion, es que hagas una lista del contenido de las carpetas que vas visitando y compararlos cada que entras a una, esto, a primera vista, evita que vuelvas a escanear una carpeta ya analizada, aunque da el problema que yo podria poner varios niveles de carpetas (no enlaces) uno tras otro que se llamen igual y tengan los mismos archivos (repetidos, copiados) y que hasta cierto nivel, algo cambie. Obviamente en este ejemplo lo que propongo (listar los directorios e irlos comparando) no seria efectivo, ahora tendrias el problema de que podria no escanear directorios correctos, ademas, de que podrias perder rendimiendo (haciendo la lista y checando cada vez).

Otra cosa que se me ocurre es que "marques" como visitada la carpeta. ¿Como? Lo primero que se me viene a la mente es crear un archivo oculto en cada dirección que inspeccionas, y al entrar comprobar "si ya esta el archivo no lo reviso porque ya pase por aqui", pero esto da otros problemas como en los dispositivos de solo lectura (como los DVD's o CD's) o dispositivos muy lentos (USB's u otros), ademas, si es el Linux, podria haber problemas con los permisos...

Otra cosa es que pudieras comprobar si la carpeta encontrada es un enlace o no.. pero esas ya serian ondas mas complicadas.... no se como se podria hacer...

Lo único que podría funcionar de una manera medianamente decente y sin interferir con otras cosas es detectarlo en la dirección.
Básicamente consistiría en que, dado un path, se detecte que haya una repetición en las carpetas que tiene el path. Esto es: "/home/pppp/algo/cfg/cfg/cfg/cfg/cfg". En este caso, la carpeta cfg se repite demasiadas veces, con lo que deberíamos abandonar la búsqueda en esa carpeta. De la misma forma se podría detectar como "/home/pppp/algo/cfg/1/algo/cfg/1/algo/cfg/1". Como la secuencia algo-cfg-1 se repite deberíamos abandonar la búsqueda.

Ventajas: se mantiene el mismo grado de concurrencia, ya que la comprobación sólo la hace 1 único hilo de manera autónoma, sin necesidad de que intevengan terceros. Evidentemente, todos los hilos deben hacer esa comprobación, pero la comunicación entre estos es nula.

Desventajas: es imprescindible establecer una tolerancia mínima, en el sentido de que es posible que el directorio "/home/pppp/algo/cfg/cfg" sea legítimo y no un bucle.

Reviviendo este tema (un año más tarde ), creo que tengo una solución bastante aceptable que puede solucionar parte de mis problemas actuales.

Partiendo de una lista de ficheros que se ha cargado con anterioridad desde un archivo, lo que se hace es lo siguiente:

• Se obtiene una instancia del directorio desde donde se quiere empezar la búsqueda
• Se compara la fecha de la última modificación de la instancia obtenida con la que estaba almacenada
• Si la fecha difiere o no se encuentra en la lista, entonces se realiza una busqueda en el sistema de ficheros. En caso contrario, la búsqueda se realiza en la lista de ficheros que se obtuvo con anterioridad

En principio creo que la idea es buena, pero presenta unos posibles problemas que hay que comprobar primero para ver cual es el comportamiento real del sistema:

• Si se almacena una instancia de la clase File, al realizar el método "lastModified()" ¿devuelve un valor cacheado o vuelve a acceder al sistema de ficheros para obtener el valor?
• Si se modifica un fichero, ¿la fecha de modificación se propaga hacia arriba por los directorios del archivo?

Las ventajas de este sistema son:

1. Acceso al disco duro sólo cuando es necesario, lo que debería incrementar la velocidad de búsqueda de forma considerable (he probado a utilizar un archivo como caché y realmente se nota que va más rápido)
2. En principio, el mantenimiento del archivo donde se almacenan la lista de ficheros debería ser mínimo. Se añaden nuevos archivos si no se encuentran o si se ha modificado el directorio y se eliminan si los archivos no existen.
3. El archivo contiene "dumps" de objetos, lo que implica que se pueden volcar objetos más complejos/completos que un File sin necesidad de generarlos desde cero. Tan sólo tendría que cargar los valores apropiados antes de tener que buscarlos. Esto también ahorraría mucho tiempo.

Los inconvenientes:

1. Depende mucho del comportamiento del método "lastModified()". Aún tengo muchas dudas sobre él.
2. El tiempo de carga del archivos con los "dumps" puede ser elevado. Estamos hablando de muchos objetos a los que se ha de añadir los directorios.

¿Creen que toda esta complejidad merece la pena? He estado haciendo algunas pruebas con el método multihilo que comente algún post por encima de este, y "en frío" me tarda en buscar en mi directorio de Música (unos 1700 archivos creo) más de 30 seg con la versión "básica" de archivo y más de 80 seg con la versión "nueva" que es la que quiero utilizar.

A ver que me dicen

Si te sirve, te dejo el algoritmo que usa python para os.walk:



el código completo lo podes ver en /usr/lib/pythonX.Y/os.py.
Por cierto, es lento solo durante la primera pasada, las subsecuentes pasadas es instantaneo.

No creo que difiera mucho del que se puede sacar de java. La razón de que las siguientes pasadas tarde menos es porque casi seguro tiene un mecanismo de caché, al igual que tiene java, para no tener que acceder al disco constantemente.
El método propocionado por java tarda unos 30 segundos en la primera pasada por mi directorio, pero luego apenas tarda 1,5 segundos.
El problema es que estoy haciendo una nueva versión de la clase File de forma que las propiedades del archivo mp3 estén cacheadas y sea muchísimo más rápido consultarlas. El cacheado actual no creo que me sirva ya que aún tengo que acceder al disco para obtener las propiedades.

Ah, entonces lo que estas buscando es algún algoritmo o librería para indexar archivos y vigilar los cambios en una carpeta, es eso?
Mirá, haber si algo de esto te sirve:

http://download.oracle.com/javase/tutor ... ation.html
http://geosoft.no/software/filemonitor/ ... .java.html
http://www.phdcc.com/fiscd/findex.htm

No es tanto para monitorizar el directorio. Me basta con saber si algo a cambiado a la hora de hacer una búsqueda, no necesito saber el momento exacto.

De todas formas, tras hacer un par de pruebas con la primera versión del algoritmo parece que el "lastModified" sólo se modifica en la propia carpeta, y no se extiende por las carpetas contenedoras como yo esperaba, así que va a ser aún más problemático hacerlo de una forma más eficiente.

Bueno creo que he llegado un poco tarde a ver este hilo, pero esta como interesante. Leyendo todos los post y dejando volar un poco la imaginación se me ocurre lo siguiente:

Se me ocurre levantar en memoria una tabla de indexamiento (Puede ser almacenada en un archivo plano) para directorios y archivos, a ver, digamos que tenemos el directorio:


entonces cuando se levante el programa se arma no se algo como un hashmap (Java)o un diccionario(Python), o una matriz, se empieza a procesar esas palabras.

En esta tabla de indexamiento debe de cargarse la palabra junto lo que retorne al aplicarle el checksum(¿Aquí se puede aplicar esto del md5?), debo de tener en cuenta de que debe de tenerse un checksum previo y otro posterior, con esto comparo si existió cambio.

Teniendo esto ya montado en memoria puedo trabajar con cualquier tipo de ordenamiento, tendría que acomodarse los criterios

Espero que ayude de algo no se, jejeje.

Ya que estoy aprendiendo Python vamos a ver si logro redondear aun mas la idea y plasmar algún código.

Salu2

PD: En caso de que mi idea sea muy descabellada podrías revisar esto a ver si te ayuda en algo

Más o menos es lo de ceduardo lo que tengo implementado. Tengo un TreeMap (un poco más lento que el hash map, pero con orden) donde guardo la lista de directorios y el día de modificación del archivo (realmente es un long, pero me vale), y además la lista de ficheros que tengo en cache.
Lo que hago es obtener la lista de directorios contenidos en el directorio que tengo que buscar, y comparar la fecha de modificación. Si es igual entonces obtengo los datos de la caché, y si no los obtengo directamente. En este caso, los ficheros los tengo que actualizar en caché (tanto para borrar como para insertar), y sobreescribir el fichero con la lista de archivos.

La opción de calcular el md5 no creo que sea lo adecuado porque te toca abrir el fichero y leerlo entero, y al menos en mi caso no resulta rentable. Creo que es mejor jugar con la fecha de modificación del directorio, ya que no creo que se acceda directamente al fichero sino que puede estar junto con otros atributos del fichero como el nombre, el tamaño, etc.

Voy a dar otra vuelta de tuerca al problema.

Partamos de mi último post: lo que tenemos es una caché más o menos ordenada donde almacenamos información a modo de indexador.
Debido a que las búsquedas se pueden alargar bastante (casi 1000 seg es mucho esperar), se hace necesario una forma de poder parar la búsqueda. Esto ya lo tengo implementado, pero el problema es el estado en el que se queda la caché.

Supongamos que se empieza la búsqueda en un determinado directorio. Una vez finalizado ese directorio se busca en uno de los hijos, pero antes se actualiza la información del padre (concretamente el valor del lastModified). Supongamos que ahora paramos la búsqueda sin haber terminado de explorar el resto del árbol de directorios. En dichos directorios puede haber información que debería estar en caché, pero que al no haber sido explorados no existen en caché.
A la hora de realizar la siguiente búsqueda lo que hago es, si no ha sido modificado el directorio (los valores de lastMoified coinciden) cargo todos los directorios que cuelgan de él desde caché. El problema está en que al no haber explorado todo el árbol lo que se considera es que los directorios que no han sido cacheados antes (porque se ha interrumpido la búsqueda) no existen, y por tanto el resultado puede ser erróneo.

A la solución que he llegado por el momento es a retrasar los cambios en la información de caché, de forma que si no se ha parado la búsqueda se actualiza la información, y sino permanece la información antigua. El problema es que, aun habiendo explorado medio árbol y poder cachear información, eso no se hace (si se para la búsqueda), lo que me parece un desperdicio.