Mejor estructura de datos para el vecino más cercano en 1 dimensión

Question

Tengo una lista de valores (unidimensionales) y me gustaría conocer la mejor estructura de datos/algoritmo para encontrar el valor de consulta más cercano que tengo. La mayoría de las soluciones (¿todas?) Que encontré aquí son para 2 o más dimensiones. ¿Alguien puede sugerirme el enfoque para mi caso?

Mi instinto me dice que ordene los datos y utilice la búsqueda binaria de alguna manera. Por cierto, no hay límite en la construcción o el tiempo de inserción de ningún árbol, por lo que probablemente alguien pueda sugerir un árbol mejor que simplemente una lista ordenada.

Answer 1

Si necesita algo más rápido que O (log (n)), que puede obtener fácilmente con una matriz ordenada o una búsqueda binaria árbol, puede usar un van Emde Boas Tree. Los árboles vEB te dan O (log (log (n))) para buscar el elemento más cercano a cada lado.

Answer 2

Ordene la lista y utilice la búsqueda binaria para encontrar el elemento que está buscando, luego compare sus vecinos izquierdo y derecho. Puede usar una matriz que es O (1) acceso.

Algo así como:

int nearest(int[] list, int element) { 

    sort(list); 
    int idx = binarySearch(element, list); 

    // make sure you are accessing elements that exist 
    min = (element - list[idx-1] <= list[idx+1] - element) ? idx-1 : idx+1; 

    return list[min]; 
} 

Esta es O (n log n), el cual será amortizado si se va a realizar muchas subidas mirada.

EDIT: Para que usted tendría que mover la clasificación de este método

Answer 3

Como ya se ha mencionado, la forma más fácil y rápida debe clasificar los datos y luego en busca de la izquierda y derecha de un vecino punto de datos.

Answer 4

Si el tiempo de inserción es irrelevante, la búsqueda binaria en una matriz ordenada es la forma más sencilla de lograr el tiempo de consulta O (log N). Cada vez que se agrega un elemento, ordena todo. Para cada consulta, realice una búsqueda binaria. Si se encuentra una coincidencia, devuélvala. De lo contrario, la búsqueda binaria debería devolver el índice del artículo, donde debería haberse insertado. Use este índice para verificar los dos elementos vecinos y determinar cuál de ellos está más cerca del punto de consulta.

Supongo que hay soluciones con O (1) tiempo. Trataré de pensar en uno que no involucre demasiado uso de memoria ...

Answer 5

El uso de OCaml Set:

module S = Set.Make(struct type t = int let compare = compare end) 

let nearest xs y = 
    let a, yisin, b = S.split y xs in 
    if yisin then y 
    else 
     let amax, bmin = S.max_elt a, S.min_elt b in 
     if abs (amax - y) < abs (bmin - y) then amax else bmin 

Por cierto, se puede apreciar mi nth-nearest neighbor sample de OCaml for Scientists y The F#.NET Journal artículo Traversing networks: nth-nearest neighbors.