Datalogisk Sorteringsmesterskab ?

Jeg har hørt om folkvalg hele dagen og et af de faktisk problemer er tilsyneladende at sortere stemmeseddlerne.

Hvis jeg havde troet de ville forstå joken, havde jeg strakt hånden om bag mig og med mandig stemme sagt "Hurtigt Robin, giv mig Bat-Datalogen!"

Men helt seriøst taler vi altså om et konkret sorteringsproblem i maskinrummet på vores demokrati, der kan dårligt findes nogen mere ædelværdig måde for en datalog at bruge sin uddannelse.

Opgaven er kort og godt at opnå den mest præcise og hurtigste sortering og optælling af stemmesedler, udført på en "computer" der består af et antal helt almindelige mennesker der har meldt sig som valgtilforordnede.

Der må simpelthen være noget i Knuth's vol.3 der kan bruges, det jeg selv har oplevet var værre end bubblesort, hvilket ikke kan undre, da det er de færreste almindelige mennesker der nogensinde har tænkt på hvordan man sorterer tusindvis af noget som helst.

Men jeg synes faktisk vi skal malke denne chance helt og aldeles: Når der endelig kaldes på kavaleriet bør de dælme ankomme i fuldt galop med gjaldende trompeter!

Hvert universitet laver en intern konkurrence og stiller derefter med deres bedste hold.

Disse hold dyster imod hinanden om et år, I god tid før kommunalvalget in Nov 2013, så vi kan få spredt algoritmer, demokratiet til gavn.

Vi prøver samtidig at gøre det til en TV-begivenhed, for at reklamere for datalogi som uddannelse, evt. sammen med KL der gerne vil tiltrække unge valgtilforordnede.

Reglerne for konkurrence kunne være noget i stil med:

Et hold er 2 personer.

De får 10 tilfældige ikke-datalogiske valgtilforordnede de aldrig har mødt før, til at hjælpe sig med manuelt at sortere og optælle 12.000 simulerede stemmesedler.

Der skal produceres to resultater: Partistemmer og Personlige stemmer

Resultatet afgøres på tid for hver af de to resultater, men det koster et strafminut for hver stemme resultatet afviger fra facit.

Den helt centrale udfordring er naturligvis at man bliver nødt til at lave en masse tradeoff: Har folk lange nok arme til quicksort ? Kan man lave en 4-bånds mergesort hvis man bruger læsebriller ? Er heap-sort hurtigere at forklare og derfor hurtigere over-all ?

Det tilfører et vidunderligt aspekt af formidling og kommunikation til opgaven, men det vil unægteligt "cramp the style" for rigtige O()-dataloger.

Derfor laver vi også en kategori hvor dataloger ikke får handicap af almindelige mennesker:

Hvert universitet kan også stille deres bedste hold på seks trænede dataloger, der kæmper på præcis samme vilkår som de andre hold og derfor skal sortere dobbelt så hurtigt som de andre hold for at vinde.

Handsken er kastet venner, vis demokratiet hvad i duer til...

phk

Kommentarer (21)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Jesper Louis Andersen

Mit umiddelbare bud er at vi allerede har gang i en slags radix-sort for det her. Første "ciffer" er partiet og dernæst personstemmerne. Knuth's bind 3 nævner at nogen af disse algoritmer blev brugt af bibliotekarer til hurtigt at sortere store mængder data.

Der er oplagt at bare fordi en maskine er vildt god til at køre en 3-way randomized quicksort, så er det ikke oplagt at mennesker er det. Dermed er køretiden muligvis ikke den vigtigste faktor. En anden ting jeg ville overveje er PHKs metode med en køkkenvægt. Du vælger bare at bundte sedlerne i portioner som en køkkenvægt kan afgøre hurtigt. Dernæst kan du gøre det med en større vægt for mange bundter osv. Det giver en pæn rekursion der burde kunne sammentælle enormt hurtigt fordi den kan tælle i en log-faktor.

Mit bud er at du skal have gang i noget radix-lignende på laveste niveau, men det er kun hvad 5 minutters overvejelse giver mig.

  • 2
  • 0
Einar Petersen

Til dem der kræver monitært incitament og for hvem demokratiet ikke er nok så giver jeg gerne 150 DKK til hver af de to deltagere på det vindende hold, i form af et gavekort der skal bruges på Amazon eller Barnes and Noble til køb af computer relateret lekture. Jeg opfordrer V2's læsere til også at lave et pledge (vi kan godt diskutere hvordan gavekortet skal bruges, hvis Amazon eller Barnes and Noble ikke tænder)

