heurística para buscar a través de datos no perfectamente ordenados

8

Dados los datos ordenados, la solución de búsqueda es obvia. Dados los datos no clasificados, las opciones razonables son ordenar y luego buscar o simplemente buscar linealmente.

Esta pregunta es sobre qué hacer si los datos están algo ordenados, pero no se pueden reorganizar (las operaciones de escritura requieren borrado de sector y los sectores no caben en la memoria RAM).

los detalles:

Los registros de datos se registran secuencialmente con una marca de tiempo . Sin embargo, el reloj de la marca de tiempo se reinicia de vez en cuando a Epoch por un tiempo antes de que se sincronice o simplemente se vuelva a ajustar debido al horario de verano, etc.

El resultado de la búsqueda debe ser el registro de registro con la marca de tiempo más cercana a la hora especificada. Al realizar una búsqueda binaria de registro en una marca de tiempo particular, es posible aterrizar en un parche de datos de registro no contiguos y girar en la dirección incorrecta.

Además de un método lineal bruto, ¿hay alguna heurística que podamos aprovechar aquí? Por ejemplo, ¿una búsqueda Simplex inmune a los mínimos locales?

actualizar:

Podemos suponer que aproximadamente el 95% de los registros están en secuencia ordenada. alrededor del 5% (disperso a través del registro) son hipo sucio. El comienzo del hipo se puede identificar cuando la marca de tiempo retrocede en el tiempo y tiene un sello anterior al inicio del registro

MandoMando
fuente
¿Existe una característica distintiva con las marcas de tiempo erróneas? Si sí, entonces sólo tiene que ir linealmente hacia delante hasta que un "buen" registro se acerca y eje sobre el que
monstruo de trinquete
@ratchetfreak, la única distinción posible es que es probable que sean marcas de tiempo más antiguas, no garantizadas. El problema con lineal a través del parche es que podría durar mucho tiempo.
MandoMando
2
también existe la opción de indexación, además de ordenar y escanear
CapelliC
Un bloque de muestra de registros podría ayudar. Además, ¿cómo se organizan sus datos, archivo de texto, registro de la base de datos, datos ASCII de formato fijo, etc.?
Jan Doggen
2
Tal vez una tontería: ¿no puede solucionar la causa raíz del reinicio del reloj? es decir. if (currentTimeStamp <lastLogTimeStamp) {force clock resync} writeToLog (...)
Steven Evers

Respuestas:

3

Suposiciones adicionales

Esta respuesta se basa en los siguientes supuestos adicionales:

  • puede determinar fácilmente la marca de tiempo para el comienzo del registro y
  • Es factible almacenar las posiciones del hipo (opcional)

Algoritmo de búsqueda

La búsqueda se divide en dos algoritmos diferentes realmente. En caso de que busque un registro con una marca de tiempo que esté después del comienzo del registro, sabe que no se encontrará en el hipo y utilice la búsqueda sin hipo a continuación. En caso de que busque una marca de tiempo antes del comienzo del registro, utilice la búsqueda de hipo . Si no busca por la marca de tiempo, sino por algún otro criterio, primero intente la búsqueda sin hipo debido a su cobertura del 95% y luego intente la búsqueda de hipo si no puede encontrar nada.

Opcionalmente, puede acelerar la búsqueda sin contratiempos mediante un paso de preprocesamiento.

Preprocesamiento (opcional)

Si es posible, analice previamente sus datos con una búsqueda lineal para descubrir las posiciones de los datos de hipo. Esto depende completamente de la viabilidad de poder almacenar estos rangos, lo que podría ser posible dado que solo representan el 5% de sus registros (o no, en cuyo caso el rendimiento se degrada).

Tenga en cuenta que la estructura de datos correspondiente debe actualizarse cada vez que escriba nuevos registros, o al menos debería poder indicarle hasta qué punto de los registros se realizó el preprocesamiento.

Búsqueda sin contratiempos

La búsqueda de datos sin hipo es posible mediante una combinación de búsqueda binaria y lineal. Sin embargo, realiza una búsqueda binaria normal, cuando su elemento pivote tiene una marca de tiempo antes del comienzo del registro, es decir, el elemento pivote es un hipo, necesita determinar la primera entrada de registro antes del elemento pivote y usarlo como el elemento pivote real de tu búsqueda binaria.

Esta primera entrada de registro con una marca de tiempo después del comienzo del registro se encuentra a través de una búsqueda lineal que comienza desde el elemento pivote de hipo. Si sabe por preprocesamiento o actualizaciones incrementales de sus problemas de almacenamiento en caché donde se encuentra el elemento pivote relevante, puede saltar allí en tiempo constante. Si tuvo que ejecutar la búsqueda lineal completa, actualice una estructura de datos para almacenar que estas posiciones están cubiertas por datos de hipo, de modo que la próxima vez pueda determinar rápidamente el elemento pivote correcto.

Búsqueda de hipo

Esto depende de si ha realizado el preprocesamiento. Si no, es una búsqueda lineal a través de todos sus datos (y también puede hacer las partes de preprocesamiento en este momento). De lo contrario, su estructura de datos preprocesada puede indicarle las posiciones de los datos de hipo y puede buscar directamente a través de estos, es decir, realizar una búsqueda lineal solo a través del 5% de los datos de hipo.

Actuación

Para la búsqueda sin contratiempos con datos totalmente preprocesados, puede obtener casi el rendimiento de una búsqueda binaria predeterminada. En lugar de una comparación simple en cada paso, necesita una comparación adicional para determinar si golpea un elemento hipo y, de ser así, necesita un acceso a su estructura de datos para encontrar el elemento pivote real. Sin embargo, este trabajo adicional se alivia un poco por el hecho de que no solo descarta la mitad de su conjunto de datos, sino que también descarta la parte de datos de hipo.

Por supuesto, si tiene que recurrir a la búsqueda lineal, esto se degrada en consecuencia.

La búsqueda de hipo es un mal caso si no tiene información sobre el hipo existente disponible y necesita buscar linealmente a través de todos los datos.

Finalmente, si no busca una marca de tiempo, pero existen otros criterios y no existe tal entrada de registro, este es su peor caso. De hecho, si no tiene una estructura de datos para el hipo, termina siendo más lento que la búsqueda lineal, ya que ambas ejecuciones de búsqueda pueden escanear linealmente las mismas posiciones de hipo (aunque todavía es O (n)).

Si tiene la estructura de datos disponible y totalmente preprocesada, el peor tiempo de ejecución se reduce a O (max (log (M) * log (N), M)) donde M es la cantidad de datos de hipo, que se busca linealmente, y suponiendo que puede buscar el final de los datos de hipo dada cualquier posición de hipo de su estructura de datos en O (log (M)).

Franco
fuente
@Franks gracias por esto! Estaba acumulando un esquema donde, al aterrizar en un hipo, se examinarían ambos posibles pivotes futuros para ver si es posible una reducción de 1/4 (en lugar de 1/2) del tamaño de los datos. No estaba seguro de qué hacer con el caso donde los tres (pivote actual y dos posibilidades) son hipo. Con su sugerencia, funcionará una caminata lineal hasta el borde del parche de hipo.
MandoMando