[Java] groeperingsalgoritme

[-FoX-]

Ik ben momenteel de mogelijkheden aan het bekijken om op een effectieve manier een hierarchische groupering van objecten te maken. In feite kan je de relatie zien als een 1-N relatie. De grouperingscriteria liggen niet vast, aangezien dezen afhangen van het type die het object met zich mee draagt.

Het gaat om transacties, die gegroepeerd moeten worden afhankelijk van het type van transactie. Ieder type heeft zo zijn eigen groeperingsregels.

Een internationale transactie dient bijvoorbeeld gegroepeerd te worden op uitvoeringsdatum en bestemmeling, opgedeeld in batches van 25.

Een mogelijke oplossing lijkt me om een Factory te creeëren, die afhankelijk van het type transactie, de juiste batch-creator (die de typische regels implementeerd) returneerd. Deze batch-creator gaat alle transacties opnemen en teruggeven in een Collection van List's.
De batch-creator zal dan een comparator implementatie moeten bevatten die de sortering voor zijn rekening neemt; de hele lijst van transacties sorteerd om hier vervolgens over te itereren en de opsplitsing te maken. Indien >25 of verschillende type gevonden bij het itereren, maak een nieuwe List aan en voeg deze toe aan de algemene Collection.

Ik ben er nog niet uit op welke wijze ik dit het best kan implementeren. De lijsten met objecten die gegroepeerd moeten worden zullen groot zijn (tussen 1.000-10.000); dus een efficient algoritme is wel aangeraden; en denk dat er wel efficientere mogelijkheden zijn, dan wat ik totnutoe verzonnen heb?

[H!GHGuY]

Het lijkt me dus alsof je bepaalde groepen/partities wil maken van transacties. Deze transacties moeten daarna ook nog eens gesorteerd zijn op bepaalde criteria ?

ik dacht hierbij meteen aan een union-find algoritme waar je de uiteindelijke partities sorteert.

[-FoX-]

Inderdaad; ik wil deze transacties opdelen in groepen oftewel partities. De criteria van groepering zijn verschillend per type transactie. Ze moeten niet perse gesorteerd zijn; maar wel in de groep geplaatst waartoe ze horen en bijvoorbeeld met een max. van 3 per groep.

code:

tx1 - 6/6/2006 - CN
tx2 - 7/6/2006 - CN
tx3 - 6/6/2006 - DN
tx4 - 6/6/2006 - DN
tx5 - 6/6/2006 - CN
tx6 - 6/6/2006 - CN
tx7 - 6/6/2006 - CN

Er dienen dan 4 uiteindelijke groepen te zijn

code:

- ROOTGROUP
  - GROUP1 [tx1, tx5, tx6]
  - GROUP2 [tx7]
  - GROUP3 [tx2]
  - GROUP4 [tx3, tx4]

Aangezien het om grote hoeveelheden zal gaan (gemiddeld tussen 1.000 en 10.000 objecten / per actie; als dit eenmalig was, viel het nog mee.. met het systeem wordt gebruikt door vele concurrent users 3000-tal), ben ik nog steeds aan het zoeken naar een optimale implementatie hiervoor.

Op welke wijze zou je die union-find dan in dit geval implementeren (pseudo)?

[H!GHGuY]

de bruikbaarheid van union-find is natuurlijk afhankelijk van de voorwaarden.

Je hebt namelijk een equivalentie-relatie nodig tussen de elementen van een groep.
(R = relatie)
-> aRa is waar
-> aRb en bRc => aRc
-> aRb => bRa

pas dan kun je effectief union-find toepassen:
http://en.wikipedia.org/wiki/Union-Find

[-FoX-]

Natuurlijk dient het te gaan om equivalantie relaties om deze te groeperen; anders zou het nut van het groeperen ook een beetje vergaan. In dit geval zullen deze equivalantie relaties wel afhangen van het type; maar binnen 1 overkoepelende group is dit eigenlijk niet van toepassing, omdat deze groep enkel transacties van hetzelfde type zal bevatten.

Ik weet niet of het union-find algoritme wel helemaal geschikt is voor mijn probleem.. heb het wikipedia artikel eens doorgelezen, maar echt duidelijk staat het er niet beschreven imho.

