De originele versie van Dit verhaal verscheen in Hoeveel tijdschrift.
Computerwetenschappers gaan vaak om met abstracte problemen die moeilijk te begrijpen zijn, maar een opwindend nieuw algoritme is belangrijk voor iedereen die boeken bezit en ten minste één plank. Het algoritme behandelt iets dat het sorteerprobleem van de bibliotheek wordt genoemd (formeler, het probleem “Lijst -labelen”). De uitdaging is om een strategie te bedenken voor het organiseren van boeken in een soort van gesorteerde volgorde – bijvoorbeeld alfabetisch – die minimaliseert hoe lang het duurt om een nieuw boek op de plank te plaatsen.
Stel je bijvoorbeeld voor dat je je boeken bij elkaar houdt en lege ruimte laat rechts van de plank achterlaat. Als u dan een boek van Isabel Allende aan uw collectie toevoegt, moet u mogelijk elk boek op de plank verplaatsen om er ruimte voor te maken. Dat zou een tijdrovende operatie zijn. En als je dan een boek krijgt van Douglas Adams, moet je het helemaal opnieuw doen. Een betere regeling zou niet -bezette ruimtes over de plank laten – maar hoe moeten ze precies worden verdeeld?
Dit probleem werd geïntroduceerd in een 1981 papieren het gaat verder dan alleen het bieden van bibliothecarissen met organisatorische begeleiding. Dat komt omdat het probleem ook van toepassing is op de opstelling van bestanden op harde schijven en in databases, waar de te regelen items in de miljarden kunnen tellen. Een inefficiënt systeem betekent significante wachttijden en belangrijke rekenkosten. Onderzoekers hebben enkele efficiënte methoden uitgevonden voor het opslaan van items, maar ze hebben al lang de best mogelijke manier willen bepalen.
Vorig jaar, in een studie Dat werd gepresenteerd op de Foundations of Computer Science Conference in Chicago, een team van zeven onderzoekers beschreef een manier om items te organiseren die verleidelijk dicht bij het theoretische ideaal komen. De nieuwe aanpak combineert een beetje kennis van de eerdere inhoud van de boekenplank met de verrassende kracht van willekeur.
“Het is een heel belangrijk probleem,” zei Seth Pettieeen computerwetenschapper aan de Universiteit van Michigan, omdat veel van de gegevensstructuren waarop we vandaag vertrouwen opeenvolgend opslaan. Hij noemde het nieuwe werk “Extreem geïnspireerd (en) gemakkelijk een van mijn top drie favoriete papieren van het jaar.”
Grenzen beperken
Dus hoe meet men een goed gesorteerde boekenplank? Een veel voorkomende manier is om te zien hoe lang het duurt om een individueel item in te voegen. Dat hangt natuurlijk af van hoeveel items er in de eerste plaats zijn, een waarde die meestal wordt aangegeven door N. In het voorbeeld van Isabel Allende, wanneer alle boeken moeten bewegen om een nieuwe te huisvesten, is de tijd die nodig is om evenredig te zijn N. Hoe groter de Nhoe langer het duurt. Dat maakt dit een “bovengrens” aan het probleem: het zal nooit langer duren dan een tijd evenredig met N Om één boek aan de plank toe te voegen.
De auteurs van de paper uit 1981 die dit probleem ingeluid, wilden weten of het mogelijk was om een algoritme te ontwerpen met een gemiddelde invoegtijd veel minder dan N. En inderdaad, ze bewezen dat men het beter zou kunnen doen. Ze creëerden een algoritme dat gegarandeerd een gemiddelde invoegtijd zou bereiken die evenredig is aan (logboek N))2. Dit algoritme had twee eigenschappen: het was “deterministisch”, wat betekent dat de beslissingen niet afhankelijk waren van willekeur en het was ook “soepel”, wat betekent dat de boeken gelijkmatig moeten worden verspreid binnen de subsecties van de plank waar inserties (of verwijderingen) zijn gemaakt. De auteurs lieten de vraag open of de bovengrens nog verder kon worden verbeterd. Meer dan vier decennia heeft niemand erin geslaagd om dit te doen.
De tussenliggende jaren zagen echter verbeteringen in de ondergrens. Terwijl de bovengrens de maximaal mogelijke tijd aangeeft die nodig is om een boek in te voegen, geeft de ondergrens de snelst mogelijke invoegtijd. Om een definitieve oplossing voor een probleem te vinden, streven onderzoekers ernaar de kloof tussen de bovenste en ondergrenzen te beperken, idealiter totdat ze samenvallen. Wanneer dat gebeurt, wordt het algoritme als optimaal geacht – een ander begrensd van boven en onder, waardoor er geen ruimte is voor verdere verfijning.
