[Java] Recursieve functies i.c.m. classe-variabele = bug

[dtech]

Ik programmeerde laatst een recursieve functie, en om het e.e.a. wat te versnellen wilde ik er een tabel voor al uitgerekende functiewaarden bij maken. Omdat ik deze wilde bewaren tussen berekeningen door heb ik de functie in een klasse gezet.

Nu kreeg ik hele rare resultaten, en met asserts kwam ik erachter dat soms de functie nul (oftewel de standaardwaarde van een int) retourneerde.

Na behoorlijk wat debuggen heb ik de fout ontdekt, maar ik ben er nog niet achter waarom het fout gaat.

Hieronder de (versimpelde) code:

Java:

// F: N x N -> N \ {0}
class F{

    private int[][] table;

    public expandTable(a,b){
        // Maak een nieuw 2-dimensionale tabel om de functiewaarden in op te slaan
        // Grootte [a+1][b+1] omdat 0 ook meeteld
        if(table==null){
            table = new int[a+1][b+1];
        }
        
        if(table.length < a+1 || table[0].length < b+1){
            // Maak tabel aan met voldoende grootte
            int[][] newTable =
                new int[(a+1>table.length?a+1:table.length)][(b+1>table[0].length?b+1:table[0].length)];
            
            // Kopieer tabel
            for(int i=0;i<table.length;i++){
                for(int j=0;j<table[0].length;j++){
                    newTable[i][j] = table[i][j];
                }
            }
            // Vervang  referentie door refentie naar nieuw tabel
            table = newTable;
        }
    }

    // 1: Dit werkt niet
    public calc(int a, int b){
        expandTable(a,b);
        
        if(table[a][b] != 0){
            return table[a][b];
        }
        
        if(iets){
            table[a][b] = calc(a-1,b);
        }else if(iets){
            table[a][b] = calc(a, b-1);
        }else{
            table[a][b] = a+b+1;
        }
        
        return table[a][b];
    }
    
    // 2: Dit werkt wel
    public calc(int a, int b){
        expandTable(a,b);
        
        if(table[a][b] != 0){
            return table[a][b];
        }
        
        int result = 0;
        if(iets){
            result = calc(a-1,b);
        }else if(iets){
            result = calc(a, b-1);
        }else{
            result = a+b+1;
        }
        table[a][b] = result;
        
        return table[a][b];
    }
    
    // 3: Dit werkt ook, maar zorgt voor meer rekenwerk en geheugenruimte
    public calc(int a, int b, int[][] table){
        expandTable(a, b, table);
        
        if(table[a][b] != 0){
            return table[a][b];
        }
        
        if(iets){
            table[a][b] = calc(a-1,b, table);
        }else if(iets){
            table[a][b] = calc(a, b-1, table);
        }else{
            table[a][b]] = eengetal;
        }
        
        return table[a][b];
    }
}

Heeft iemand enig idee van de precieze reden hiervan?
Is het dat de "table[a][b]" "te vroeg" wordt vertaald naar een "echte" geheugenlocatie of is het iets anders?

[ Voor 1% gewijzigd door dtech op 15-02-2009 11:34 . Reden: 1: opmaak gefixt 2: overtik foutje gefixt ]

[Soultaker]

dtech schreef op zaterdag 14 februari 2009 @ 22:54:
Is het dat de "table[a][b]" "te vroeg" wordt vertaald naar een "echte" geheugenlocatie of is het iets anders?

Ik dacht dat dat het was maar ik kan het toch niet helemaal verklaren. In Java wordt een statement van links naar rechts geëvalueerd; eerst wordt dus het adres van table[a][b] geëvalueerd (wat op zichzelf al twee stappen zijn; eerst wordt het a-de element van table geëvalueerd, wat een array van arrays oplevert, waarna daarvan weer het b-de element wordt genomen) en daarna wordt calc() uitgevoerd. Als calc() dan een nieuwe waarde aan table toekent, gaat 't mis omdat je het resultaat dan in een oude array stopt.

