[Alg/Java] Ruimte bepalen voor een interval

[-FoX-]

Ik ben op zoek naar een goede maar vooral efficiënte manier om te bepalen of een bepaald interval in een bepaalde lijst terecht kan zonder hiermee andere intervallen te overlappen. Als het nieuwe interval een andere interval zou overlappen; dan moet deze in een nieuwe lijst terechtkomen.

Om het maar even met een voorbeeld duidelijk te maken; ik heb deze lijst van intervallen:

code:

[15, 30[ - [60, 90[

Ik wil het volgend interval in de lijst inbrengen: [45 - 90[. Dit is dus niet mogelijk omdat er overlap is met het element [60,90[. Ik denk dat het wel duidelijk is waar ik naartoe wil.

Aangezien er meerdere lijsten mogelijk zijn, wil ik zo efficiënt mogelijk kunnen bepalen in welke lijst er nog ruimte beschikbaar is voor het nieuwe interval. Ook wil ik dit binnen de lijst zo goed mogelijk kunnen bepalen.

Ik dacht de implementatie hiervan op te lossen door gebruik te maken van een HashMap<Integer, TreeSet>. De Integer stelt dan het nummer van de lijst voor; en de TreeSet wil ik gebruiken om een B-Tree voorstelling van de elementen te verkrijgen.

Voor deze heb ik dan ook een comparator geïmplementeerd voor de sortering van de intervallen (maar hier klopt nog iets niet aan imo):

Java:

private class IntervalComparator implements Comparator {
    public int compare(Object obj1, Object obj2) {
      Interval interval1 = (Interval ) obj1;
      Interval interval2 = (Interval ) obj2;

      int fromCompare = interval1.getFrom().compareTo(interval2.getFrom());
      if(fromCompare != 0) {
        return fromCompare;
      }

      return interval1.getTo().compareTo(interval2.getTo());
    }
  }

Ik zou dus een subSet van deze TreeSet kunnen nemen om te bepalen of er een overlap inzit. Maar weet niet goed hoe ik deze dan moet bepalen.

Ik geraak er even niet uit op welke manier ik dit nu het best kan implementeren

Hopelijk is het een beetje duidelijk zo; alle hulp is welkom!

[Feyd-Rautha]

Een zeer interessante datastructuur die je zou kunnen gebruiken is de Interval-tree. Meer informatie kun je hier vinden. Persoonlijk heb ik geen ervaring met deze tree, maar dit was iets waar ik aan dacht.

Dit is een uitbreiding van een BST (veelal een Red-Black tree). Implementaties van deze datastructuur hebben dan bv een search-operatie die een interval kan opzoeken die overlapt met een gegeven interval in O(lg n) tijd.

[ Voor 29% gewijzigd door Feyd-Rautha op 02-09-2006 12:58 ]

[Verwijderd]

Ik ging een binary search voorstellen maar die interval tree is natuurlijk precies hetzelfde.

De vraag of een interval in een gegeven lijst past valt dus in O(log N) te beantwoorden, en ik denk niet dat het beter wordt dan dat[1].

In welke lijst uit een verzameling van lijsten hij het beste kan is een hele andere vraag en hangt ervanaf hoe je "beste" definiëert. Oftewel, waar wil je naar optimaliseren? Zo min mogelijk ongebruikte ruimte in een lijst? Zo veel mogelijk intervallen in een lijst? Zoveel mogelijk verdelen over de beschikbare lijsten?

Afhankelijk van je eisen kun je misschien wel wegkomen met een gewoon "greedy" algoritme. Pak de eerste de beste lijst waar een interval in kan. Klaar.


[1] Een alternatieve oplossing: met een array van "punten" kun je dat veranderen in O(M), waar M de lengte is van de in te voegen intervallen. Alleen aan te raden als je veel, relatief kleine intervallen gebruikt, en je beperkt jezelf op die manier natuurlijk wel tot alleen integers, of een ander discreet interval van willekeurige precisie. Plus het kost natuurlijk bakken geheugen. Ik denk dat de O(log N) van een binaire boom dus in de praktijk je beste oplossing zal zijn.

[-FoX-]

Een interval tree lijkt inderdaad een goede match voor dit probleem te zijn.

Verwijderd schreef op zaterdag 02 september 2006 @ 16:18:
Ik ging een binary search voorstellen maar die interval tree is natuurlijk precies hetzelfde.

De vraag of een interval in een gegeven lijst past valt dus in O(log N) te beantwoorden, en ik denk niet dat het beter wordt dan dat.

Ik weet niet zeker of dit wel in O(log N) operaties bekomen kan worden? Waar staaf jij je op; op een regular binary tree?

In welke lijst uit een verzameling van lijsten hij het beste kan is een hele andere vraag en hangt ervanaf hoe je "beste" definiëert. Oftewel, waar wil je naar optimaliseren? Zo min mogelijk ongebruikte ruimte in een lijst? Zo veel mogelijk intervallen in een lijst? Zoveel mogelijk verdelen over de beschikbare lijsten?

Afhankelijk van je eisen kun je misschien wel wegkomen met een gewoon "greedy" algoritme. Pak de eerste de beste lijst waar een interval in kan. Klaar.

Een "greedy" algoritme kan in eerste instantie wel voldoende zijn. Ik denk dat de eerste lijst zoveel mogelijk intervallen moet bevatten.. en hoe meer lijsten er zijn, hoe minder intervallen ze in principe mogen bevatten.

Dan blijft er alleen nog de vraag op welke manier ik dit "Interval Tree" algoritme moet implementeren

[Feyd-Rautha]

Ik weet niet zeker of dit wel in O(log N) operaties bekomen kan worden? Waar staaf jij je op; op een regular binary tree?

Een Interval-tree is een zogenaamde augmented binary tree. Als je onderliggende datastructuur een balanced tree is (zoals een RB-tree), zijn uw operaties in O(log n) te doen.

Dan blijft er alleen nog de vraag op welke manier ik dit "Interval Tree" algoritme moet implementeren

Op google is er wel het een en het ander over te vinden. De algoritmes moeten ook wel te vinden zijn.
Let er wel op dat jouw onderliggende binary tree zeker en vast self-balancing is. Aangezien je enkel niet-overlappende intervallen in zo een boom zult opslaan, krijg je anders een volledig ongebalanceerde boom (enkel linkse of rechtse takken); met als resultaat dat uw operaties terug O(n) zullen zijn.

[ Voor 45% gewijzigd door Feyd-Rautha op 02-09-2006 17:28 ]

[Verwijderd]

offtopic:
En dan was er een topic, waarin werd gezegd dat software engineers niets aan de universiteit zouden hebben.... (dat het allemaal veels te "theoretisch" was). Interessant tegenvoorbeeld.

[.oisyn]

Een interval tree hoef je niet per se tee implementeren, je kunt ook gebruik maken van een reguliere binary tree waar je steeds het eind-element in opslaat, met het start-element als geassocieerde data. Kijken of een bepaald getal in een interval valt doe je door een lowerbound search te doen op dat getal - dit geeft het eerstvolgende interval dat eindigt na het getal, dus na controle of dat interval ook daadwerkelijk overlapt heb je je resultaat. Om te kijken of er intervallen bestaan in een gegeven interval, doe je zowel lowerbound als upperbound searches op resp. de start en het eind van het interval, en doe je de controle zoals voorheen.

[-FoX-]

.oisyn schreef op zaterdag 02 september 2006 @ 19:54:
Een interval tree hoef je niet per se tee implementeren, je kunt ook gebruik maken van een reguliere binary tree waar je steeds het eind-element in opslaat, met het start-element als geassocieerde data.
Kijken of een bepaald getal in een interval valt doe je door een lowerbound search te doen op dat getal - dit geeft het eerstvolgende interval dat eindigt na het getal, dus na controle of dat interval ook daadwerkelijk overlapt heb je je resultaat. Om te kijken of er intervallen bestaan in een gegeven interval, doe je zowel lowerbound als upperbound searches op resp. de start en het eind van het interval, en doe je de controle zoals voorheen.

Ik kan je redenering op zich wel volgen, maar kan je het misschien nog wat aansterken met wat leesbare (pseudo) code? Want ik zie het toch niet helemaal voor me

Met lowerbound bedoel je de linkerzijde?

[Nick The Heazk]

Je kunt je compare-code beter generisch maken. Zo voorkom je casting-exceptions.

Java:

private class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval interval1, Interval interval2) {
      int fromCompare = interval1.getFrom().compareTo(interval2.getFrom());
      if(fromCompare != 0) {
        return fromCompare;
      }

      return interval1.getTo().compareTo(interval2.getTo());
    }
  }

[H!GHGuY]

Het kan eventueel handig zijn om een andere notatie te gebruiken.
ipv [10, 15[ gebruik je <10,5<.

Je kan een gebalanceerde boom gebruiken, gesorteerd op beginpunt. Als je een interval wil toevoegen zoek je je nieuw beginpunt op en gebruik je de 2 nodes (als het beginpunt gelijk is moet je zowiezo niet toevoegen) met dichtste beginpunten en controleer je of er overlap is.

dit kan aangezien geen enkele 2 intervallen reeds overlappen.