Og til dem der skal køres lidt op og komme i stemning kan man gå ind og se denne herlige video The Sorter - Som i øvrigt kan bruges til at få den generelle befolkning til at forstå hvad for en sort magi der er tale om.

www.youtube.com/watch?v=2HjspVV0jK4

Det er en vido som betegnes som en Schoolhouse Rock-style video som kigger på forskellene imellem et par sorteringsalgoritmer.

"Producenten/uploaderen" er IT underviser og har i øvrigt lavet en række andre søde videoer f.eks. om den ottearmede blæksprutte der lærer at tælle til...

Håber PHK laver en formel konkurenceside - Evt. på Datamuseum.dk's hjemmeside - Så kan der genereres nogen trafik til den og mon ikke der kunne findes nogle corporate sponsors til en sådan konkurence også ?

  • 1
  • 0
Jens Katz-Kolberg

Stemmesedlerne skal vel ikke sorteres i datalogisk forstand, da der ikke er en naturlig rangordning af stemmesedlerne. Stemmesedlerne skal lægges i N bunker, hvor N er antallet af opstillede partier, og indenfor hver af partibunkerne, skal sedlerne lægges i bunker med de opstillede indenfor hvert parti. Først derefter skal de enkelte bunker sorteres efter antallet af stemmer i bunkerne.

Hvis vi skal blive i sorteringsalgoritmeanalogien, skal vi nok over i noget modificeret mergesort.

  • 1
  • 0
Henning Makholm

De gange jeg har været valgtilforordnet, har sorteringen på selve valgdagen (hvor man kun er interesseret i partilister, ikke i enkelte kandidater) kunnet klares med en simpel bucketsort -- evt med en fælles bunke til yderpartier og løsgængere hvor man så sorterer de få stemmesedler der ender i den ud i hånden bagefter.

De første gange jeg var med, chokerede det mig at de grovsorterede stemmesedler ikke bliver verificeret af andre tilforordnede efter de er endt i bunker. De bliver bare talt op som de er og indberettet til IM. Det der kan tage en masse tid er at være helt sikker på HVOR MANGE stemmesedler der er i hver bunke, så summen svarer præcis til antallet af udleverede blanke stemmesedler. Men om bunkerne har det rette INDHOLD er man ikke interesseret i på dét tidspunkt.

Dagen (eller dagene) efter bliver de så fintalt og tjekket, men det gøres (ihvertfald i Rødovre) ikke af tilforordnede fra partierne, men af kommunale embedsmænd. Det splintrede nogen af mine illusioner om det fine system med modstandernes gensidige kontrol af hinanden.

Så hvis der er et algoritmisk problem, er det nok ved fintællingen. Men jeg tror såmænd ikke engang egentlig problemet er algoritmisk -- bucket- eller radixsort virker stadig nær optimalt i denne situation. Det virkelige problem er at computerens inddataenhed (nemlig menneskeøjne) er for langsom, og bliver utilstedelig upålidelig hvis man forsøger at overclocke den.

Basalt set kan dét problem ikke løses ved en smartere algoritme. Hver stemmeseddel bliver nok ikke læst nævneværdigt flere gange end det med det forhåndendværende udstyr er nødvendigt at læse den for at opnå den ønskede pålidelighed.

Der er vist så nogen der forestiller sig at en form for OCR må være vejen frem -- men scannere og fødemekanismer der kan klare karton i stemmeseddelstørrelse efter det har været foldet sammen på diverse ukurante måder og i øvrigt mishandlet i stemmeurnerne (som ved visse valg ikke har været store nok til alle de leverede stemmesedler uden at blive stampet godt sammen undervejs) er nok ikke hyldevarer. Eller hvis de er, er det alligevel dyrt at indkøbe så mange af dem som man skal have i gang samtidig over hele landet én aften hvert andet år...

Så jeg kan sagtens se det umiddelbart tillokkende i at registrere stemmerne elektronisk samtidig med at de bliver afgivet. Jeg kan bare ikke se hvordan det skulle kunne lade sig gøre uden at sætte papirsystemets sikkerheden og gennemsigtighed over styr.

Det mest lovende i den retning vil nok være at have et apparat i stemmeboksen som printer den stemme man afgiver med OCR-venlig skrift på en stemmeseddel af et format der kan håndteres af almindeligt massescanningsudstyr, og så håbe på at kommunerne kan bruge massescannerne til noget fornuftigt i administrationen når der ikke lige er valg. Men det skaber stadig et problem med hvordan jeg bliver sikker på at apparatet i stemmeboksen ikke i smug logger hvilke stemmer der er afgivet hvornår...

  • 7
  • 0