Een stukje code wat dit probleem simpeler illustreert:

Java:

public class Test
{
    private int[] a;
    public int foo() {
        a = new int[100];
        return 1337;
    }
    public int bar(int n) {
        a[n] = foo();
        return a[n];
    }
    public static void main(String[] args)
    {
        System.out.println(new Test().bar(7));
    }
};

Je zou zeggen dat deze code zou werken omdat éérst foo() uitgevoerd moet worden voordat een assignment uitgevoerd kan worden, dus wordt de array gealloceerd door foo(). Maar Java zal eerst a[n] proberen te evalueren (en falen).

Toch is dit niet de volledige verklaring, want in jouw specifieke code worden a en b alleen maar kleiner, dus de recursieve aanroep van calc() kan er nooit voor zorgen dat de tabel opnieuw aangemaakt wordt. Weet je heel zeker dat dat in je echte (niet versimpelde) code ook zo werkt?

[Erik Jan]

Neem eerst expandTable() eens onder de loep:
• Je doet op tientallen plekken a+1 en b+1, dat kan natuurlijk nooit goed zijn want dat is redundantie.
• Waarom gebruik je uberhaupt a+1 en b+1, het is toch veel beter als een functie gewoon doet wat ie belooft te doen? M.a.w. zorg dat expandTable(int rows, int cols) ook daadwerkelijk een tabel met (rows * cols) cellen oplevert.
• Waarom return je niet na regel 10?
• Waarom staat er op regel 16 een a+1 in de ternary operatie die over b gaat? Dit kon voorkomen worden door duidelijkere namen voor je variabelen te gebruiken.
• Wat gebeurt er als een of andere onverlaat stiekum de functie met negatieve argumenten aanroept? Aangezien ik al ergens a-1 zag staan is dit niet een heel onrealistische situatie.

Dan laat ik calc() nog even met rust

[ Voor 0% gewijzigd door Erik Jan op 15-02-2009 00:31 . Reden: typo ]

[MSalters]

Soultaker schreef op zaterdag 14 februari 2009 @ 23:51:
[...]
In Java wordt een statement van links naar rechts geëvalueerd; eerst wordt dus het adres van table[a][b] geëvalueerd (wat op zichzelf al twee stappen zijn; eerst wordt het a-de element van table geëvalueerd, wat een array van arrays oplevert, waarna daarvan weer het b-de element wordt genomen) en daarna wordt calc() uitgevoerd. Als calc() dan een nieuwe waarde aan table toekent, gaat 't mis omdat je het resultaat dan in een oude array stopt.

Is dat nou eigenlijk handig? De regel is wel simpel, maar het lijkt erop dat de regel nogal arbitrair is - een gevolg van syntax, niet van semantiek. Als we assignments als calc(a-1,b) -> table[a][b] hadden geschreven, was table[a][b] dan pas na calc() geevalueerd?

Mijn eerste aanname was overigens dat het vooraf uitrekenen van de left-hand side betekende dat je gedurende de functiecall een register kwijt was, je moet het resultaat van table[a][b] opslaan. Maar bij nader inzien valt dat wel mee; je hieft table, a en b zelf niet meer op te slaan. Maar hoe zou dat in het algemeen uitpakken? Als je zou mogen kiezen, is het dan handiger om de linkerkant eerst uit te rekenen?

[ Voor 26% gewijzigd door MSalters op 15-02-2009 02:56 . Reden: quote knippen ]

[dtech]

Soultaker schreef op zaterdag 14 februari 2009 @ 23:51:
[...]

Toch is dit niet de volledige verklaring, want in jouw specifieke code worden a en b alleen maar kleiner, dus de recursieve aanroep van calc() kan er nooit voor zorgen dat de tabel opnieuw aangemaakt wordt. Weet je heel zeker dat dat in je echte (niet versimpelde) code ook zo werkt?

My bad, in de echte functie wordt a weliswaar steeds kleiner, maar is b zo onberekenbaar als ****
Het is overigens de Ackermann_function

