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
fuente
Respuestas:
Suposiciones adicionales
Esta respuesta se basa en los siguientes supuestos adicionales:
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)).
fuente