Jens Katz-Kolberg

Naturligvis kan man altid omforme et klassifikationsproblem til et sorteringsproblem, ved at indføre en arbitrær rangordning af klasserne, men det er jo ikke sikkert at klassifikationsproblemet bliver hurtigere at løse på den måde. Hvis du har et bevis for at dette er tilfældet, vil jeg meget gerne se det.
En pointe er f.eks., at nogle mennesker vil være hurtigere til at lægge stemmesedlerne i bunker efter partinavnet, andre efter partibogstavet, og andre igen efter Løkkes parti/Helles parti/etc. Det kommer helt an på hvilken association, den enkelt får, når de ser stemmesedlen. Bunkerne behøver heller ikke at ligge på en ret linie foran den enkelte optæller, det kommer helt an på den enkelte. Mao. bør man ikke imho indføre en fælles rangordningskriterium optællerne ved den indledende klassifikation, andet end kravet om hvilke klasser man vil have.

  • 1
  • 0
Anders Wegge Keller

Jeg var valgtilforordnet ved sidste kommunalvalg, hvor jeg endte med at tælle stemmer til regionsrådsvalget. Det resultat vi skulle levere var "kun" fordelingen på lister. Det andet lag radix-sort stod de kommunalt ansatte for ved de efterfølgende dages fintælling.

Konkret endte optællingen hos os med en tre-bunkers strategi (A, V, resten), efterfulgt af en yderligere neddeling af "resten". Den algoritme skal dog tilpasses lidt efter hvornår på dagen den enkelte stemmeurne er blevet fyldt.

Rent sorteringsmæssigt er der nok ikke så meget at hente i forhold til det forlk allerede gør intuitivt, men der er nok snarere noget at hente på at pipeline processen.

1) Folde[1] stemmesedler ud, og vende dem rigtigt. ->
2) Grovsortere på de 2-3 største partier, samt "resten" ->
2a) Finsortere resten. ->
3) Bundte i størrelser på 25-50 og kontroltælle.

Hvis jeg må hive vilkårlige mekaniske hjælpemidler med mkig, vil jeg låne en seddeltæller i det nærmeste pengeinstitut, og benytte den i sidste del af pipelinen.

  1. I drømmer ikke om hvor meget folk kan krølle de &&#¤¤% papstykker sammen.
  • 3
  • 0
Henning Makholm

Hvis ikke det du selv beskriver kan omskrives til "sorteres efter antallet af cm fra øverste papirkant til krydset" ved jeg ikke hvordan en "datalogisk sortering" måtte se ud...

Jeg tror Jens' pointe var at det ville være acceptabelt at finde en eller anden skidesmart løsning der producerede de korrekte bunker i en anden evt. tilfældig rækkefølge.

Uheldigvis leder dén ekstra frihed bare ikke til nogen særlig nyttige åbninger. Den datalogiske brug af ordet "sortering" stammer jo fra engelsk "sort" som ret beset bare betyder "slags" -- altså netop at få lagt hver slags i sin bunke uden noget a priori hensyn til den indbyrdes rækkefølge af bunkerne. Det viser sig bare at den letteste måde at gøre det på er at vælge sig en rækkefølge en gang for alle, og derfor kom "to sort" i edb-sammenhæng til at betyde "lægge i den rigtige rækkefølge", ikke bare "lægge i de rette bunker". Sidstnævnte er i praksis ikke lettere at gøre end førstnævnte, selvom korrekthedskriteriet matematisk set er svagere.

  • 0
  • 0
Poul-Henning Kamp Blogger

De gange jeg har været valgtilforordnet, har sorteringen på selve valgdagen (hvor man kun er interesseret i partilister, ikke i enkelte kandidater) kunnet klares med en simpel bucketsort [...]

Opgaven som jeg stiller den dækker begge tællinger fordi det især var fintællingen der blev klaget over og fordi der er et sammenspil imellem hvorledes første sortering afleverer til anden sortering.

Så jeg kan sagtens se det umiddelbart tillokkende i at registrere stemmerne elektronisk [...]

Og det er der en masse andre problemer med at gøre, så den diskussion holder vi lige ude af denne blogs debat, der handler om en datalogisk sorteringsopgave.

  • 0
  • 0
Jens Katz-Kolberg

Henning,

Uheldigvis leder dén ekstra frihed bare ikke til nogen særlig nyttige åbninger.

