Att hitta rätt algoritm-data struktur kombination är lätt, men att hitta rätt data struktur för en uppsättning algoritmer är mycket mindre trivialt. Dessutom kan det vara suboptimalt att använda samma datarepresentation under hela programmet. Beroende på flera faktorer, som ofta bara är kända vid körning, har vissa program nytta av att ändra datarepresentationen under körningen. I detta positionsdokument introducerar vi idén om Just-In-Time datastrukturer, en kombination av ett datagränssnitt och en uppsättning konkreta data representationer med olika prestandaegenskaper. Dessa Just-InTime datastrukturer kan dynamiskt byta sin interna datarepresentation när kostnaden för byte betalas tillbaka många gånger i återstoden av beräkningen. För att Just-In-Time datastrukturer ska fungera krävs forskning på tre fronter: 1. Vi måste bättre förstå synergin mellan olika data representationer och algoritmer; 2. Vi behöver ett strukturerat tillvägagångssätt för att hantera övergången mellan datarepresentationer; 3. Vi behöver beskrivande programmeringskonstruktioner för att uttrycka vilken representation som passar ett programfragment bäst. Tillsammans kommer denna forskning att resultera i en strukturerad programmeringsmetod där datagränssnittet separeras från datarepresentationen, inte bara förbättrar begripligheten och underhållbarheten, utan också förbättrar prestandan genom automatiserade övergångar av datarepresentation. Nyckelord algoritmer, datastrukturer, prestanda Att hitta rätt kombination av en datastruktur och en algoritm är enkelt: det kräver antingen kunskap (dvs. kurser och böcker om datastrukturer och algoritmer), eller det kräver erfarenhet. Men i de flesta fall kräver en optimal lösning prestandateknik på själva programmet, eftersom program sällan förlitar sig på en enda algoritm för att göra sitt jobb. Att hitta rätt kombination av en datastruktur och en sekvens av algoritmer (dvs. program) är inte så trivialt och kanske inte ens möjligt utan att ta den dynamiska behörigheten att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt eller klassrum användning beviljas utan avgift förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga hänvisning på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org. kännetecknen, t.ex. mängden data och egenskaper som sorteradhet, med hänsyn tagen till detta. I dessa situationer är det fördelaktigt att överväga flera data representationer för samma datagränssnitt och ändra representation mellan faser av programmet, dvs. när kostnaden för att byta från en datarepresentation till en annan, är mindre än den kostnad som införs genom att använda "fel" (dvs. suboptimal) datastruktur. I vår forskning riktar vi in oss på denna typ av stegvisa program som kan dra nytta av en föränderlig datarepresentation. Betrakta ett e-postklientprogram som ett exempel: för det mesta vill du ha dina e-postmeddelanden sorterade efter datum, men samtidigt gillar du också att bläddra igenom en historia av e-post från en enda korrespondent, medan nya e-postmeddelanden fortsätter att anlända i din brevlåda. En utbildad datavetare eller programmerare kan hitta den bästa algoritmen för att sortera en oftast sorterad sekvens (dvs. sortera efter datum), hitta den bästa datastrukturen för iterering över en delmängd av element (dvs. iterera efter författare) och hitta den bästa datastrukturen för billig insättning vid fronten (dvs. nya e-postmeddelanden anländer per definition i kronologisk ordning). Frågan om vilken datarepresentation som passar alla behov kommer sannolikt att lämnas obesvarad. Dessutom bryr sig inte programmeraren som är ansvarig för att kombinera de olika funktionerna om hur datagränssnittet implementeras. Vill han programmera med en länkad-list-of-emails, en array-of-emails, eller skulle han föredra att programmera mot gränssnittet i en brevlåda? Det är väl accepterat att programmering med abstrakta datatyper (interfaces to data) istället för med konkreta implementationer (interfaces to data representation) är bättre för att upprätthålla, förstå och modulära. Vi antar att skilja valet av datarepresentation från algoritmdesign och annan programlogik kan också ha en betydande fördelaktig inverkan på programmens prestanda genom att ändra representationen vid körtid. I den senaste forskningen (se avsnitt 2) har detta antagande med framgång verifierats i specifika sammanhang, t.ex. samlingar på högre nivå. Vi vill utveckla en strukturerad programmeringsmodell som generaliserar denna teknik och för den till tillämpningsprogrammets nivå. I denna modell uppmuntras separation av gränssnitt från implementationer, så att ändring av data representation kan automatiseras, med förbättrad prestanda som ett resultat. Vi är inte de första att tänka på att hitta rätt algoritm-data struktur kombination för prestandans skull. Det är ett känt och studerat problem, men hittills saknar vi en allmän lösning. I detta avsnitt ger vi en översikt över vad forskning har gjorts tidigare. Framför allt har det gjorts en stor mängd grundarbete om algoritmers prestanda i kombination med datastrukturer inom teoretisk datavetenskap. Att mäta och/eller uppskatta algoritmernas tidskomplexitet är en del av varje kurs på kandidatnivå i detta ämne och är en del av varje bok om detta ämne, t.ex. Cor-
I REF motiverar en kartläggning av olika tillvägagångssätt för att välja idealisk datarepresentation utvecklingen av ett strukturerat tillvägagångssätt som kallas Just-in-time datastrukturer.
Data interface + algorithms = efficient programs: separating logic from representation to improve performance
{'venue': 'ICOOOLPS@ECOOP', 'journal': None, 'mag_field_of_study': ['Computer Science']}