[Java] Stackoverflow in Windows, niet in Linux

[Hielko]

Ik heb een simpele binaire boom data structuur gemaakt. Het probleem is wanneer ik hier een flinke gesorteerde woordenlijst in gooi hij na enkele seconden een stackoverflow error geeft (bij een gesorteerde lijst als invoer wordt een binaire boom erg diep). Het vreemde is dat onder Linux hij dit echter wel kan.

Het testbestand met een gesorteerde lijst van woorden is 160kb groot wat dus niet werkt onder windows xp. Een ongesorteerde lijst van 1,6MB past echter wel zonder probleem in de Binaire boom. Het lijkt er dus op dat de stackbuffer in windows somehow kleiner is dan in linux????

Voor de volledigheid, de code:

De eigenlijke boom:

Java:

class BinNode {
  
  BinNode links, rechts;
  String element;
 
  BinNode () {
    links = null;
    rechts = null;
    element = null;
  } // constructor
    
  public void voegtoe (String woord) {
    BinNode nieuw = zoek(woord);
    if (nieuw.element == null) {
        // System.out.println(woord);
        nieuw.element = woord;
        nieuw.links = new BinNode();
        nieuw.rechts = new BinNode();
    } 
  } // voegtoe
  
  public BinNode zoek (String woord) {
    
    if (element == null) {
      return this;
    } else if (element.compareTo(woord) > 0) {
      return rechts.zoek(woord);
    } else if (element.compareTo(woord) < 0) {
      return links.zoek(woord);
    }
    return this;
  } // zoek
  
}

De class die gegevens in de boom stopt:

Java:

/*
 * @(#)Binboom.java 1.0 03/11/19
 *
 */
 
import java.io.*;
import local.*;
 
class Binboom {
  
  static BinNode wortel = new BinNode();
  
  public static void main(String args[]) {
    
    try{
      String s = args[0];
      
      // String s = "test.txt";
      
      Reader r = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
      StreamTokenizer st = new StreamTokenizer(r);
      st.lowerCaseMode(true);
      st.whitespaceChars(',','.');
      st.nextToken();
      while (st.ttype != StreamTokenizer.TT_EOF) {
        if (st.ttype==StreamTokenizer.TT_WORD) {
          // System.out.println(st.sval);
          wortel.voegtoe(st.sval);
        }
        st.nextToken();
      }
    } catch(Exception e) {
      e.printStackTrace();
    }
    
    
    while (true) {
      System.out.print("Geef het woord dat opgezocht moet worden: ");
      Extractor inv = new Extractor();
      String zoekwoord = inv.readString();
      BinNode test = wortel.zoek(zoekwoord);
      if (test.element == null) {
        System.out.println("Niet gevonden");
      } else {
        System.out.println("Wel gevonden");
      }
    }
    
    
    } // main
    
}

[ACM]

Je krijgt met een gesorteerde lijst dan zeker een boom van n elementen diep?
Dat lijkt me sowieso niet heel handig (dan heb je gewoon een linked list), maar is geloof ik niet echt eenvoudig te voorkomen.

En het probleem lijkt me niet de stackgrootte, want in zo'n geval zal je daar met je zoek()-methode ook tegenaanlopen als je een iets langere gesorteerde lijst hebt.

't Probleem zit hem er natuurlijk in dat de gesorteerde term altijd links (of rechts) wordt geplaatst en daardoor de boom alleen die kant op groeit.
Je zou kunnen kijken of je een algortime kan vinden/toepassen dat je boom gebalanceerd houdt, dan treed dit probleem veel minder snel op maar wordt het allemaal wel wat slomer om te inserten (wel sneller om te doorzoeken).

[Hielko]

Met een gesorteerde lijst krijg je inderdaad een boom van n elementen diep. Dat is inderdaad niet handig, maar in Linux werkt het wel, dus in Windows zou het toch ook moeten werken.

Het probleem lijkt mij eerlijk gezegt wel de stackgrootte, want waarom zou ie anders als error geven: "Expetion in Thread "main" Java.lang.stackOverflowError" (dit is ook het enige wat ie terug geeft als error). Waarom het bij die andere, langere, lijst dus wel goed gaat is het feit dat daar de invoer ongeveer random is en de boom dus lang niet zo diep wordt.

