Hallo Community,
ich benötige alle sog. "Partitionen der Länge x einer natürlichen Zahl n". Auf gut deutsch sind das alle möglichen Summenzerlegungen einer bestimmten Zahl, wobei auch die Null vorkommen darf. Kleines Beispiel:
Zur Veranschaulichung kann man sich vorstellen, n Kugeln in x Urnen zu verteilen. Ich habe mir einen Algorithmus überlegt, der genau nach obigem Beispiel vorgeht. Zuerst werden alle Kugeln in die Urne ganz links gelegt, dann wird eine Kugel aus dieser Urne herausgenommen und in alle Urnen rechts davon gelegt. Dieser Vorgang wird rekursiv für alle Ergebnisse wiederholt:
Hinweis: das Programm sollte mit den Optionen -Xms512m -Xmx512m gestartet werden, es benötigt ein bisschen Speicher :shock:
Um Dubletten zu erkennen benutze ich ein HashSet, in dem ich mir alle bereits vorgekommenen Kombinationen merke. Ansonsten ist der Code denke ich selbsterklärend.
Wenn man das Programm mal laufen lässt, erkennt man mein Problem...bei größeren Zahlenkombinationen wird das ganze recht zäh. Das Kernproblem liegt meiner Ansicht nach klar auf der Hand...bei größeren Kombinationen Kugeln / Urnen wird das Hashset recht groß, und die Lookups dauern ihre Zeit.
Wie könnte ich den Algorithmus noch tunen??? An der hashCode Methode schrauben? In der Doku steht, ein HashSet sei bei einer eindeutigen Hashfunktion am schnellsten, allerdings sollte die Hashfunktion auch schnell sein. Lohnt es sich, da noch mehr zu experimentieren?
Oder bin ich auf dem völlig falschen Dampfer und es gibt eine performantere und speichersparendere Art und Weise, die Dubletten zu vermeiden?
Des weiteren bin ich etwas verwundert über die Speicherfreigabe. Das Programm nimmt sich ziemlich schnell die 512 MB Speicher und dümpelt dann an dieser Obergrenze rum. Ich habe den Eindruck, der Speicher wird sehr selten freigegeben. gc ist ja ein Thema für sich, Java macht das lieber selbst. Eigentlich sollte ja nach jedem Schleifendurchlauf das alte Partitioner-Objekt nicht mehr referenziert werden, der Speicher könnte wieder freigegeben werden. Ist aber anscheinend nicht wirklich so...Kann ich da auch noch was optimieren?
Ich bin für jederlei Anregung offen...danke schonmal für die Mühe...
Grüße Louis
ich benötige alle sog. "Partitionen der Länge x einer natürlichen Zahl n". Auf gut deutsch sind das alle möglichen Summenzerlegungen einer bestimmten Zahl, wobei auch die Null vorkommen darf. Kleines Beispiel:
Code:
n = 3, x = 4
Ergebnis:
3 0 0 0
2 1 0 0
2 0 1 0
2 0 0 1
1 2 0 0
1 1 1 0
1 1 0 1
1 0 2 0
1 0 1 1
1 0 0 2
0 3 0 0
0 2 1 0
0 2 0 1
0 1 2 0
0 1 1 1
0 1 0 2
0 0 3 0
0 0 2 1
0 0 1 2
0 0 0 3Zur Veranschaulichung kann man sich vorstellen, n Kugeln in x Urnen zu verteilen. Ich habe mir einen Algorithmus überlegt, der genau nach obigem Beispiel vorgeht. Zuerst werden alle Kugeln in die Urne ganz links gelegt, dann wird eine Kugel aus dieser Urne herausgenommen und in alle Urnen rechts davon gelegt. Dieser Vorgang wird rekursiv für alle Ergebnisse wiederholt:
Code:
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class Partitioner implements Iterator<int[]> {
protected Queue<PartitionerState> queue;
protected HashSet<PartitionerState> visitedStates;
protected int balls;
protected int buckets;
public Partitioner( int balls, int buckets ) {
queue = new LinkedList<PartitionerState>();
visitedStates = new HashSet<PartitionerState>();
this.balls = balls;
this.buckets = buckets;
//in the beginning all balls are in the most left bucket
int[] start = new int[buckets];
start[0] = balls;
queue.offer( new PartitionerState(start) );
}
public boolean hasNext() {
return ! queue.isEmpty();
}
public int[] next() {
return enqueue();
}
public void remove() {
throw new IllegalArgumentException("method remove() not implemented");
}
private int[] enqueue() {
PartitionerState state = null;
if (!queue.isEmpty()) {
state = queue.poll();
//get first bucket not zero
int i=0;
for (; i<state.buckets.length; i++) {
if (state.buckets[i]>0)
break;
}
//take a ball from the found bucket and put it in every
//bucket right hand to this one
for (int j=i; j<buckets; j++) {
int[] tempBucket = (int[]) state.buckets.clone();
tempBucket[i] -= 1;
if (j+1<tempBucket.length) {
tempBucket[j+1] += 1;
PartitionerState newState = new PartitionerState(tempBucket);
if ( !visitedStates.contains(newState) ) {
queue.offer(newState);
visitedStates.add(newState);
}
}
}
}
return state.buckets;
}
public static void main( String[] args ) throws Exception {
int maxBalls = 15;
int maxBuckets = 15;
for (int balls=1; balls <= maxBalls; balls++) {
for (int buckets = 1; buckets <= maxBuckets; buckets++) {
System.out.print(balls + " balls in " + buckets + " buckets: ");
Partitioner p = new Partitioner(balls, buckets);
long start = System.currentTimeMillis();
int i=0;
while ( p.hasNext() ) {
int[] partition = (int[]) p.next();
i++;
}
long diff = System.currentTimeMillis() - start;
System.out.println(i + " partitions, duration: " + diff + " ms");
}
}
}
}
class PartitionerState {
protected int[] buckets;
public PartitionerState( int[] buckets ) {
this.buckets = buckets;
}
public boolean equals( Object other ) {
PartitionerState s = (PartitionerState) other;
for( int i=0; i<this.buckets.length; i++ ) {
if ( this.buckets[i] != s.buckets[i] ) {
return false;
}
}
return true;
}
public int hashCode() {
int hash = 0;
int m = 1;
for( int i=0; i<buckets.length; i++ ) {
hash += m * buckets[i];
m *= 2;
}
return hash;
}
}Hinweis: das Programm sollte mit den Optionen -Xms512m -Xmx512m gestartet werden, es benötigt ein bisschen Speicher :shock:
Um Dubletten zu erkennen benutze ich ein HashSet, in dem ich mir alle bereits vorgekommenen Kombinationen merke. Ansonsten ist der Code denke ich selbsterklärend.
Wenn man das Programm mal laufen lässt, erkennt man mein Problem...bei größeren Zahlenkombinationen wird das ganze recht zäh. Das Kernproblem liegt meiner Ansicht nach klar auf der Hand...bei größeren Kombinationen Kugeln / Urnen wird das Hashset recht groß, und die Lookups dauern ihre Zeit.
Wie könnte ich den Algorithmus noch tunen??? An der hashCode Methode schrauben? In der Doku steht, ein HashSet sei bei einer eindeutigen Hashfunktion am schnellsten, allerdings sollte die Hashfunktion auch schnell sein. Lohnt es sich, da noch mehr zu experimentieren?
Oder bin ich auf dem völlig falschen Dampfer und es gibt eine performantere und speichersparendere Art und Weise, die Dubletten zu vermeiden?
Des weiteren bin ich etwas verwundert über die Speicherfreigabe. Das Programm nimmt sich ziemlich schnell die 512 MB Speicher und dümpelt dann an dieser Obergrenze rum. Ich habe den Eindruck, der Speicher wird sehr selten freigegeben. gc ist ja ein Thema für sich, Java macht das lieber selbst. Eigentlich sollte ja nach jedem Schleifendurchlauf das alte Partitioner-Objekt nicht mehr referenziert werden, der Speicher könnte wieder freigegeben werden. Ist aber anscheinend nicht wirklich so...Kann ich da auch noch was optimieren?
Ich bin für jederlei Anregung offen...danke schonmal für die Mühe...
Grüße Louis
