[Java] Algoritme voor nesten

[Standeman]

Dit is niet echt een Java probleem, maar meer algemeen. Aangezien ik het wel met Java op wil lossen heb ik het er even bij gezet.

Het komt er op neer dat ik groepen wil nesten en ik ben op zoek naar een redelijk efficiente manier hiervoor. Ik zal even mijn probleem uitleggen:

ik heb een java.util.List met waarin meerdere keren het volgende object in voorkomt:

code:

public class Group {
  private String groupid;  //unique id, not sequential
  private String parentid; //id of the parentgroup
  private List groups //The groups in this group
  private .....
  etc, etc
}

De lijst met groepen komt uit een SQL DB, het is de bedoeling dat de lijst met groepen genest gaat worden (als een tree), bijvoorbeeld

huidige situatie:
group 1.2
group 1.1
group 1.1.2
group 2.2
group1
group 1.4
group 1.3
group2
group 1.1.1
group 2.1
etc


nieuw situatie:
group1
| - group 1.1
| |- group 1.1.1
| |- group 1.1.2
| - group 1.2
| - group 1.3
| - group 1.4
group2
| - group 2.1
| - group 2.2
etc

(groep nummers zijn niet representatief, is meer zo van "fj4gfj40g8u43". Er zit geen info in verwerkt van de verwachte locatie in de tree)

Theoretisch gezien kan het nesten zo'n beetje oneindig door gaan.

Uiteraard kan ik 100x (of iig heelveel x) die lijst doorlopen totdat ik het geheel heb opgebouwd, maar dat lijkt me niet het meest efficient.

Kan iemand mij op weg helpen (kan me niet voorstellen dat ik de eerste ben die met dit probleem zit ). bijv door een verwijzing naar een desingpattern o.id. of gewoon een slim idee.
Ik heb overigens al in omega en google gezocht, maar niets gevonden

[ Voor 15% gewijzigd door Standeman op 30-06-2004 11:51 . Reden: uitgebreid ]

[Creepy]

* Creepy gokt op recursie

[Blizard]

http://www.exciton.cs.ric...ignPatterns/composite.htm
Ik denk dat je wel wat kan met het Composite-Pattern ?!

En dan iets meer naar code-gerichte uitleg :
http://www.javaworld.com/...-0913-designpatterns.html

[Alarmnummer]

Standeman schreef op 30 juni 2004 @ 11:44:
Het komt er op neer dat ik groepen wil nesten en ik ben op zoek naar een redelijk efficiente manier hiervoor. Ik zal even mijn probleem uitleggen:

Uiteraard kan ik 100x (of iig heelveel x) die lijst doorlopen totdat ik het geheel heb opgebouwd, maar dat lijkt me niet het meest efficient.

Ik neem aan dat je met efficient bedoelt de opzoek tijd. De meest snelle opzoek tijd hiervoor kan hiervoor contstant zijn (dus onafhankelijk van het aantal groepen). Wat je zou kunnen doen is op basis van een key bv "1.3.41.3.4" een groep plaatsen in een map structuur. Je kan dan ranzigsnel een groep op basis van zijn key ophalen.

Er gaan echter meer wegen naar Rome en er zijn dus veel meer oplossingen. Je zou ook een tree (recursieve datastructuur: ik gok in het 1 blok van het 1e jaar informatica) kunnen gebruiken.

rootGroup.getGroup("1").getGroup("5").getGroup("9")

voor de groep: 1.5.9

Kan iemand mij op weg helpen (kan me niet voorstellen dat ik de eerste ben die met dit probleem zit ). bijv door een verwijzing naar een desingpattern o.id. of gewoon een slim idee.

Dit is gewoon een klassiek stukje datastructuur. Dus niet meteen aankomen zetten met design patterns.

[ Voor 6% gewijzigd door Alarmnummer op 30-06-2004 11:59 ]

[Alarmnummer]

Blizard schreef op 30 juni 2004 @ 11:52:
http://www.exciton.cs.ric...ignPatterns/composite.htm
Ik denk dat je wel wat kan met het Composite-Pattern ?!