[dtech]

@Erik Jan
even vooraf, dit is niet de echte code; ik dacht het wat duidelijker te maken door details weg te laten...

Erik Jan schreef op zondag 15 februari 2009 @ 00:30:
Neem eerst expandTable() eens onder de loep:
• Je doet op tientallen plekken a+1 en b+1, dat kan natuurlijk nooit goed zijn want dat is redundantie.

Als jij een input range van 0-a (bijv. a=5) hebt, en je wilt een array maken waar dat in kan, hoeveel elementen heb je dan nodig? juist: a+1 (tel maar, bij a=5: 0 1 2 3 4 5)

Erik Jan schreef op zondag 15 februari 2009 @ 00:30:
• Waarom gebruik je uberhaupt a+1 en b+1, het is toch veel beter als een functie gewoon doet wat ie belooft te doen? M.a.w. zorg dat expandTable(int rows, int cols) ook daadwerkelijk een tabel met (rows * cols) cellen oplevert.

Dat gaat niet werken omdat je dan een te klein nieuw tabel kunt krijgen, m.a.w. het oude tabel past niet meer in het nieuwe tabel. Bijv:

Java:

tabel[0][0] = 1;
tabel[1][0] = 2;

// Als je enkel een nieuwe tabel met [a+1][b+1] zou maken...
expandTable(0, 1);
newTable[0][0] = 0;
newTable[0][1] = 0;

// En dan gaat hij nu kopieren, over tabel.length;
newTable[0][0] = tabel[0][0];
// Krijg je hier een ArrayIndexOutOfBoundsException
newTable[1][0] = tabel[1][0];

Erik Jan schreef op zondag 15 februari 2009 @ 00:30:
• Waarom staat er op regel 16 een a+1 in de ternary operatie die over b gaat? Dit kon voorkomen worden door duidelijkere namen voor je variabelen te gebruiken.

Mijn fout bij het opnieuw tikken van de code

Erik Jan schreef op zondag 15 februari 2009 @ 00:30:
• Wat gebeurt er als een of andere onverlaat stiekum de functie met negatieve argumenten aanroept? Aangezien ik al ergens a-1 zag staan is dit niet een heel onrealistische situatie.

Dan laat ik calc() nog even met rust

In de echte code wordt daar even op gesjekt

[Macros]

Aantal vragen:
- waarom doe je moeilijk met array's als ze van grootte veranderen? gebruik dan gewoon arraylists.
- als je toch perse arrays wilt gebruiken, waarom gebruik je dan niet System.arraycopy()? Is altijd sneller dan for loopjes om elementen te kopieren.

[Soultaker]

dtech schreef op zondag 15 februari 2009 @ 11:33:
My bad, in de echte functie wordt a weliswaar steeds kleiner, maar is b zo onberekenbaar als ****
Het is overigens de Ackermann_function

Ah ja. Daarmee is je vraag ook beantwoord dus? (Of was mijn uitleg niet voldoende duidelijk/bevredigend?)

[ Voor 7% gewijzigd door Soultaker op 15-02-2009 15:05 ]

[Soultaker]

MSalters schreef op zondag 15 februari 2009 @ 02:56:
Is dat nou eigenlijk handig? De regel is wel simpel, maar het lijkt erop dat de regel nogal arbitrair is - een gevolg van syntax, niet van semantiek. Als we assignments als calc(a-1,b) -> table[a][b] hadden geschreven, was table[a][b] dan pas na calc() geevalueerd?

Dat is wel een interessante vraag. Ik dat het inderdaad gewoon een arbitraire regel is om te garanderen dat de volgorde van evaluatie volledig gedefinieerd is, zodat er geen twijfel kan bestaan over hoe dit soort code moet worden uitgevoerd. Dat is wel prettig aan Java.

