Hacher une plage

Question

J'ai un tableau d'éléments de plage. Chaque élément a un début et une fin. Dans le tableau, les plages ne se chevauchent pas et sont triées.

ie (code juste pour illustrer, ne vous attendez pas à compiler):

var arr = { [0,3], [5,10], [15,59] }; 

Compte tenu d'une valeur (par exemple 9), est-il une fonction de hachage des gammes qui me permettra d'obtenir rapidement la élément qui a la plage qui contient la valeur?

Bien sûr, il y a la solution naïve, il suffit de faire défiler chaque élément jusqu'à ce que vous trouviez le bon; le plus élaboré, comme la recherche binaire par le début de la gamme; et le breveté de créer un arbre binaire avec les gammes. Mais est-ce que quelqu'un connaît un moyen d'utiliser un hachage?

Answer 1

Vous pouvez créer un index pour les valeurs de départ à indexer en arr.

var arr = { [0,3], [5,10], [15,59] }; 

var dictStart = new Dictionary<int, int>(); 
dictStart.Add(0, 0); 
dictStart.Add(5, 1); 
dictStart.Add(15, 2); 

Maintenant, pour obtenir la gamme que vous pouvez faire une recherche binaire sur les valeurs de la dict dictStart pour le premier élément qui est plus élevé que la valeur à rechercher. Ensuite, prenez l'entrée précédente.

Difficile à expliquer. A titre d'exemple, recherchez 9. Faites la recherche de ce qui a eu l'élément e = [5, 1].

var range = arr[e[1]]; // = [5, 10] 
bool isWithin = val <= range[1] && val >= range[0]; 

Ainsi, la mémoire sera moins invasive. La clé est d'avoir une recherche rapide pour les valeurs de départ des plages. Je suppose que cela va résoudre le problème, mais ce n'est pas un hachage.

Answer 2

Vous pouvez calculer à l'avance le quartier le plus proche et le stocker quelque part. Dans votre exemple, la table contient 0..59 entrées et vous stockez l'index de la plage la plus proche à chaque index.

De cette façon, ce sera vraiment rapide.

Answer 3

Que diriez-vous d'utiliser un Dictionary<int, Element> pour contenir tous les nombres dans toutes les plages, i. e. ajouter les quatre entrées

0, [0,3] 
1, [0,3] 
2, [0,3] 
3, [0,3] 

et ainsi de suite pour les autres plages. Il utilise un hachage en utilisant le dictionnaire, mais je doute que ce soit la solution la plus efficace.