Je kan er hele mooie dingen mee, maar het heeft niets te maken met dit probleem. Het idee achter het composite design patterns is dat een uniforme interface hebt voor een enkel object of voor een compositie van objecten, en daar is hier dus (nog) geen sprake van.

[ Voor 11% gewijzigd door Alarmnummer op 30-06-2004 12:05 ]

[Blizard]

Inderdaad, ik had het probleem verkeerd begrepen

[Standeman]

Dit is gewoon een klassiek stukje datastructuur. Dus niet meteen aankomen zetten met design patterns.

In principe is dit een vrij standaard probleem en vaak is daar wel een "soort" van pattern (standaard oplossing zeg maar) voor te vinden

Het grote probleem was dat de lijst met groupen vrijwel random is opgebouwd. Hierdoor kon ik niet zomaar een group opzoeken (misshien zit deze genest, misschien niet, etc).

Maar ik heb het iig opgelost met de volgende code:

code:

    private static List nestGroups(List groups) {
        Iterator iGroups = groups.iterator();
        List returnList = new ArrayList();

        while (iGroups.hasNext()) {
            Group group = (Group) iGroups.next();
            if (group.getParentGroupId() == null) { //is een "root group"
                returnList.add(group);
                iGroups.remove();
            }
        }

        Iterator iReturnList = returnList.iterator();
        while (iReturnList.hasNext()) {
            Group group = (Group) iReturnList.next();
            group = getSiblings(group, groups);
        }
        return returnList;
    }

    private static Group getSiblings(Group parent, List groups) {
        Iterator iGroups = groups.iterator();
        while (iGroups.hasNext()) {
            Group possibleSibling = (Group) iGroups.next();
            if (parent.getGroupId().equals(possibleSibling.getParentGroupId())) {
                possibleSibling = getSiblings(possibleSibling, groups);
                parent.add(possibleSibling);
            }
        }
        return parent;
    }

Ik zit me alleen nog af te vragen of het niet makkelijker (lees efficienter / sneller) kan
(Of zit ik nu stomme dingen te doen in de code?? Kheb namelijk nog niet zo gek veel programmeer ervaring)

[Soultaker]

In je huidige oplossing loop je de hele lijst voor elke groep opnieuw door. Dat lijkt me vrij overbodig. Aangezien je al handige keys kun je waarschijnlijk gewoon een Map (HashMap lijkt me heel geschikt) gebruiken.

Ik weet niet hoe ver je bent met Java, maar een Map is en container object waarin je waarden opslaat met een bepaalde key en ook aan de hand van die key weer kunt ophalen. In dit geval kun je die gebruiken om dat Group objecten op te slaan met hun groupid-attribuut als key, zodat je ze ook aan de hand van hun id makkelijk op kunt zoeken.

Het groeperen gaat dan in twee stappen; eerst het vullen van de hashmap en daarna die hashmap gebruiken om de group objecten elk aan hun parent group toe te voegen.

In (pseudo-)code:

code:

HashMap groupmap = new HashMap();
Iterator i;

i = groups.iterator();
while( i.hasNext() )
{
    Group group = (Group)i.next();
    groupmap.put( group.getGroupId(), group );
}

i = groups.iterator();
while( i.hasNext() )
{
    Group group = (Group)i.next();
    String parentid = group.getParentGroupId();
    if(parentid)
        ((Group)groupmap.get(parentid)).groups.add( group );
}

[Alarmnummer]

Standeman schreef op 30 juni 2004 @ 16:07:
[...]
In principe is dit een vrij standaard probleem en vaak is daar wel een "soort" van pattern (standaard oplossing zeg maar) voor te vinden

Jij moet Patterns in Java van Mark Grand gaan lezen. Daarin is ook echt alles een pattern. Ik zou dit dus geen pattern willen noemen.

[Robtimus]

Soultaker schreef op 30 juni 2004 @ 16:18:

code:

HashMap groupmap = new HashMap();

Ga je ff diep schamen. Declareren als HashMap ipv Map...

[Standeman]