[curry684]

ACM schreef op 04 december 2003 @ 14:15:
En het probleem lijkt me niet de stackgrootte, want in zo'n geval zal je daar met je zoek()-methode ook tegenaanlopen als je een iets langere gesorteerde lijst hebt.

Niet gegarandeerd, het is namelijk 'bad practice' om een zoekfunctie in een platte lijst recursief aan te pakken: [rml]curry684 in "[ C] linked list traversal optimalisatie"[/rml]

Je kunt een binaire boom overigens met wat moeite ook heel simpel non-recursief uitlezen (moet je alleen een lokale stack bijhouden van nestings).

[Janoz]

Stack overflow komt inderdaad door het hoge aantal recursieve aanroepen. Probeer voor de gein eens het aantal niveau's af te drukken zodat je weet waneer je de stack overflow krijgt

Waarschijnlijk is dit op te lossen door een grotere stacksize mee te geven aan java (met de -Xss optie ofzo).

Om ervoor te zorgen dat je boom wat gebalanceerd blijft kun je red black trees gebruiken. Hierin is de kortste weg van root naar leaf gegarandeerd nooit korter dan de helft van de langste weg. De insert en delete operaties zijn nog steeds O(logN) (O(1) voor inster en delete zelf en O(logN) voor zoeken naar lokatie) en voor de rest is het hetzelfde als een gewone binaire boom.

[ACM]

Ja, dat begrijp en bedoel ik

Maar het basisprobleem is dat je Tree geen gebalanceerde Tree is, maar min of meer een Linked List is geworden. Elke toevoeging die je doet vergt dus k+1 zoek()-aanroepen (waarbij k het ingevoerde aantal elementen is).

Dat het in Linux wel goed gaat komt alleen maar omdat je gesorteerde lijst niet lang genoeg is om daar de Stack van te vullen, blijkbaar, niet omdat de Stack zoveel langer is als in Windows.
En dus zul je ook in Linux op een gegeven moment tegen de callstack-limiet aanknallen, terwijl je dat grotendeels kan voorkomen door de boom netjes gebalanceerd te houden.

Stel X is de stackgrootte, dan kan je nu in worst-case (een gesorteerde lijst) maximaal X elementen toevoegen voor je een exception krijgt.
Bij een gebalanceerde boom is dat 2 ^ X (2 tot de macht X), aardig wat meer

[.oisyn]

ACM schreef op 04 december 2003 @ 14:15:
Je krijgt met een gesorteerde lijst dan zeker een boom van n elementen diep?
Dat lijkt me sowieso niet heel handig (dan heb je gewoon een linked list), maar is geloof ik niet echt eenvoudig te voorkomen.

gebruik gebalanceerde boomalgoritmes, zoals AVL trees of red-black trees. Dan is het opzoeken ook gelijk altijd O (log n)

.edit: bliep, spuit 11, ik had de laatste 2 reacties nog niet gezien

[ Voor 13% gewijzigd door .oisyn op 04-12-2003 14:48 ]

[curry684]

.oisyn schreef op 04 december 2003 @ 14:46:
[...]
gebruik gebalanceerde boomalgoritmes, zoals AVL trees of red-black trees. Dan is het opzoeken ook gelijk altijd O (log n)

Mjah, als je een gesorteerde lijst van 1 miljoen elementen op de botst mogelijke manier in een boom stopt zul je inderdaad een boom van 1 miljoen nestings krijgen die allemaal 1 leaf hebben, dan krijg je wel een stackoverflow

Maar wat is er mis met een linked list?

[ACM]

Een linked list is niet zo erg, maar zoekt zo langzaam
Zeker als je die recursief gaat proberen te doorzoeken.

[Janoz]

curry684 schreef op 04 december 2003 @ 14:48:
[...]

Mjah, als je een gesorteerde lijst van 1 miljoen elementen op de botst mogelijke manier in een boom stopt zul je inderdaad een boom van 1 miljoen nestings krijgen die allemaal 1 leaf hebben, dan krijg je wel een stackoverflow

Maar wat is er mis met een linked list?

En dat terwijl deze compleet gebalanceerd maar 20 levels diep hoeft te zijn ..

[curry684]

