Mise en œuvre de l'algorithme de recherche de plage

Question

Je voudrais poser une question sur l'algorithme.

Supposons qu'il y ait plusieurs segments (segments nombre pas fixes, peut-être si longd)

exemple:.

segment     data range (data range not fixed) 

**A        0~10** 

**B        11~45** 

**C        46~49** 

**D        50~100** 

**E        101~105** 

**F        106~128** 

Si l'entrée → 99

Je vais obtenir la sortie 'D' de mon programme.

Je vais mettre cet exemple d'implémentation en Java. Alors, avez-vous un moyen ou un algorithme pour accélérer le temps d'exécution du programme?

Answer 1

Vous pouvez utiliser la plage de gaava. Créez des plages, vérifiez (simple pour la boucle) si votre entrée est à portée.

Guava's Range Tutorial

Ranges Explanation

Docs

Answer 2

Vous pouvez utiliser ConcurrentSkipListMap et ajouter à la carte la gamme et les valeurs

Answer 3

En supposant que vos plages de données sont à la fois triées et ne se chevauchent pas, vous peut essayer d'utiliser une approche de style de recherche binaire à ce sujet.

Vous pouvez placer les valeurs de départ de chaque plage dans un tableau:

[0, 11, 46, 50, 101, 106] 

La valeur de départ correcte, si elle existe, aurait les deux propriétés suivantes:

• Il est moins
• La valeur adjacente à droite est soit supérieure à 90, soit n'existe pas (par exemple, si la valeur initiale était la dernière plage du tableau)

La recherche de 90 est triviale dans ce cas parce que nous le frapperions immédiatement. Disons que nous voulions trouver 20. Nous prendre les mesures suivantes:

[0, 11, 46, 50, 101, 106] 
Choose 50; fails because 50 > 20; go left 
[0, 11, 46] 
Choose 11; succeeds because 20 > 11 and 20 < 46 

Donc, ce céderais la gamme 11-45, et nous avons besoin d'un plus vérifier pour vous assurer que 20 est dans cette plage. Dans ce cas, c'est le cas, mais ce n'est pas obligatoire. L'approche de recherche binaire décrite ci-dessus ne trouve que la meilleure plage d'ajustement, qui ne doit pas nécessairement contenir le nombre réel.

Answer 4

Vous pouvez utiliser un Interval Tree - J'ai publié une implémentation here il y a un certain temps. Un arbre d'intervalle peut également gérer des plages de chevauchement.