heurística para buscar datos no ordenados perfectamente

8

Dados los datos ordenados, la solución de búsqueda es obvia. Dados los datos sin clasificar, las opciones razonables se ordenan por búsqueda, o simplemente por búsqueda lineal.

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

los detalles:

Los registros de datos se registran secuencialmente con una marca de tiempo . Sin embargo, el reloj de la marca de tiempo, desde la hora hasta , se restablece en Epoch por un tiempo antes de sincronizarse o simplemente se ajusta nuevamente debido al horario de verano, etc.

El resultado de la búsqueda debe ser el 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 equivocada.

Además de un método lineal bruto, ¿hay alguna heurística que podamos aprovechar aquí? p.ej. ¿Una búsqueda simplista inmune a los mínimos locales?

actualizacion :

Podemos suponer que alrededor del 95% de los registros están en secuencia ordenada. Alrededor del 5% (dispersos a través del registro) son los hipo sucios. El comienzo de las dificultades puede identificarse cuando la marca de tiempo se desplaza hacia atrás en el tiempo y y tiene un sello anterior al principio del registro

    
pregunta MandoMando 09.04.2013 - 18:13

1 respuesta

3

Suposiciones adicionales

Esta respuesta se basa en los siguientes supuestos adicionales:

  • puede determinar fácilmente la marca de tiempo para el inicio del registro, y
  • es posible almacenar las posiciones de los contratiempos (opcional)

Algoritmo de búsqueda

La búsqueda se divide en dos algoritmos diferentes realmente. En el caso de que busque un registro con una marca de tiempo que sea después de el comienzo del registro, sabrá que no se encontrará en los contratiempos y utilice búsqueda de no hipo abajo En caso de que busque una marca de tiempo antes del comienzo del registro, utilice hipo search en su lugar. Si no busca por marca de tiempo, pero sí algún otro criterio, primero intente la búsqueda sin interrupciones debido a su cobertura del 95% y luego intente la búsqueda de interrupciones si no se ha podido encontrar nada.

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

Preprocesamiento (opcional)

Si es posible, analice previamente sus datos con una búsqueda lineal para averiguar 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 interrupciones es posible a través de una combinación de búsqueda binaria y lineal. Sin embargo, cuando 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 problema, debe determinar la primera entrada del registro antes del elemento pivote y utilizarlo como el elemento pivote real. de tu busqueda binaria.

Esta primera entrada de registro con una marca de tiempo después el inicio 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 a sus problemas almacenados en caché donde se coloca el elemento de 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 de 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 puede hacer las partes de preprocesamiento en este momento también). De lo contrario, su estructura de datos preprocesada puede decirle 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.

Rendimiento

Para una búsqueda sin interrupciones con datos totalmente preprocesados, puede obtener casi el rendimiento de una búsqueda binaria predeterminada. En lugar de una simple comparación en cada paso, necesita una comparación adicional para determinar si ha alcanzado un elemento de 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 ve ligeramente aliviado 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 disponible sobre hipos existentes y necesita buscar de forma lineal en 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 los contratiempos, termina siendo más lento que la búsqueda lineal, ya que ambas ejecuciones de búsqueda pueden escanear linealmente las mismas posiciones de contratado (aunque todavía es O (n)).

Si tiene la estructura de datos disponible y completamente preprocesada, el tiempo de ejecución en el peor de los casos se reduce a O (máx. (log (M) * log (N), M)) donde M es la cantidad de datos de hipo, que es buscó de forma lineal, y suponiendo que puede buscar el final de los datos de hipo dado cualquier posición de hipo de su estructura de datos en O (log (M)).

    
respondido por el Frank 10.04.2013 - 08:15

Lea otras preguntas en las etiquetas