In eerste instantie gaat het ook niet echt om een diep geneste hierarchische structuur, en zal het vaak gaan om 2 levels diep (zal later waarschijnlijk pas uitgebreidt dienen te worden naar meerdere niveau's).

Als ik het goed begrijp, ga je eigenlijk in elke gecreeerde lijst kijken of deze een equivalent type bevat en het huidige erbij proppen als dit het geval is; in het andere geval een nieuwe lijst creeeren?

[H!GHGuY]

dat zou een variant zijn die denk'k toch beter bij jou situatie past ja.

bij union-find is het zo dat elk element in het begin een eigen groep vormt.
Daarna worden telkens 2 elementen aangereikt die equivalent zijn.
Je zoekt hun vertegenwoordiger op (een equivalent type) en als die niet gelijk is moet je de 2 groepen bij elkaar voegen.

Het algoritme van Kruskal is een toepassing van union-find voor een minimaal overspannende boom te vinden.

Wat jou situatie betreft zou het misschien beter zijn als je telkens een element aanreikt en kijkt of deze equivalent is met de reeds bestaande groepen. Is ze equivalent dan voeg je ze toe. Is ze dit niet dan creer je een nieuwe groep.

[-FoX-]

Een mogelijke oplossing inderdaad, maar lijkt me toch nog verre van optimaal en zelfs zwaar voor het systeem. Stel dat we een lijst hebben van een 10.000-tal elementen en dat er geen enkel element een equivalent heeft. Dan zou ik dus uiteindelijk 10.000 List's hebben, met telkens maar 1 object erin. Maar ook het vergelijken loopt erg omslachtig; aangezien het vergelijken met ieder element noodzakelijk is.
Element X moet zichzelf vergelijken met X-1 elementen, in elk geval!

Er moet toch nog een betere manier te vinden zijn

[H!GHGuY]

ja, je moet altijd een afweging maken: kan de ergste situatie voorkomen?

In mijn geval is de bovengrens dan O(n²).
Bij een normaal union-find is dit O(n²lg n). Aangezien je je equivalentie per elke 2 elementen zal moeten geven.

Misschien ben je dan beter af als je adhv de regels een uniek getal definieert per partitie. Dit sorteer je dan in O(n lg n).

Veel is dus afhankelijk van het aantal partities dat je verwacht. Is er een manier om die bij jou te voorspellen/schatten?

[-FoX-]

Voorspellen is moeilijk.. maar de kans is reëel dat het dikwijls om grote aantallen zal gaan; waar slechts kleinere paren gemaakt zullen worden. Dit is echter moeilijk in te schatten.

Ik heb ook al gedacht om een soort van B-Tree implementatie te maken, adhv de regels, door hier een unieke waarde voor te genereren. Maar ik weet niet of ik hier wel goed aan doe.

Aan de hand van de door mij voorgestelde gegevens, welke implementatie zou jij dan kiezen?

[H!GHGuY]

Als jij een unieke waarde wil maken per partitie dan moet je toch het aantal groepen impliciet ook kennen? Het kan misschien wel zo zijn dat je niet alle partities zal opvullen.

Die andere mogelijkheid, waarbij je een unieke waarde genereert per partitie is O(lg n) per element.
Je kan nl een hash-tabel op die unieke waarden gooien en daaraan een gesorteerde lijst/boom hangen.
Wat je voorbereidend werk is daarentegen...

Er zijn nog wel andere mogelijkheden te bedenken hoor. Als je per groep een object zou hebben die true/false geeft per element, dan kun je met elk zo'n object alle resterende transacties overlopen en gaan groeperen. das dan O(n*m) met m het aantal groeperende objecten.

Wat me net te binnen schiet en waarschijnlijk ook niet onbelangrijk is:
kan een transactie tot meerdere groepen behoren ? Want je sprak over een hierarchische structuur. Kunnen groepen hierin genest zijn ?

[-FoX-]

HIGHGuY schreef op woensdag 07 juni 2006 @ 08:21:
Als jij een unieke waarde wil maken per partitie dan moet je toch het aantal groepen impliciet ook kennen? Het kan misschien wel zo zijn dat je niet alle partities zal opvullen.

Waarom is dat nodig? Als iedere groep uniek aangeduidt kan worden, lijkt me dit toch geen probleem? Alhoewel het misschien geen echt goede oplossing is.

Die andere mogelijkheid, waarbij je een unieke waarde genereert per partitie is O(lg n) per element.
Je kan nl een hash-tabel op die unieke waarden gooien en daaraan een gesorteerde lijst/boom hangen. Wat je voorbereidend werk is daarentegen...

Er zijn nog wel andere mogelijkheden te bedenken hoor. Als je per groep een object zou hebben die true/false geeft per element, dan kun je met elk zo'n object alle resterende transacties overlopen en gaan groeperen. das dan O(n*m) met m het aantal groeperende objecten.

Wat me net te binnen schiet en waarschijnlijk ook niet onbelangrijk is:
kan een transactie tot meerdere groepen behoren ? Want je sprak over een hierarchische structuur. Kunnen groepen hierin genest zijn ?

Nee, een transactie kan maar tot 1 groep behoren. De groepen kan je een beetje zien als een bulk-operation voor die set van transacties.

[Confusion]

Is het niet efficienter om eerst te sorteren volgens bepaalde criteria en vervolgens de lijst af te lopen? Dan hoef je alleen bij 'overgangen' naar een nieuwe soort, of wanneer de vorige groep vol is, een actie te ondernemen, in plaats van bij ieder element een actie te ondernemen. In feite sorteer je meerdere keren als je telkens van ieder element gaat kijken in welke basket het hoort, terwijl je met eerst sorteren al weet dat in de 'huidige' basket hoort.

[ Voor 11% gewijzigd door Confusion op 07-06-2006 09:26 ]

[-FoX-]

Confusion schreef op woensdag 07 juni 2006 @ 09:26:
Is het niet efficienter om eerst te sorteren volgens bepaalde criteria en vervolgens de lijst af te lopen? Dan hoef je alleen bij 'overgangen' naar een nieuwe soort, of wanneer de vorige groep vol is, een actie te ondernemen, in plaats van bij ieder element een actie te ondernemen. In feite sorteer je meerdere keren als je telkens van ieder element gaat kijken in welke basket het hoort, terwijl je met eerst sorteren al weet dat in de 'huidige' basket hoort.

Dat is een mogelijke oplossing die ik in mijn openingspost reeds aanhaalde. Op zich lijkt me dit nog niet zo'n slecht idee.. je hangt dan wel af van het Collections sorteringsalgorithme (mergesort n log(n)). Grote voordeel is dat je zelf geen complexe operaties meer moet schrijven, enkel een gepaste comparator voor de gesorteerde elementen.

Misschien dat ik hier wel voor zal gaan; tenzij er iemand bezwaren tegen heeft?

[Confusion]

Ah, te snel door de openingspost gelezen .

Beter dan n log(n) lukt je AFAIK niet, tenzij je informatie aan je systeem toevoegt waardoor al een bepaalde ordening ontstaat. Zolang een willekeurig aantal objecten in een willekeurige volgorde staat, zal het sorteren n log(n) vergen.

Die mergesort lijkt me juist voor dit soort gevallen bedoeld. De beste manier om efficientie te winnen is misschien wel donders goed opletten bij het schrijven van je compareTo methode?

[-FoX-]

Confusion schreef op woensdag 07 juni 2006 @ 10:07:
Die mergesort lijkt me juist voor dit soort gevallen bedoeld. De beste manier om efficientie te winnen is misschien wel donders goed opletten bij het schrijven van je compareTo methode?

Wat bedoel je met opletten?

[H!GHGuY]

hij bedoelt dat je een efficiente compareTo moet schrijven.

Wat ik bedoel:
Als je je partities op voorhand gaat nummeren dan is het vanuit perspectief van union-find alsof je voor elke groep 1 equivalent element voorop zet/aanmaakt.
met andere woorden: je kent op dat moment ook het exacte aantal partities.

laten we effe rekenen voor je: (e leg ik later uit, stel op dit moment e=1)

Stel bijvoorbeeld dat van je n=10.000 transacties uiteindelijk m=50 groepen overblijven.
Bij de aangepaste union-find moet je rekenen op O(nm) vergelijkingen. Per toevoeging heb je lg(n) werk om je groep gesorteerd op te bouwen volgens jouw sorteringscriteria.
geheel: O(enm lg(n)) = 10.000*50*100 = 50.000.000

Maak je op voorhand je partities aan en blijken er l=O(n)=1000 mogelijke partities te zijn dan heb je
O(l²) vergelijkingen gedaan om je partities op te stellen.
Daarna moet je elk element met mogelijk alle partities vergelijken. O(n*l)
en eenmaal toevoegen is weerom O(lg(n))
dus O(el² + n(el+lg(n))) = 1.000.000 + 10.000(1000 + 100) = 12.000.000

gebruik je nummers + hashmap dan is eenmaal de partities gemaakt (dit is hashtabel aanmaken met juiste grootte en de juiste gegevensstructuren er in aanbrengen):
O(1) om te zoeken. O(lg(n)) om toe te voegen.
dus O(el² + en lg(n)) = 1.000.000 + 10.000*100 = 2.000.000

maak je niet bestaande partities aan als je ze nodig hebt (met het risico je Hashtabel te moeten rehashen, hoewel weinig waarschijnlijk):
O(en lg(n)) = 1.000.000

LET OP:
hierbij heb ik gerekend dat
A ) het aanmaken van een hashcode voor een transactie adhv de regels een O(1) operatie is.
B ) het vergelijken en opstellen van een partitie (of een vertegenwoordiger ervan) een O(1) operatie is.

ik heb nadien in de formules e toegevoegd. e = efficientie van vergelijken adhv regels of hashcode aanmaken

C ) het aantal mogelijke partities groter is dan het aantal effectief gebruikte in het nadeel voor de laatste methoden.
D ) Dit zijn natuurlijk ergste performanties + in O() notatie. Bij de eerste (aangepaste union-find) kan je bijvoorbeeld een heuristiek toevoegen dat je lijst met groepen volgens dalend aantal transacties gesorteerd is. Hierdoor kan je het aantal vergelijkingen gemiddeld terugbrengen tot een fractie van het aantal groepen. (vb. 5 ipv 50 zodat O(...) = 5.000.000)

In realiteit en afhankelijk van het aantal regels kan dit dus tegenvallen, maar het lijkt me onoverkomelijk aangezien je per transactie de regels erbij zal moeten betrekken.

Ik denk dat het je onderhand begint duidelijk te worden