Of het qua efficiëntie veel uitmaakt... tja, ik betwijfel het. Zelfs als je extra info moet saven zal die overhead wel meevallen ten opzichte van de function call. Misschien dat om de reden die je aangeeft (je rekent het doeladres alvast uit, waarna je indices niet meer nodig hebt) de huidige keuze wel efficiënter is, maar dan nog betwijfel ik of dat een overweging was bij het definiëren van de taal. Ik heb het idee dat bij het ontwerpen van Java niet veel rekening is gehouden met dit soort micro-optimalisaties, anders hadden ze nog wel wat dingen zoals value-types en meerdimensionale arrays kunnen inbouwen.

[dtech]

Soultaker schreef op zondag 15 februari 2009 @ 15:05:
[...]

Ah ja. Daarmee is je vraag ook beantwoord dus? (Of was mijn uitleg niet voldoende duidelijk/bevredigend?)

Bijna, maar niet helemaal, waarom werkt het wel als je dit doet? (en dan natuurlijk expandTable en calc zo aanpast dat ze een int[][] als derde parameter nemen)

Java:

table[a][b] = calc(a-1,b+1, table);

[Soultaker]

Hoe werkt expandtable() dan precies? Uit je pseudo-code lijkt het alsof je de member variable helemaal niet gebruikt.

[dtech]

Nee, inderdaad niet. Ik bedoelde dat ik er in kan komen dat het niet werkt omdat table[a][b] te vroeg geëvalueerd wordt, maar waarom werkt het dan wel als dit dit doet:

Java:

class F{

    public expandTable(a,b, table){
        if(table==null){
            table = new int[a+1][b+1];
        }
        
        if(table.length < a+1 || table[0].length < b+1){
            // Maak tabel aan met voldoende grootte
            int[][] newTable =
                new int[(a+1>table.length?a+1:table.length)][(b+1>table[0].length?b+1:table[0].length)];
            
            // Kopieer tabel
            for(int i=0;i<table.length;i++){
                for(int j=0;j<table[0].length;j++){
                    newTable[i][j] = table[i][j];
                }
            }
            // Vervang  referentie door refentie naar nieuw tabel
            table = newTable;
        }
        return table;
    }
    
    public calc(int a, int b){
        return this.cal(a, b, null);
    }
    
    // 3: Dit werkt ook, maar zorgt voor meer rekenwerk en geheugenruimte
    // We gaan er even vanuit dat de functie goed gebruikt wordt, dus enkel met N x N als argumenten
    protected calc(int a, int b, int[][] table){
        table = expandTable(a, b, table);
        
        if(table[a][b] != 0){
            return table[a][b];
        }
        
        if(a==0){
            table[a][b] = b+1;
        }else if(b == 0){
            table[a][b] = calc(a-1, 1, table);
        }else{
            table[a][b] = calc(a-1, calc(a, b-1), table);
        }
        
        return table[a][b];
    }
}

[Soultaker]

Ah, dat is behoorlijk logisch: als expandTable() nu een nieuwe tabel aanmaakt, verandert de variabele tabel in de oorspronkelijke aanroep van calc() niet, omdat dat nu gewoon een lokale variable is in plaats van een member variable.

Het probleem in je oorspronkelijke code zat 'm er in dat table op regel 38/40/42 naar de oude array verwijst, daarna wordt een nieuwe array aan tabel toegekend, waardoor je op regel 45 een waarde uit de níeuwe array leest! Door van tabel een lokale variabele te maken omzeil je precies dat probleem.

(Overigens lijkt de tweede methode me de beste manier om het probleem op te lossen, voor het geval je daar nog over twijfelde).

[ Voor 12% gewijzigd door Soultaker op 15-02-2009 22:37 ]

[dtech]

Natuurlijk, nu zie ik hem.

Methode twee is idd ook de methode die ik gebruikt heb, methode 3 kan 2^n keer zoveel geheugen gebruiken (waarbij n=aantal splitsingen door de laatste else) ofzoiets, plus dat veel van de berekeningen niet "gedeeld" worden en dus herhaaldelijk uitgevoerd worden.