Ah, äntligen kom jag underfund med varför vissa beräkningar har tagit dubbelt så lång tid för varenda version jag lagt till. Det berodde på en simpel nollställning av om en fråga används. Funktionen anropade för varje fråga versionen tidigare för att nollställa, som då gick igenom hela versionsträdet. Det gör att exekveringstiden blir proportionell emot 2 ^ n. Med 31 versioner blir det 2 ^ 31, vilket gjorde att beräkningen tog flera timmar på en dubbel-kärne processor. Nu går samma sak på några sekunder.

rdos skrev:Ah, äntligen kom jag underfund med varför vissa beräkningar har tagit dubbelt så lång tid för varenda version jag lagt till. Det berodde på en simpel nollställning av om en fråga används. Funktionen anropade för varje fråga versionen tidigare för att nollställa, som då gick igenom hela versionsträdet. Det gör att exekveringstiden blir proportionell emot 2 ^ n. Med 31 versioner blir det 2 ^ 31, vilket gjorde att beräkningen tog flera timmar på en dubbel-kärne processor. Nu går samma sak på några sekunder.

Och så brukar kritiker av komplexitetsteori tjata om att det där med exponentialitet inte är något problem i praktiken, bara i teorin.

Kvasir skrev:Och så brukar kritiker av komplexitetsteori tjata om att det där med exponentialitet inte är något problem i praktiken, bara i teorin.

Ja, det är lustigt. Jag har nog aldrig råkat ut för ett sådant här problem tidigare som gett så märkbara resultat. Själva nollställningen var bara en enda programrad som anropade en annan metod. Det hela ser mycket enkelt & effektivt ut. Inte speciellt enkelt att hitta heller. Jag började tröttna när en till synes mycket enkel procedur inte var klar på en halvtimme. Då körde jag det hela i debuggern för att se vad som tog sådan förskräcklig tid.

Tänk, jag hade ju inte ens behövt byta dator om jag listat ut detta tidigare. För bara en 5-10 versioner sedan kunde en gammal maskin köra alltsammans hur bra som helst.

rdos skrev:Ja, det är lustigt. Jag har nog aldrig råkat ut för ett sådant här problem tidigare som gett så märkbara resultat. Själva nollställningen var bara en enda programrad som anropade en annan metod. Det hela ser mycket enkelt & effektivt ut. Inte speciellt enkelt att hitta heller. Jag började tröttna när en till synes mycket enkel procedur inte var klar på en halvtimme. Då körde jag det hela i debuggern för att se vad som tog sådan förskräcklig tid.

Det låter onekligen väldigt ovanligt att ett så enkelt fel skulle leda till exponentiellt beteende. Det brukar oftast handla om att man använder en exponentiell algoritm när det finns effektivare alternativ eller att själva problemet kräver exponentiell tid.

Tänk, jag hade ju inte ens behövt byta dator om jag listat ut detta tidigare. För bara en 5-10 versioner sedan kunde en gammal maskin köra alltsammans hur bra som helst.

Hur många företag tror du inte har investerat i nya maskiner pga. programfel eller dålig programmering?

Nu har du en ny och snabb dator i alla fall, och det är ju alltid trevligt.

För öfvrigt, utförs beräkningarna på rdos eller något annat OS?

nitro2k01 skrev:För öfvrigt, utförs beräkningarna på rdos eller något annat OS?

Just nu kör jag bara under Windows. Jag har ingen maskin med 512MB minne som kör med rdos. Annars så tror jag iofs att det skulle fungera, förutsatt att minnet räcker.

Det är iofs oxå ett problem som borde åtgärdas. Det ska inte behövas flera hundra megabyte för att göra dessa analyser, men det är inte lika enkelt att fixa till. Jag lider väl av Microsoft-sjukan när det gäller att skriva minneshungriga applikationer som tar evigheter att köra.

Kvasir skrev:Det låter onekligen väldigt ovanligt att ett så enkelt fel skulle leda till exponentiellt beteende. Det brukar oftast handla om att man använder en exponentiell algoritm när det finns effektivare alternativ eller att själva problemet kräver exponentiell tid.

Den normala algoritmen kräver bara en tid som är proportionell emot N. Den blev exponentiell för att varje nytt steg gjorde om samma jobb som de tidigare stegen. Rekursiv programmering är ibland förädiskt.

Kvasir skrev:Hur många företag tror du inte har investerat i nya maskiner pga. programfel eller dålig programmering?

Säkert massor

Kvasir skrev:Nu har du en ny och snabb dator i alla fall, och det är ju alltid trevligt.

Jo, men dottern vill gärna låna den för att titta på DVD, fast hon fick min gamla. Jag får väl hjälpa henne att skaffa nya högtalare till sin dator.

rdos skrev:
Den normala algoritmen kräver bara en tid som är proportionell emot N. Den blev exponentiell för att varje nytt steg gjorde om samma jobb som de tidigare stegen. Rekursiv programmering är ibland förädiskt.

Aha, så istället för ett rekursivt anrop så gjorde du två (eller flera)? Det är nog många som har gått på den niten utan att det är slarvfel, som i ditt fall. Det ser ju inte ut att vara någon stor skillnad.