Det vil jeg nu mene det gør. Hvis du får en tabel med alle stemmesedler i tidslig rækkefølge, og skal optælle stemmerne, så vil du vel ikke begynde med at sortere alle stemmesedlerne i tabellen ? Det er da meget hurtigere at køre tabellen igennem een gang og så opdatere antallet i hver klasse undervejs ?

  • 0
  • 0
Baldur Norddahl

Datalogernes sorteringsalgoritmer er optimeret til og under forudsætning af en bestemt maskinmodel. For eksempel er køretiden for at indsætte et element midt i et array O(n). Men hvor lang tid tager det mon at indsætte et kort midt i stakken af spillekort? Ja det tager O(1). Søgning i spillekortene kan gøres i O(lg(n)) på en allerede sorteret stak kort. Ergo har insertion-sort en køretid på O(n*lg(n)). Ikke helt det samme som på en computer...

Så alt du tror du ved om sorteringsalgoritmer gælder faktisk ikke for en "fysisk" sortering.

  • 5
  • 0
Anonym

Alt efter hvordan stemmerne vilkårligt fordeler sig, vil der være et antal ideelle resultater, på en sådan opstilling.
Der er tale om at sortere vilkårlige ind i et klassifikationssystem.

  • 0
  • 0
Torben Mogensen Blogger

Da jeg som ung var postafløser, skete sorteringen af breve på følgende måde:

  1. Postnummeret var opdelt i ca. 20 distrikter, så der var en reol med det samme antal store hylder, der var tilgængelige fra begge sider. Et hold arbejdere sorterede indkommende post på disse 20 hylder.

  2. Mens dette foregik, kom postomdelerne med jævne mellemrum rundt og hentede posten til deres distrikt fra disse hylder og gik hen til deres egne reoler, der var opdelt i ca. 25 rum, som typisk svarede til 1-2 gader (evt. kun lige eller ulige numre).

  3. Når der ikke var mere post at hente, sorteredes brevene i hvert rum med en blanding af bucket sort og insertion sort, hvor man i venstre hånd havde fire "buckets" mellem fingrene, hvori man indsatte brevene i rækkefølge. Som Baldur siger, er indsætning O(1), så det gik ret hurtigt. Brugen af buckets her havde primært til formål hurtigt at finde det sted, brevet skulle indsættes i rækkefølgen.

    1. Indholdet af hylderne sættes i posttasken i den rækkefølge, de skal uddeles, og omdeleren kører ud med sin post.

En lignende metode kunne sagtens bruges til stemmesortering, og efter de beskrivelser, der er givet herover, er det ikke langt fra sandheden. Blot sker den sekundære sortering (efter personlige stemmer). Valghandlinger har dog et ekstra element, der ikke findes i sortering: Optælling af stemmer. Her synes jeg PHKs forslag om at veje bundter af sedler er en god ide. Det skal nok være noget mere præcist end en køkkenvægt (der ikke altid er kalibreret rigtigt), men f.eks. en postvægt eller en slagtervægt (som jævnligt kontrolleres for præcision) kunne sagtens bruges. Her er det en fordel, at stemmesedlerne i Danmark er så kæmpestore: Præcisionen af almindelige post- eller slagtervægte er god nok til at se om der er 50 eller 51 sedler i et bundt.

  • 0
  • 0
Poul-Henning Kamp Blogger

Postnummeret var opdelt i ca. 20 distrikter, så der var en reol med ...

Vi har 1500 valgsteder og valg hvert andet år, så en af udfordringerne er at klare sig med så lidt "special-hardware" som muligt.

Dette skal naturligvis reflekteres i konkurrencens regler på passende vis.

(PS: en stemmeseddel vejer ca. 30 gram, det kan en køkkenvægt fint finde ud af.)

  • 1
  • 0
Christian Thoudahl

Jeg er game på den konkurrence... Tror da i øvrigt også jeg vil sende et brev til den lokale kommune med et tilbud om at påtage mig det borgerlige ombud hvis jeg ikke lige skal noget den dag alligevel.

  • 0
  • 0
Tom Paamand
  • der må være mange med tilsvarende erfaringer, også udenlands. Mit eget bud, hvis vi taler og halvmeters stemmesedler, er at starte opdelingen med at smide alle med nederste eller øverste halvdel udfyldt i hver sin bunke. Et ekstra led, men det kan gå forbandet hurtigt, og så skal næste og grundigere led ikke strække arme og hals så voldsomt.
  • 0
  • 0
Log ind eller Opret konto for at kommentere