ACM schreef op 04 december 2003 @ 14:50:
Een linked list is niet zo erg, maar zoekt zo langzaam
Zeker als je die recursief gaat proberen te doorzoeken.

Het is een beetje afhankelijk van het doel. Zoals ik Hielko begrijp wordt er eenmalig een lijst gevuld waarop veel lookups worden gedaan en zelden tot nooit inserts plaatsvinden. In dat geval is een platte gesorteerde array met b-searches tig keer effectiever dan alle andere concepten natuurlijk.

[curry684]

Semi-offtopic trouwens:

Java:

public BinNode zoek (String woord) { 
     
    if (element == null) { 
      return this; 
    } else if (element.compareTo(woord) > 0) { 
      return rechts.zoek(woord); 
    } else if (element.compareTo(woord) < 0) { 
      return links.zoek(woord); 
    } 
    return this; 
  } // zoek 

Dit is natuurlijk rampzalig inefficient, je dwingt de compiler hier nu om de helft van de tijd 2 stringcompares te doen. Je kunt veel beter eenmalig het resultaat van compareTo in een integer storen en die vervolgens vergelijken.

[Hielko]

Ik snap dat het probleem is dat mijn boom ongebalanceerd is en dat een andere datastructuur minder snel problemen zal kennen. Maar ik wil graag dat dit ook gewoon werkt en dat moet dus ook gewoon kunnen aangezien het in linux dus wel werkt.

Ik heb geprobeerd het nu uit te voeren met een grotere stackgroote, maar zelfs als ik zeg: "java -Xss128m Binboom text1" dan geeft ie nog een stack overflow. Dus blijkbaar vergroot dat niet de juiste stack. Volgens een pagina op internet doet deze optie het volgende:

Each Java thread has two stacks: one for Java code and one for C code. The -Xss option sets the maximum stack size that can be used by C code in a thread to n. Every thread that is spawned during the execution of the program passed to java has n as its C stack size. The default units for n are bytes and n must be > 1000 bytes.
To modify the meaning of n, append either the letter k for kilobytes or the letter m for megabytes. The default stack size is determined by the Linux operating system upon which the Java platform is running.

Misschien dat ik dan die andere stack moet vergroten? Alleen ik kan daar geen commando voor vinden.

Trouwens het doel van de boom is er niet echt; ik moet een vergelijking maken van de prestaties van een Binboom en een SplayBoom (die laatste is dus wel soort van gebalanceerd, maar ook deze kent stackproblemen in windows). Overstappen naar een andere, slimmere datastructuur is voor mij dan ook geen oplossing.

[ACM]

Hielko schreef op 04 december 2003 @ 15:02:
Trouwens het doel van de boom is er niet echt; ik moet een vergelijking maken van de prestaties van een Binboom en een SplayBoom (die laatste is dus wel soort van gebalanceerd, maar ook deze kent stackproblemen in windows). Overstappen naar een andere, slimmere datastructuur is voor mij dan ook geen oplossing.

Mja, maar een balancerende binboom is wat anders dan een splayboom, voor zover ik de uitleg daarover begreep

De splayboom verschuift de root steeds naar de laatst opgezochte item oid, magoed, aangezien het geen opdracht van levensbelang is voor je applicatie kun je wellicht het beste de boel in Linux vergelijken dan en je niet te druk maken om het feit dat het niet goed in windows draait?

[Hielko]

Een splayboom is een binboom waarbij het laatst opgezochte of toegevoegde element naar de wortel verplaatst wordt. Dat is dus inderdaad geen gebalanceerde binboom, maar door het splayen wordt de boom in de meeste gevallen dus wel minder diep.

Maarja als niemand dus weet hoe ik het werkend in windows kan krijgen zal ik het dus inderdaad maar in Linux moeten gaan vergelijken.

[curry684]

Hielko: als het om efficiente-metingen gaat zou ik [rml]curry684 in "[ Java] Stackoverflow in Windows, niet in..."[/rml] toch maar wel even meenemen (kan tot 20-25% performance schelen worst case scenario).

[JeffG]

Ik ben diegene die Hielko's progje op mijn linux bak heeft geprobeerd.
Ik heb iemand anders met een windows bak gevraagd om het progje te testen, daar werkte het echter wel met -Xss128m als extra commando. Zonder dit kreeg hij weer de Stackoverflow. Erg vaag allemaal.

