Meilleure structure de données pour le plus proche voisin dans 1 dimension

Question

J'ai une liste de valeurs (1-dimensionnelle) et je voudrais connaître la meilleure structure de données/algorithme pour trouver le plus proche d'une valeur de requête que j'ai. La plupart des solutions (toutes?) Que j'ai trouvées pour les questions ici concernent 2 dimensions ou plus. Quelqu'un peut-il me suggérer l'approche de mon cas? Mon instinct me dit de trier les données et d'utiliser la recherche binaire d'une manière ou d'une autre. En passant, il n'y a aucune limite sur la construction ou le temps d'insertion pour n'importe quel arbre nécessaire, alors probablement quelqu'un peut suggérer un arbre meilleur que simplement une liste triée.

Answer 1

Si vous avez besoin de quelque chose de plus rapide que O (log (n)), que vous pouvez facilement obtenir avec un tableau trié ou une recherche binaire arbre, vous pouvez utiliser un van Emde Boas Tree. Les arbres vEB vous donnent O (log (log (n))) pour rechercher l'élément le plus proche de chaque côté.

Answer 2

Triez la liste et utilisez la recherche binaire pour trouver l'élément que vous recherchez, puis comparez vos voisins gauche et droit. Vous pouvez utiliser un tableau qui est un accès O (1).

Quelque chose comme:

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]; 
} 

Ceci est O (n log n), qui sera amorti si vous allez effectuer des hauts look.

EDIT: Pour que vous auriez à déplacer le tri de cette méthode

Answer 3

Comme vous l'avez mentionné, la façon la plus rapide et la plus simple devrait être trier les données et à la recherche puis pour le voisin de gauche et à droite d'un point de données.

Answer 4

Si le temps d'insertion n'est pas pertinent, la recherche binaire sur un tableau trié est le moyen le plus simple d'atteindre l'heure de requête O (log N). Chaque fois qu'un article est ajouté, tout est trié. Pour chaque requête, effectuez une recherche binaire. Si une correspondance est trouvée, retournez-la. Sinon, la recherche binaire doit renvoyer l'index de l'élément, où il aurait dû être inséré. Utilisez cet index pour vérifier les deux éléments voisins et déterminer lequel d'entre eux est le plus proche du point de requête. Je suppose qu'il y a des solutions avec O (1) temps

Je vais essayer de penser à un qui n'implique pas trop d'utilisation de la mémoire ...

Answer 5

L'utilisation Set de OCaml:

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 

Soit dit en passant, vous pouvez apprécier ma nth-nearest neighbor sample de OCaml for Scientists et The F#.NET Journal article Traversing networks: nth-nearest neighbors.