Alverdens programmører ved nu, at en række gængse datastrukturer umuligt kan gøres mere effektive. Kasper Green Larsen har fundet formlen.

Af Filip Graugaard Esmarch

På en af de store danske portaler for brugte biler søger jeg efter en bil til højst 100.000 kr. Samtidig er jeg miljøbevidst, så jeg beder om kun at få vist de biler, som hævdes at kunne køre mindst 30 kilometer på literen.

Det tager systemet et lille sekund at fortælle mig, at blandt de næsten 40.000 personbiler i databasen opfylder 79 af dem mine to kriterier. Men med den internetforbindelse og hardware, der nu engang findes hos mig og i databasens server, kunne jeg så have fået resultatet endnu hurtigere, hvis databasens søgesystem var smartere bygget op? Altså, hvis programmørerne bag dens platform var innovative nok, kunne de så forbedre datastrukturernes hastighed?

Den type spørgsmål har optaget dataloger i mere end 30 år, men ingen har kunne levere et tilfredsstillende svar. Ikke før Kasper Green Larsen som ph.d.-studerende kom på banen med en ny måde at regne det ud på. Han fandt ud af, at svaret i øjeblikket er ‘nej’.

Overvandt en mur

”Når en computer skal finde resultatet af en databasesøgning med et bestemt antal kriterier, vil processoren altid skulle kigge i databasen et vist minimum af gange. Og sådan en nedre grænse er værdifuld at kende, fordi den viser, om man kan gøre et konkret søgesystem mere effektivt

eller ej. Derfor har man siden 1970’erne forsøgt at finde en stærk formel for den nedre grænse,” fortæller Kasper Green Larsen. Her ramte man i 80’erne en mur, som Kasper udtrykker det. Men i 2004 fik en forsker forbedret formlen en smule.

”Det var ved at læse hans artikler, at jeg kom ind i feltet. Og mit resultat har udviklet formlen længere end det, han formåede. Min formel beviser, at man allerede er nået i mål med at finde den mest effektive opbygning af flere forskellige datastrukturer.”

Kasper Green Larsen forklarer, at langt de fleste computerprogrammer er bygget op omkring 10-20 almindelige datastrukturer. Når man vil finde grænsen for, hvor effektive de kan blive, giver det et tilsvarende antal matematiske problemer. Her er det blandt andet lykkedes ham at finde den endegyldige løsning på det problem, som har at gøre med databasesøgning ud fra flere kriterier.

Hele 21 artikler

Selvom Kasper Green Larsens formel ikke er stærk nok til at løse alle problemerne, er hans resultat særdeles opsigtsvækkende. Og i sin artikel har han formidlet det så godt, at den modtog en af de mest prestigefyldte priser inden for teoretisk datalogi.

Med i alt 21 publicerede artikler i løbet af ph.d.-studiet har Kasper Green Larsen været exceptionelt produktiv. Mange af dem handler om nye og hurtigere løsninger på forskellige matematisk-datalogiske problemer. Det område vil han fortsætte med, nu hvor han fra den 1. maj 2014 er ansat som adjunkt ved Datalogisk Instituts forskningscenter MADALGO.