edit: nee met -Xss128m bleek het toch niet goed te werken. Je krijgt geen StackOverlfow, maar bij het zoeken krijg je geen waarden terug. Alsof er geen waarde bestaat.

[ Voor 25% gewijzigd door JeffG op 04-12-2003 16:07 ]

[Hielko]

curry684 schreef op 04 december 2003 @ 15:44:
Hielko: als het om efficiente-metingen gaat zou ik [rml]curry684 in "[ Java] Stackoverflow in Windows, niet in..."[/rml] toch maar wel even meenemen (kan tot 20-25% performance schelen worst case scenario).

Oke, bedankt voor de tip, zal ik dan ff veranderen

[curry684]

Hielko schreef op 04 december 2003 @ 16:54:
[...]
Oke, bedankt voor de tip, zal ik dan ff veranderen

Grap is dat de compiler niet kan of mag aannemen dat > en < bepaald voor ons logisch gedrag vertonen, en hij zal dus in beide gevallen de complete stringcompare moeten uitvoeren. Correct is dus ongeveer (mijn Java is niet zo sterk dus even in C++ ):

C++:

BinNode* BinNode::Zoek(const string &Woord)
{
register int  Result;

if(!element)
  return this;
Result = element->compareTo(Woord);
if(Result > 0)
  return rechts.Zoek(Woord);
else if(Result < 0)
  return links.Zoek(Woord);
return this;
}

[JeffG]

Verschilt niet zoveel van java

Java:

public BinNode zoek (String woord)
{ 
    int result;
    if (element == null)
        return this; 
    result = element.compareTo(woord);
    if (result > 0) 
        return rechts.zoek(woord); 
    else if (result < 0)
        return links.zoek(woord); 
    return this; 
}

[ Voor 3% gewijzigd door JeffG op 05-12-2003 12:57 ]

[Soultaker]

Hielko schreef op 04 december 2003 @ 15:32:
Een splayboom is een binboom waarbij het laatst opgezochte of toegevoegde element naar de wortel verplaatst wordt. Dat is dus inderdaad geen gebalanceerde binboom, maar door het splayen wordt de boom in de meeste gevallen dus wel minder diep.

Het is nooit mogelijk om 'm minder diep te krijgen dan ^blog(N) en een gebalanceerde boom is optimaal; je (binary) splay tree wordt dus nooit ondieper dan je balanced binary tree.

De reden dat je de er in de praktijk vaak toch winst uit kunt halen ligt in de lagere gemiddelde kosten van de operaties en niet de worst case complexiteit.

[Potatoman]

Geloof het of niet, maar ik zit met hetzelfde probleem
Ik heb een quicksort over +- 50000 objecten, en ik krijg dezelfde error.
Over een kleinere lijst werkt het wel. Dus als iemand de oplossing hiervoor weet, houd ik me aanbevolen

[curry684]

Potatoman schreef op 05 december 2003 @ 15:29:
Geloof het of niet, maar ik zit met hetzelfde probleem
Ik heb een quicksort over +- 50000 objecten, en ik krijg dezelfde error.
Over een kleinere lijst werkt het wel. Dus als iemand de oplossing hiervoor weet, houd ik me aanbevolen

We hebben er net 3 of 4 gegeven?

[Verwijderd]

het probleem is volgens mij niet zozeer dat de boom inefficent is, anders stopte hij de elementen er wel in een ander volorde is, maar het feit dat het onder linux wel werkt en onder Windows niet.

Dus hoe krijg je het voor elkaar dat de limiet van Windows net zo hoog wordt als die van linux.

[.oisyn]

Overigens is het zootje iteratief sowieso al veel sneller, en daar hoef je je datastructuur niet voor aan te passen.
Net als dat je iteratief door een linked list heen kunt gaan kun je natuurlijk ook gewoon iteratief door een boom surfen. Lost ook gelijk je stackprobleem op in je worst-case scenario waar je een al gesorteerde lijst in een boom stopt

Java:

public BinNode zoek (String woord) 
{
    BinNode node = this;
    while (node.element != null)
    {
        int r = element.compareTo (woord);
        if (r > 0)
            node = node.rechts;
        else if (r < 0)
            node = node.links;
        else
            return node;
    }
    return node;
}

[.oisyn]

Verwijderd schreef op 05 december 2003 @ 15:40:
het probleem is volgens mij niet zozeer dat de boom inefficent is

dat is juist wel het probleem! Wat jij voorstelt is symptoom bestrijding, maar dat lost het probleem niet op. Goed, en dan werkt het op een gegeven moment onder windows net zoals het onder linux werkt. Maar als je boom dan ineens 2x zo groot wordt, wat dan? Of als je het op een ander OS draait?

[Glimi]

Potatoman schreef op 05 december 2003 @ 15:29:
Geloof het of niet, maar ik zit met hetzelfde probleem
Ik heb een quicksort over +- 50000 objecten, en ik krijg dezelfde error.
Over een kleinere lijst werkt het wel. Dus als iemand de oplossing hiervoor weet, houd ik me aanbevolen

Java's Array.sort? Een eigen quicksort? Een random-pivot quicksort? Gesorteerde lijsten?

[Potatoman]

Glimi schreef op 05 december 2003 @ 15:54:
[...]

Java's Array.sort? Een eigen quicksort? Een random-pivot quicksort? Gesorteerde lijsten?

Het is al een eigen quicksort. Ik wil wel de Array.sort methode gebruiken, maar dan moet ik mijn classes nogal aanpassen. Bovendien wil ik op meerdere attributen in een class sorteren, en de array.sort methode werkt meer op 1 attribuut (via de compare methode).

[Hielko]

Hmm stackoverflow bij quicksort? Ik geloof dat er een in place variant is van Quicksort, denk dat je dat dan moet gebruiken.

ps. Mijn binboom werkt nu goed nu ik de recursieve aanroepen heb vervangen door een while loop

[Glimi]

Potatoman schreef op 05 december 2003 @ 16:08:
Het is al een eigen quicksort. Ik wil wel de Array.sort methode gebruiken, maar dan moet ik mijn classes nogal aanpassen. Bovendien wil ik op meerdere attributen in een class sorteren, en de array.sort methode werkt meer op 1 attribuut (via de compare methode).

Arrays.sort kan ook werken met een Comparable interface, zodat je zelf kunt opgeven. Het probleem zal waarschijnlijk in een niet optimale quicksort zitten, want 50.000 elementen sorteren gaat met gemakt met Arrays.sort

Wat voor een data sorteer je eigenlijk? Is de n² bovengrens van quicksort wel goed genoeg voor je applicatie?

Hielko schreef op 05 december 2003 @ 16:18:
Hmm stackoverflow bij quicksort? Ik geloof dat er een in place variant is van Quicksort, denk dat je dat dan moet gebruiken.

In place zal geen effect hebben op dit probleem. Hoogstens winst met toewijzingen, maar je methode aanroepen blijven nog steeds staan hoor. Die objecten worden echt niet op de stack gemaakt in java hoor

[ Voor 24% gewijzigd door Glimi op 05-12-2003 16:22 ]

[Soultaker]

Praktisch elke QuickSort implementatie kan in theorie O(N) recursieve aanroepen doen en dat is natuurlijk funest bij het sorteren van een beetje een grote array. Als je een beetje handig je pivot kiest dan komt die situatie natuurlijk bijna niet meer voor.

[Potatoman]

Glimi schreef op 05 december 2003 @ 16:18:
[...]

Arrays.sort kan ook werken met een Comparable interface, zodat je zelf kunt opgeven. Het probleem zal waarschijnlijk in een niet optimale quicksort zitten, want 50.000 elementen sorteren gaat met gemakt met Arrays.sort

Dat lijkt mij ook, maar dat moet ook makkelijk kunnen met mijn sort (die gewoon een standaard quicksort is eigenlijk).
Vandaar dat ik nog wat geëxperimenteerd heb, en ik heb het probleem gevonden:
ik was vergeten de data-opvraagmethode voor het sorteren te maken
Die gaf nu altijd "" terug. Blijkt dus wel dat mijn quicksort het niet leuk vindt om
50000x dezelfde data te sorteren dus ik ga nog wel even een betere oplossing zoeken.