@soultaker,
hmmmm.. dat is inderdaad een stuk beter. Het loopt ook aardig wat sneller dan mijn code, dus thanks.

@Alarmnummer
Je hebt gelijk, het is ook geen pattern. Ik heb inmiddels Volume 1 van Grand thuisliggen, nu nog een keer de tijd nemen om het ook inderdaad te lezen

[Alarmnummer]

Standeman schreef op 01 juli 2004 @ 13:38:
@soultaker,
hmmmm.. dat is inderdaad een stuk beter. Het loopt ook aardig wat sneller dan mijn code, dus thanks.

@Alarmnummer
Je hebt gelijk, het is ook geen pattern. Ik heb inmiddels Volume 1 van Grand thuisliggen, nu nog een keer de tijd nemen om het ook inderdaad te lezen

Uhhh.. misschien dat je het nog kan terug brengen, want het is een snertboek. Bij hem is echt alles een pattern: interface pattern, abstract class pattern. En dat is een beetje het probleem de laatste tijd met het hele pattern gebeuren. Iedereen probeert een graantje mee te pikken door alles maar een pattern te noemen en dat is een hele slechte zaak.

Als je een boek wilt kopen over patterns dan moet je Design Patterns - Elements of Reuseable Object-Oriented Software en Design Patterns Explained: A New Perspective on Object-Oriented Design bekijken. De laatste is trouwens iets leesbaarder dan de 1e en er worden nagenoeg dezelfde patterns in behandeld.

Verder is doorlezen van zo`n boek niet voldoende. Je moet ze ook toepassen en je moet de kennis ook onderhouden. Regelmatig zul je nog een keer terug het boek moeten inspringen voor de puntjes op de i of voor een diepere kennis.

[ Voor 11% gewijzigd door Alarmnummer op 01-07-2004 13:52 ]

[Robtimus]

Alarmnummer schreef op 01 juli 2004 @ 13:50:
Design Patterns - Elements of Reuseable Object-Oriented Software

Van de gang of four , dat boek hoort zo ongeveer thuis op je boekenplank.

[Alarmnummer]

IceManX schreef op 01 juli 2004 @ 14:10:
[...]
Van de gang of four , dat boek hoort zo ongeveer thuis op je boekenplank.

Op de boekenplank staan alleen de boeken die ik niet lees

[Soultaker]

IceManX schreef op 01 juli 2004 @ 10:38:
Ga je ff diep schamen. Declareren als HashMap ipv Map...

Het is een lokale variable, dus dan moet dat kunnen, vind ik.

[Standeman]

Alarmnummer schreef op 01 juli 2004 @ 13:50:
[...]


Uhhh.. misschien dat je het nog kan terug brengen, want het is een snertboek. Bij hem is echt alles een pattern: interface pattern, abstract class pattern. En dat is een beetje het probleem de laatste tijd met het hele pattern gebeuren. Iedereen probeert een graantje mee te pikken door alles maar een pattern te noemen en dat is een hele slechte zaak.

Als je een boek wilt kopen over patterns dan moet je Design Patterns - Elements of Reuseable Object-Oriented Software en Design Patterns Explained: A New Perspective on Object-Oriented Design bekijken. De laatste is trouwens iets leesbaarder dan de 1e en er worden nagenoeg dezelfde patterns in behandeld.

Verder is doorlezen van zo`n boek niet voldoende. Je moet ze ook toepassen en je moet de kennis ook onderhouden. Regelmatig zul je nog een keer terug het boek moeten inspringen voor de puntjes op de i of voor een diepere kennis.

Even een vraagje dan, wat is dan een definitie van een pattern? Een pattern is toch een gestandaardiseerde oplossing voor een veel voorkomend probleem? Of zit ik nu echt helemaal fout te denken

[Soultaker]

In principe wel, maar niet elke oplossing voor een veelvoorkomend probleem is een pattern. Met design patterns probeer je programmeerervaring te formaliseren. Ze zijn dan vooral bedoelt om ontwerpen te kunnen bepalen en motiveren die niet direct voor de hand liggen.