Algoritm maskinen: 13 steg (med bilder)

2024 Författare: John Day | [email protected]. Senast ändrad: 2024-01-30 12:41

Jag har undervisat i datavetenskap på högskolenivå i 15 år, och även om min expertis är mer på programmeringssidan, lägger jag fortfarande ganska mycket tid på att täcka standardalgoritmer för sökning och sortering. Ur undervisningssynpunkt är den centrala frågan beräkningskomplexitet: hur mycket tid kräver varje algoritm med inmatning av en viss storlek? Men det finns många nyanser. Har algoritmerna till exempel olika drifttider beroende på de specifika inmatningsvärdena (i motsats till storleken)? I vilka fall skulle du välja en sorteringsalgoritm framför en annan? Även om vi diskuterar dessa frågor i sammandrag, bugade det mig alltid att det inte fanns något enkelt sätt att se hur olika algoritmer fungerar under olika förhållanden.

Mål

Mitt övergripande mål för detta projekt var att skapa en interaktiv display för studenter att visualisera och utforska algoritmer. Jag begränsade mig till algoritmer som arbetar med värdena (heltal), så jag kan använda en adresserbar RGB LED -remsa för att visualisera matrisinnehållet. Arrayen har 100 element, och varje heltal mappas till en färg i regnbågens ordning, så att det är omedelbart uppenbart när arrayen sorteras, delvis sorteras eller randomiseras. Förutom värdena ville jag dock ha ett sätt att visualisera kontrollaspekter av algoritmen - till exempel vilka element i matrisen som för närvarande jämförs eller byts.

De specifika målen är:

- Ge en mängd olika sök- och sorteringsalgoritmer

- Visualisera värdena i arrayen på ett sätt som belyser algoritmens framsteg

- Visualisera algoritmkontroll; särskilt de element som övervägs.

- Låt användarna välja inmatningsmönster snarare än att alltid generera slumpmässiga värden

- Låt användare kontrollera hastigheten och pausa algoritmen

-Låt användare tvinga fram bästa fall, värsta fall, genomsnittliga beteende (algoritmspecifikt)

- Visa antalet steg när algoritmen fortskrider

Visualisering

Ur en fysisk designsynpunkt är den mest intressanta delen av detta projekt visualisering av matrisen. Jag kämpade med hur man visar data och kontroll, och hur man bygger själva displayenheten. Mitt mål var att visa datavärdena som färgade cirklar och kontrollpunkterna som färgade pilar som pekar på datavärdena. Efter lite experimenterande bestämde jag mig för en design med två parallella remsor med 100 RGB -lysdioder (WS2812) med en cirkulär mask över varje data -LED och en triangulär mask över varje kontroll -LED. Jag gjorde en 3D -modell av masken med 10 par cirklar och trianglar och sedan 3D -utskrivna 10 av dessa moduler för totalt 100 cirklar och 100 trianglar. Storleken och avståndet på min mask är utformad för remsor med 100 lysdioder per meter. 3D -modellfilerna ges senare i denna beskrivning.

Elektronik och kapsling

Resten av enheten är enkel, ur elektronisk synvinkel. Förutom de två LED-remsorna finns det ett gäng tillfälliga knappar, en vridkodare (för hastighetsreglering) och en 7-segmentskärm (för att visa steg). Med så många knappar och kontroller valde jag att använda en ESP32 -mikrokontroller eftersom den utsätter många stift och för att den är ganska kraftfull. Jag ska gå igenom ledningsstrategin, men det är ganska grundläggande. Du kan nog göra något smart med skiftregister om du vill använda färre stift.

Du kan bygga höljet för den här enheten i många olika former. Jag föreställde mig inledningsvis som en stor rektangulär bräda med LED -remsan över toppen och ett rutnät med knappar i mitten. Formen jag slutade med är inspirerad av ett slags 1960-tals syn på rymdåldersteknik. Du kan också bygga den med LED -remsorna i vertikal orientering. Eller gör LED -delen mycket större - fyll en hel vägg - med en separat kontrollpanel.

programvara

Koden för den här enheten är fritt tillgänglig på GitHub, och jag har gjort mitt bästa för att dokumentera hur den fungerar och hur jag konfigurerar den. Det enda externa biblioteket du behöver är FastLED för att driva WS2812 -remsorna.

Tillbehör

Elektronik