Wat voor een data sorteer je eigenlijk? Is de n² bovengrens van quicksort wel goed genoeg voor je applicatie?

Ik heb een aantal classes met een aantal attributen (naam, achternaam, dat soort dingen). Als ik op één bepaald attribuut hiervan wil sorteren, dan kan ik of al die attributen zelf in een array stoppen en sorteren (via Array.sort dan), of de classes zelf sorteren en de index van het attribuut meegeven.
Dat laatste vind ik zelf de mooiste oplossing, alleen daar moet ik dus nog even een goede searchmethode voor maken / gebruiken

[Glimi]

Soultaker schreef op 05 december 2003 @ 16:22:
Praktisch elke QuickSort implementatie kan in theorie O(N) recursieve aanroepen doen en dat is natuurlijk funest bij het sorteren van een beetje een grote array. Als je een beetje handig je pivot kiest dan komt die situatie natuurlijk bijna niet meer voor.

Ik heb pas nog wat gelezen over Divide & Conquer Selection. Dat kan in O(n) tijd worst case, terwijl dat Quicksort based is.
Je zou een pseudomediaan kunnen kiezen als volgt: Verdeel de input in groepen van 5 zodat je floor( N/5 ) groepjes hebt. Van die groepjes ga je vervolgens de mediaan bepalen en dat kan in constante tijd.
Dan heb je van elk groepje de mediaan en dan haal je daarvan de mediaan.
Op dat moment heb je een mediaan die groter is dan 3/2*(n/5 - 1) + 2 elementen van de input ( 3 elementen uit elke groep met ene kleinere mediaan en twee elementen uit de groep van de mediaan). Dit is in O(n) tijd te bepalen.

Als je dan in O(n) tijd een pivot hebt gevonden die zeker nooit voor O(n²) gedrag kan zorgen, heb je gegarandeerd O( nlogn ) als bovengrens lijkt me. Alleen die verborgen constante moet ik nog even naar kijken.
Zal vanavond wel even wat narekenen

[Soultaker]

Wanneer voer je die selectie uit dan? Als je dat voor elke recursieve aanroep van quicksort doet, dan mag 'ie maximaal O(1) zijn en dat is het blijkbaar niet. Als je het van te voren doet zie ik niet echt wat je er mee opschiet. Kan ik dit algoritme ergens nalezen?

[Macros]

Doe gewoon radix sort, die is order O(kN), vooral bij hele grote sorts heb je onwijs veel meer snelheid. En omdat er nauwelijks branches zijn stalled je CPU ook veel minder snel door branch minspredictions (welke veel voorkomen omdat die telkens anders zijn). Ook loopt het veel voorspelbaarder door je dataset heen, wat cache misses verminderd.

[Glimi]

Soultaker schreef op 05 december 2003 @ 17:36:
Wanneer voer je die selectie uit dan? Als je dat voor elke recursieve aanroep van quicksort doet, dan mag 'ie maximaal O(1) zijn en dat is het blijkbaar niet. Als je het van te voren doet zie ik niet echt wat je er mee opschiet.

Sorry, misschien dat ik al te lang niets meer met sort's gedaan heb, maar waarom zou hij maximaal O(1) mogen zijn? Elke partionstap kost al O(n) tijd. Als daar in het kiezen van de pivot in plaats van O(1) opeens O(n) gaat kosten, krijg je O(n) + O(n) toch? Ja, je partionstap kost nu wel meer tijd, maar je hebt geen O( n² ) meer.

Vraag ik me opeens wel af, of het nu gemiddeld nog wel sneller gaat zijn dan mergesort.

Kan ik dit algoritme ergens nalezen?

