Hur snabb är datorn?

pdp11

Hur snabb är din dator? En till synes enkel fråga som är svår att besvara. Här kommer ett svar som med största sannolikhet kommer att vara sant även om 50 år – när all hårdvara och mycket av den mjukvara som vi använder idag är föråldrad och bortglömd.

Det är inte bara hårdvaran som påverkar datorns hastighet. Mjukvaran kan vara ännu viktigare. Det finns många olika sätt att lösa ett visst problem med hjälp av mjukvara och olika lösningar kan ha dramatiskt olika prestanda. Det finns kompletta ord­behandlings­program som fungerar utmärkt på en 1 MHz-processor med 1 Mbyte minne. Samtidigt finns det ord­behandlings­program som går långsamt och utnyttjar datorns resurser till bristnings­gränsen trots att de kör på en modern dator med långt bättre prestanda.

Algoritmer och datastrukturer handlar om att skriva högpres­terande program. Alla bra universitet har kurser i detta ämne och vår förståelse börjar bli ganska god. Att tillämpa kunskaperna i praktiken kan dock vara svårt. Ibland vill man inte ens. Det går nämligen bra att tjäna pengar även på ineffektiv programvara. På det sättet kan man sälja mer hårdvara och mer datorsupport – båda viktiga inkomst­källor inom dator­industrin. Dessutom kan det vara svårt för en användare att avgöra om ett program är bra eller dåligt eftersom programmen är oåtkomliga för de flesta.

Låt mig ta ett typiskt exempel. På min äldsta dator – som är över tjugo år gammal och redan ett museiföremål – kan man be operativ­systemet att flytta om filerna på hårddisken för att få bättre plats för nya filer. Det intressanta med detta program är att det visar en animering på skärmen där man kan se hur olika block på hårddisken fylls med data. På det sättet kan man följa algoritmen trots att man inte har tillgång till programkoden. Man ser att programmet börjar med att försöka fylla det första blocket med data. Om det misslyckades så börjar algoritmen om från början. Den här gången fylls, med lite tur, två stycken block innan man återigen får starta om. Det fortsätter på samma sätt och det kan ta timmar innan städningen av hårddisken är klar.

Att exakt räkna ut hur lång tid hela algoritmen tar är svårt. En grov, men ändå användbar, uppskattning är att algoritmen totalt behandlar 1 + 2 + 3 + ... + n stycken block, där n är det totala antalet block som behövs för att rymma alla filer. Varje gång vi startar om från början fyller vi ju på ytterligare ett block och i sista varvet fylls n stycken block.

Den totala tiden blir därför av storleksordning n(n-1)/2. Eftersom vi ändå inte kan räkna exakt i det här exemplet så approximerar vi detta med n2. Vi har en algoritm där tiden är proportionell mot kvadraten på problemets storlek. Vi säger att en sådan algoritm har kvadratisk tidskomplexitet.

En algoritm med kvadratisk tidskomplexitet fungerar bra för små problem, men redan vid några tusen dataenheter (pixlar, block, bokstäver, etc) så riskerar algoritmen att bli alltför långsam – tusen i kvadrat blir ju en miljon. Med en miljon dataenheter så är algoritmen troligen totalt oanvändbar eftersom en miljon i kvadrat är tusen miljarder.

Den här typen av beteende hittar man i all slags programvara och problemet kan inte lösas genom att köpa en snabbare dator. När minnet blir tio gånger så stort så måste processorn bli hundra gånger snabbare för att vi ska bli klara på samma tid. Redan medelstora problem (10-100 kbyte data) kan bli olösliga även med den snabbaste processor.

Det finns gott om långsamma algoritmer i kommersiell programvara. Den goda nyheten är att många grundläggande och viktiga problem har effektiva algoritmer och att allt fler av dessa börjar dyka upp i modern programvara. Den dåliga nyheten är att det finns problem där ingen har lyckats hitta några effektiva algoritmer.

Det finns problem där de bästa kända algoritmerna har tidskomplexitet av exponentiell storlek. Det betyder att det tar tid proportionell mot 2n att lösa vissa problem av storlek n. Redan för mycket små n är dessa algoritmer fullständigt opraktiska: 220 är till exempel mer än en miljon och 240 mer än tusen miljarder.

En stor klass av intressanta och viktiga problem – så kallade NP-svåra problem  – har ingen lyckats lösa bättre än så. Många av dessa problem är praktiskt viktiga och man blir därför tvungen att kompromissa. Ibland går det till exempel att hitta effektiva algoritmer om man nöjer sig med lösningar som inte är helt optimala eller helt korrekta. Det pågår mycket och intressant forskning om detta inom ett ämnesområde som heter komplexitetsteori.

Stefan Nilsson