Comment trouver 1 ou plusieurs intervalles de temps partiellement entrecroisés dans une liste de quelques millions?

Question

J'ai besoin d'une idée pour un algorithme d'index/recherche efficace, et/ou structure de données, pour déterminer si un intervalle de temps chevauche zéro ou plusieurs intervalles de temps dans une liste, en gardant à l'esprit qu'un chevauchement complet est un cas particulier chevauchement partiel. Jusqu'à présent, je n'ai pas trouvé quelque chose de rapide ou élégant ...

Considérons une collection d'intervalles avec chaque intervalle ayant 2 dates - début et fin.

Les intervalles peuvent être grands ou petits, ils peuvent se chevaucher partiellement ou pas du tout. Dans la notation Java, quelque chose comme ceci:

interface Period 
{ 
    long getStart(); // millis since the epoch 
    long getEnd(); 
    boolean intersects(Period p); // trivial intersection check with another period 
} 

Collection<Period> c = new ArrayList<Period>(); // assume a lot of elements 

L'objectif est de trouver efficacement tous les intervalles qui se coupent partiellement un intervalle d'entrée nouvellement arrivé. C comme ArrayList cela pourrait ressembler à ...

Collection<Period> getIntersectingPeriods(Period p) 
{ 
    // how to implement this without full iteration? 
    Collection<Period> result = new ArrayList<Period>(); 
    for (Period element : c) 
    if (element.intersects(p)) 
     result.add(element); 
    return result; 
} 

En parcourant la liste complète nécessite linéairement un trop grand nombre se compare à atteindre mes objectifs de performance. Au lieu de ArrayList, quelque chose de mieux est nécessaire pour diriger la recherche et minimiser le nombre de comparaisons.

Ma meilleure solution consiste à maintenir deux listes triées en interne et à effectuer 4 recherches binaires et une itération de liste pour chaque requête. De meilleures idées?

---

Note de l'éditeur: intervalles de temps sont un cas particulier en utilisant des segments linéaires le long d'un axe unique, que ce soit X, ou dans ce cas, T (pour le temps).

Answer 1

Interval trees fera:

En computer science, un arbre intervalle est un tree data structure de tenir intervals. Plus précisément, il permet de trouver efficacement tous les intervalles qui se chevauchent avec un intervalle ou un point donné. Il est souvent utilisé pour les requêtes de fenêtrage, par exemple, pour trouver toutes les routes sur une carte informatisée dans une fenêtre rectangulaire, ou pour trouver tous les éléments visibles à l'intérieur d'une scène tridimensionnelle. Une structure de données similaire est la ...

Answer 2

Semble l'article Wiki résout plus que demandé. Êtes-vous lié à Java?

Vous avez un « énorme collection d'objets » qui me dit « Base de données » Vous avez demandé « des capacités intégrées d'indexation de la période » et l'indexation me dit base de données.

Vous seul pouvez décider si ce SQL répond à votre perception de « élégante »:

Select A.Key as One_Interval, 
     B.Key as Other_Interval 
From Big_List_Of_Intervals as A join Big_List_Of_Intervals as B 
    on A.Start between B.Start and B.End OR 
     B.Start between A.Start and A.End 

Si le début et colonnes de fin sont indexés, une base de données relationnelle (selon la publicité) sera très efficace à ce sujet.