Het is het gebaseerd op het Selectionprobleem (kies het s'de element van een rij als deze gesorteerd zou zijn) en hoe deze in O( n ) tijd op te lossen. Die gebruikt een quicksort-basis zeg maar, maar of het ooit echt in een quicksort geïmplementeerd is weet ik niet (het was een wild idee net even zeg maar ).
Ik ga even zoeken voor je.

[edit] Duurde wat langer, problemen met de verbinding hier. Maar neem het volgende eens:
http://www.ics.uci.edu/~eppstein/161/960130.html
Als je het stukje pseudo-code bekijkt, dan moet je dat als volgt verbouwen:
• Maak een aparte methode die uit een rij van 5 getallen de mediaan geeft, noem bijvoorbeeld medianOfFive()
• Haal uit de psuedocode het gedeelte om de pseudomediaan te bepalen (t/m M = select({x[i]}, n/10)) en maak hiervan een aparte methode, genaamd bijvoorbeeld pseudoMedian(). Die in het forloopje medianOfFive() aanroept en bij de bepaling van de pseudomediaan zichzelf ( pseudoMedian() )aanroept.

De rest van de methode gooi je weg en pak je oude vertrouwde quicksortcode erbij. Vervang vervolgens je randomstatement of je bitshift voor de pivotbepaling door een aanroep naar pseudoMedian

[edit 2]
Prettige +:) trouwens iedereen

[ Voor 29% gewijzigd door Glimi op 05-12-2003 23:01 ]

[Infinitive]

Geloof het of niet, maar ik zit met hetzelfde probleem
Ik heb een quicksort over +- 50000 objecten, en ik krijg dezelfde error.
Over een kleinere lijst werkt het wel. Dus als iemand de oplossing hiervoor weet, houd ik me aanbevolen

Ook voor quicksort wil je de recursie diepte zo laag mogelijk hebben. Sommige keuzen voor de pivot (spil) zijn niet erg handig, vooral niet wanneer de input al gesorteerd is. Een simpele truuck is het random kiezen van je pivot. Je hebt grote kans om goede pivots te kiezen.

Een alternatieve manier is door gebruik making van een 'pseudo mediaan'. Daarmee kan je ervoor zorgen dat quicksort in worst-case in de orde van log(n) diepte moet gaan. Het nadeel van deze methode is dat verborgen constanten wat betreft efficiency erg groot wordt, terwijl het tegenovergestelde juist pluspunt van de conventionele quicksort is.

[edit]
Te laat...

Hier kan je overigens ook nalezen hoe het precies zit:
http://www.cs.uu.nl/docs/vakken/al/algoritmiek2003-2.ppt

Onder andere beschreven/bewezen in:
Fundamentals of Algorithmics
Gilles Brassard and Paul Bratley
ISBN 0133350681

[ Voor 27% gewijzigd door Infinitive op 06-12-2003 10:53 ]

[Glimi]

Infinitive schreef op 06 december 2003 @ 10:29:

offtopic:
Inderdaad, Algoritmiek En volgens mij ben jij ook begeleider van groep 2 bij Grammatica's en Ontleden. Dan ben ik diegene die opdracht één compileerde met GHC om zo één niveau dieper te komen

Ik zal binnekort even een reference implementatie maken en eens een benchmarkje op draaien.

[Infinitive]

Ik zal binnekort even een reference implementatie maken en eens een benchmarkje op draaien.

Hoe meer tests je in je benchmark hebt zitten, hoe dichter je de 'expected case' benaderd en dat betekend dus een voordeel voor de gerandomiseerde quicksort. Ik denk dat je benchmark dus weinig zin heeft

offtopic:
Dus jij was die uitslover
Ik assisteer geef nu de werkcolleges op dinsdag en vrijdag. Er is alleen geen kip die naar de werkcolleges gaat... maar wel 44 practicumopdrachten voor ons om na te kijken

[ Voor 29% gewijzigd door Infinitive op 06-12-2003 12:19 ]

[Glimi]

Infinitive schreef op 06 december 2003 @ 12:15:
Hoe meer tests je in je benchmark hebt zitten, hoe dichter je de 'expected case' benaderd en dat betekend dus een voordeel voor de gerandomiseerde quicksort. Ik denk dat je benchmark dus weinig zin heeft

Hoe weet je nou hoe ik die benchmark wil gaan uitzetten Je gaat natuurlijk eerst de winst kijken bij worst-case scenario en daarna kun je kijken hoe het verschil oploopt bij een gemiddeld geval. Daarmee kun je dan wel gaan afwegen of het verschil groot wordt of niet.
_{Random bij java is ook redelijk traag als je hem moet initializen bij een stateless quicksort}

offtopic:
Dus jij was die uitslover

offtopic:
Had je me anders verwacht dan