1 ESP32 utvecklingskort (t.ex.

2 WS2812 eller liknande LED -remsor, densitet 100 lysdioder per meter (t.ex.

1 Startknapp för triangeln (t.ex.

12 tillfälliga knappar (t.ex. https://amzn.com/B01N4D4750) - olika former om du vill

1 paket (20) förkopplade knappkontakter (t.ex.

1 Pack JST -kontakter (t.ex.

1 roterande kodare (t.ex.

1 Vred för roterande pulsgivare (t.ex.

1 Pack Dupont -kontakter (t.ex. https://amzn.com/B014YTPFT8) - det är också värt att få krympverktyget.

1 fatuttag (för ström) (t.ex.

1 TM1637 7-segment numerisk display (t.ex.

Löd- och ledningsutrustning

3D -modellfiler

Du kan hitta 3D-modellen för ett par 10-ljusmoduler på Thingiverse:

www.thingiverse.com/thing:4178181

Du måste skriva ut den här modellen fem gånger för totalt 10 moduler.

programvara

github.com/samguyer/AlgorithmMachine

Inhägnad

Trä, plexiglas, bultar och skruvar i rostfritt stål

Diffusionsmaterial. Min favorit är Lee Filters #216 full vit diffusion, men det finns andra alternativ. Även vanligt vitt papper gör ett bra jobb.

Steg 1: Algoritmer 101

Många tror att datavetenskap är i huvudsak studier av programmering. Men det verkliga hjärtat och själen i detta område är algoritmer: studier av systematiska procedurer för att lösa problem och deras kostnader (vanligtvis hur lång tid de tar). Häftiga personer i fältet, som Alan Turing, Alonzo Church och Edsger Dijkstra, tänkte på dessa idéer innan datorer som vi känner till dem existerade.

Nyckelfunktionen i en algoritm för att lösa ett visst problem är att det är detaljerat och exakt, så att någon kan använda det för att få en lösning utan att förstå hur det fungerar alls; följ bara stegen på ett mekaniskt sätt så får du rätt svar. Du kan se hur detta hjälper med programmering av datorer, eftersom de behöver denna detaljnivå. En dator kan inte fylla i saknade detaljer eller göra bedömningar, så som en person kan.

Hur lång tid tar det?

När vi väl har ett detaljerat förfarande är en naturlig fråga hur lång tid det tar att få svaret? Vi kan inte använda vanliga tidsenheter, eftersom det beror på vem som utför arbetet (jämför hur snabbt en person kan beräkna något kontra en superdator). Dessutom beror det på hur mycket data vi har. Det tar uppenbarligen längre tid att söka i en lista med en miljon telefonnummer än en lista med hundra.

För att beskriva kostnaden för en algoritm väljer vi först en operation i proceduren som representerar ett "steg" - vanligtvis något enkelt, som att jämföra eller lägga till två tal, som tar en viss tid att göra. Sedan kommer vi fram till en formel som beskriver hur många steg algoritmen kommer att ta med ett visst antal dataobjekt. Av historiska skäl betecknar vi nästan alltid antalet dataobjekt med stort N.

Till exempel, genom att titta igenom en lista med N -telefonnummer krävs N -steg. Att titta igenom listan två gånger tar 2N steg. Båda dessa kallas linjära tidsalgoritmer - det totala antalet steg är en multipel av ingångsstorleken. Andra algoritmer är kvadratisk (N kvadrat tid) eller kubik (N kubad) eller logaritmisk (log N) eller någon kombination av dessa. Några av de svåraste beräkningsproblemen kräver exponentiella tidsalgoritmer (2^N).

Okej, så vad?

När antalet dataposter N är litet spelar det ingen större roll. Till exempel, för N = 10, är 10N det namnet som N i kvadrat. Men hur är det med N = 1000? eller N = 1000000? En miljon i kvadrat är ett ganska stort antal. Även på en mycket snabb dator kan en kvadratisk algoritm ta lång tid om ingången är tillräckligt stor. Exponentiella algoritmer är mycket mer besvärliga: för N = 50 skulle en exponentiell algoritm ta två veckor att slutföra även på en dator där varje steg bara är en nanosekund (1 miljarddel av en sekund). aj!

I andra änden av skalan har vi logaritmiska tidsalgoritmer, som är mycket snabba. Loggtiden är motsatsen till exponentiell tid: med inmatningsstorlek N är antalet steg exponenten T i formeln 2^T = N. Om vår inmatningsstorlek till exempel är en miljard, kräver en loggtidsalgoritm bara 30 steg, eftersom 2^30 = 1, 000, 000, 000. Hur sött är det?! ??!

Du kanske undrar, vem bryr sig om inmatningsstorlekar på miljoner eller miljarder? Tänk efter: hur många användare finns det på Facebook? Hur många webbsidor indexeras av Google? Hur många baspar finns det i det mänskliga genomet? Hur många mätningar går in i en vädersimulering?

Steg 2: Algoritmerna

Algoritmmaskinen implementerar för närvarande följande algoritmer. Två av dem är sökalgoritmer (hitta ett visst värde i listan), resten är sorteringsalgoritmer (sätt ordning på värdena).

Linjär sökning

Sök igenom listan över värden en efter en från början. Kräver linjär tid.

Binär sökning

Sök i en lista genom att upprepade gånger dela den i hälften. Kräver loggtid, men listan måste sorteras för att den ska fungera.

Bubbla sortera

Sortera en lista och utbyter upprepade gånger närliggande element som inte är i ordning. Kräver kvadratisk tid.

Insättningssort

Sortera en lista genom att placera varje element på rätt plats i listan över redan sorterade värden. Kräver kvadratisk tid.

Quicksort

Sortera en lista genom att upprepade gånger dela listan i hälften och flytta alla värden mindre än medianen till den första halvan och alla värden som är större än medianen till den andra halvan. I praktiken kan vi inte effektivt hitta medianen, så vi väljer ett värde slumpmässigt. Som en följd av detta kan denna algoritm vara kvadratisk i värsta fall, men kräver vanligtvis N * logN -tid.

Slå ihop sortering

Sortera en lista genom att dela den på mitten, sortera de två halvorna separat (med kopplingssortering) och sedan slå ihop dem genom att sammanfoga värdena. Kräver alltid N * logN -tid.

Heap sort

Sortera en lista genom att bygga en datastruktur som kallas en hög, som låter dig hitta det minsta värdet i loggtid. Kräver alltid N * logN -tid.

Bitonisk sort

På samma sätt som sammanslagningssortering och kvicksort, dela en lista i hälften, sortera halvorna och kombinera dem igen. Denna algoritm kräver N * logN * logN -tid, men har fördelen att det är lätt att parallellisera.

Steg 3: LED -stapel: 3D -utskrift av masken

Det första steget i att bygga LED -fältet är att 3D -skriva ut masken som ger lamporna deras form. Varje modul täcker tio element i matrisen, 10 värden (cirklar) och 10 indikatorer (trianglar), så du behöver totalt 10 moduler. STL -filen jag tillhandahåller här innehåller två instanser av modulen, så du måste göra fem utskriftscykler. Jag har inte den bästa 3D -skrivaren, så jag var tvungen att rengöra dem manuellt med hjälp av en fil och sandpapper. Det viktigaste är att de cirkulära och triangulära hålen är rena.

På bilderna ser du min testinställning: Jag tejpade ner de två LED -remsorna och kopplade dem till en brödbräda med en mikrokontroller. Det här steget är inte nödvändigt, men jag ville se hur det skulle se ut innan jag började montera höljet. Jag ställde upp maskmodulerna på de två LED -remsorna och körde en enkel skiss med slumpmässiga färger. Med en remsa av diffusionsmaterialet dyker formerna och färgerna verkligen upp.

Steg 4: LED -baralternativ

När jag först startade detta projekt experimenterade jag med andra sätt att göra LED -masken. Om du inte har en 3D -skrivare kan du överväga ett av dessa alternativ. Jag ska vara ärlig: det är en enorm smärta att göra dessa delar.

Till cirklarna köpte jag ett 13/32 mässingsrör, som är nästan exakt 1 cm i diameter. Jag skar den i hundra 1 cm segment och spraymålade dem sedan vita.

Till trianglarna använde jag tung aluminiumfolie skuren från en engångsform. Jag gjorde en triangulär form av trä, svepte sedan korta folieremsor runt formen och tejpade dem. Återigen behöver du hundra av dessa saker, så det tar lite tid och tålamod.

Steg 5: LED -stångskåp

Mitt hölje är ganska enkelt: två remsor av trä för sidorna och två remsor av plexiglas för toppen och botten. Alla delar är cirka 102 cm långa (1 meter för lysdioderna, plus lite extra för att rymma ledningarna). Sidorna ska vara lite högre än 1 cm för att få plats med LED -remsorna. Efter att ha klippt remsorna klämde jag in de 3D -tryckta maskbitarna mellan dem för att mäta bredden för plexiglaset. Skär två bitar av plexiglas på stångens bredd och längd. Skär slutligen en remsa av diffusionsmaterialet så att det passar över masken.

För diffusion gillar jag verkligen Lee Filters #216 (full vit diffusion). Det är ett tunt plastark som ger jämn diffusion utan att förlora mycket ljus. Men det är dyra grejer. Ibland kan du hitta mindre ark till salu online, men en hel rulle ger dig tillbaka $ 125. Några andra alternativ är vitt papper eller någon annan form av satin eller frostad plast. Ett populärt val är tunna skärmattor av plast.

Innan du monterar LED -baren, se till att du har lämpliga kontakter lödda på LED -remsorna. Många remsor har förlödda ledningar, så du kan bara använda dem.

Jag började montera med att skruva fast den övre delen av plexiglas på träsidorna (se bild). Sedan vände jag den och placerade diffusionsremsan i, följt av de 10 maskbitarna. När jag var nöjd med avståndet fästade jag dem på plats med några punkter varmt lim.

Lägg sedan de två LED -remsorna sida vid sida ovanpå maskerna. Se till att lysdioderna vänder nedåt och se till att varje lysdiod står i linje med motsvarande hål i masken. Lägg till lite lim eller tejp för att hålla LED -remsorna på plats. Slutligen skruva fast bakstycket av plexiglas.

Kör ett testmönster. Bra jobb! Du har gjort det svåraste!

Steg 6: Kontrollpanelen

Kontrollpanelen är den del som ger den mest kreativa friheten. Det behöver bara hålla alla kontroller och elektronik, tillsammans med LED -fältet. Den enklaste designen är en rektangulär bräda: borra hål för knapparna och kontrollerna och fäst LED -stången. Jag gillar att kombinera trä, plexiglas och andra material för att ge ett slags steampunk / retro-modernt utseende. I det här fallet skär jag en bit kraftigt plexiglas för att hålla de viktigaste algoritmvalsknapparna och en trästång för att hålla resten av elektroniken. Jag borrade hål för att matcha storleken på arkadknapparna. Ledningarna visar på baksidan, men jag gillar det!

Jag borrade också ut utrymme för 7-segmentskärmen, den roterande givaren och några av ledningarna på baksidan. Jag skar en dado i toppen för att hålla LED -fältet.

Steg 7: Knappsele

Att koppla in många knappar kan vara en riktig smärta. Lyckligtvis har de som tillverkar arkadmaskiner kommit på några standardkontakter som du kan använda. Varje knappkontaktkabel har två ledningar, en för VCC och en för jord. Ena änden har spadekontakter som passar ledningarna på baksidan av knappen - fäst marken till den "normalt öppna" ledningen och VCC till den "vanliga" kabeln. I denna konfiguration, när användaren trycker på knappen, är kretsen klar och mikrokontrollern kommer att läsa HÖG på motsvarande ingångsstift.

Den andra änden av kabeln har en JST -kontakt (den lilla vita saken). Det som är trevligt med dessa kontakter är att de bara går in i behållaren på ett sätt, så det finns inget sätt att av misstag vända VCC och jord.

Det jag gjorde är att bygga en liten sele för dessa kontakter. Jag lödar en serie JST -behållare på en bit protoboard och kör sedan ledningar tillbaka till Dupont -kontakter som jag ska ansluta till mikrokontrollen. Den röda tråden är VCC -linjen och den ansluts till alla JST -behållare. De blå trådarna är de som är separata för varje knapp.

Steg 8: Rotary Encoder

Den roterande kodaren låter användaren styra algoritmens hastighet. Jag använder en modul som kommer som en utbrottskort som innehåller uppdragningsmotstånd för de två datalinjerna (gula ledningar). Den här råkar också vara en knapp, men jag använder inte den funktionen. De andra två ledningarna är VCC och mark. Jag fick också en fin fet knopp.

Det jag gillar med en roterande kodare, till skillnad från en potentiometer, är att den bara signalerar rotation (medurs moturs) till mikrokontrollern, så det är enkelt att ändra hur värdet tolkas. Till exempel kan du ge den en känsla av acceleration (som en mus) när användaren snurrar snabbt.

Steg 9: 7-segment Display

Inte mycket att säga här. Dessa saker finns överallt. Lysdioderna styrs av ett chip som kallas TM1637, som kommunicerar med mikrokontrollern genom ett enkelt seriellt protokoll. Jag använder ett befintligt bibliotek som låter mig berätta vilket nummer jag vill visa, och det gör resten.

Baksidan har fyra stift: VCC, jord och två ledningar för det seriella protokollet. Jag lödde en 4-stifts rubrik, som ansluts till en motsvarande Dupont-kontakt som är ansluten till mikrokontrollern.

Steg 10: Huvudstyrkort

Huvudkontrollkortet innehåller själva mikrokontrollen och alla kontakter till kontrollerna (knappar, display, lysdioder). Mikrokontrollern är en ESP32, som ger mycket datorkraft och minne, och exponerar massor av stift. Ledningarna är ganska standard, men jag ska peka på några intressanta bitar.

OBS: Du kanske vill titta på koden (https://github.com/samguyer/AlgorithmMachine) innan du börjar ansluta huvudkortet så att din pin -konfiguration matchar min.

Jag lödde ett fatuttag på brädet för att få ström och kopplade två biffiga koppartrådar till brädans kraft- och jordskenor. Anledningen är att LED -fältet kan dra mycket ström om ljusstyrkan är hög, och jag vill inte dra all den strömmen genom USB -kontakten på mikrokontrollen.

För att förenkla kabeldragningen lödde jag en remsa av en manlig till en kvinnlig rätvinklig rubrik längs hela sidan av mikrokontrollen (ovansidan av brädet enligt bilden). Dupont -kontakterna från knappselen kopplas direkt till denna rubrik.

VIKTIGT: strömmen för knapparna (den röda ledningen) måste anslutas till 3,3V -strömledningen på mikrokontrollen. ESP32 är ett 3,3V -chip, så endast 3,3V -källor ska någonsin anslutas till datastiften.

Mikrokontrollern drar ström (eller skjuter ström) till skenorna (nedre sidan av kortet som visas) genom 5V USB -stift och jord. Alla andra röda/svarta trådar är VCC och slipade.

De två blå ledningarna är datalinjerna för LED -remsorna (WS2812s). Det gula/gröna paret är datalinjerna för den roterande kodaren, och det gula paret är den seriella anslutningen till 7-segmentskärmen.

Steg 11: Montering

Denna fotoserie visar den slutliga monteringen och kabeldragningen. Jag fäst också huvudkontrollkortet på baksidan högst upp.

Innan jag startade den gjorde jag några kontroller för att undvika otäcka överraskningar. I synnerhet för att se till att jag inte hade några ström/jordkontakter bakåt och inga kortslutningar. Ställ in din multimeter för att testa kontinuitet - den kommer att pipa när det finns en elektrisk väg mellan de två avledningarna. Fäst en ledning till den gemensamma VCC -linjen på knapparna. Fäst sedan den andra ledningen på varje stift i selen en efter en. Multimetern ska bara pipa när du trycker på knappen. Om du får andra pip betyder det att du har en vändning eller en kort. Spåra upp det och åtgärda det innan du slår på strömmen!

Steg 12: Kod

Öppna först din Arduino IDE och se till att FastLED -biblioteket är installerat.

Ladda ner Algorithm Machine -koden från GitHub:

github.com/samguyer/AlgorithmMachine.git

Du kan antingen klona det direkt i din Arduino -mapp eller kopiera in det för hand.

Innan du laddar upp den, se till att stiftinställningarna matchar din maskinvarukonfiguration. Jag har placerat alla pin -inställningar högst upp i filen.

Ladda upp och njut!

Steg 13: Hur man använder

Algoritm maskinen är enkel att använda och nästan alla kombinationer av knappar är ok!

Använd först dataknapparna för att initiera värdena i matrisen. Det finns tre val: (1) randomisera, (2) lägga till ett slumpmässigt värde och (3) vända arrayen. Observera att värdena är beständiga, så du kan göra saker som att sortera dem först, sedan lägga till lite brus och sedan köra en annan sorterings- eller sökalgoritm.

Välj en sök- eller sorteringsalgoritm från de andra knappvalen. För närvarande finns det ingen feedback när du gör detta val (något för framtida arbete). Tryck sedan på "spela" -knappen.

Vredet styr hastigheten. Du kan också trycka på "spela" för att pausa och avbryta algoritmen.

Det stannar automatiskt när det är klart. Du kan också trycka på en annan algoritmknapp när som helst. Maskinen stoppar den aktuella algoritmen och initierar den nya, men behåller data exakt som den tidigare algoritmen lämnade den.

Stora priset i STEM -tävlingen