Hallo zusammen,
ich habe ein Problem mit einer rekursiven Methode. Die Anwendung ist eine Huffman Codierung mit einer Spezialform des Package Merge (nach Turpin und Moffat).
Der stack overflow kommt dadurch zustande, dass ich einen beliebig tief geschachtelten Baum von "Packages" habe, den ich, von der Wurzel aus, rekursiv durchgehen muss um die Auftrittshäufigkeit einzelner Werte zu zählen.
Mir ist klar, dass Iteration in Java immer der Rekursion vorzuziehen ist, aber für diese spezielle Struktur kann ich keine vollständig iterative Lösung bauen, weil die Bäume beliebig tief verschachtelt sein können. Oder habe ich hier etwas übersehen??
Eine Reduktion der Iterationstiefe habe ich bereits versucht, jedoch hat das auch nicht viel bewirkt und ich möchte eine wasserdichte Lösung bzw brauche sie... Dementsprechend ist auch eine simple vergrößerung des Stack nicht sinnvoll, weil ich ggf sehr große Datenmengen codieren muss...
Nachfolgend die Struktur des Package Objekts...
Der Stackoverflow passiert dann in der folgenden Methode...
Ich bin wirklich für jeden Ansatz dankbar...
ich habe ein Problem mit einer rekursiven Methode. Die Anwendung ist eine Huffman Codierung mit einer Spezialform des Package Merge (nach Turpin und Moffat).
Der stack overflow kommt dadurch zustande, dass ich einen beliebig tief geschachtelten Baum von "Packages" habe, den ich, von der Wurzel aus, rekursiv durchgehen muss um die Auftrittshäufigkeit einzelner Werte zu zählen.
Mir ist klar, dass Iteration in Java immer der Rekursion vorzuziehen ist, aber für diese spezielle Struktur kann ich keine vollständig iterative Lösung bauen, weil die Bäume beliebig tief verschachtelt sein können. Oder habe ich hier etwas übersehen??
Eine Reduktion der Iterationstiefe habe ich bereits versucht, jedoch hat das auch nicht viel bewirkt und ich möchte eine wasserdichte Lösung bzw brauche sie... Dementsprechend ist auch eine simple vergrößerung des Stack nicht sinnvoll, weil ich ggf sehr große Datenmengen codieren muss...
Nachfolgend die Struktur des Package Objekts...
Java:
import java.util.*;
public class Package implements Comparable<Package>{
int freq;
int sign;
Package[]children;
static int amount=0;
/** Erzeugt einen Package Knoten ohne Kinder
*
*/
public Package(){
int freq=0;
int sign=0;
children=new Package[0];
}
/** Erzeugt einen Package Knoten mit einem Kind
*
* @param child
*/
public Package(Package child){
int freq=child.freq;
int sign=0;
children=new Package[1];
children[0]=child;
}
/**Erzeugt einen Package Knoten mit mehreren Kindern (Package Array)
*
* @param children
*/
public Package(Package []children){
int freq=0;
int sign=0;
this.setChildren(children);
}
/**Erzeugt einen Package Blatt - children[]=null
*
* @param freq
* @param sign
*/
public Package(int freq, int sign){
this.freq=freq;
this.sign=sign;
children=new Package[0];
}
// Es folgen getter und Setter usw....
Der Stackoverflow passiert dann in der folgenden Methode...
Java:
public void amountSign(int sign){
if(this.children.length==0){
if(this.sign==sign)
amount++;
}else
{
for(int i=0;i<this.children.length;i++){
this.children[i].amountSign(sign);
}
}
}
Ich bin wirklich für jeden Ansatz dankbar...