Die algoritme -masjien: 13 stappe (met foto's)

2024 Outeur: John Day | [email protected]. Laas verander: 2024-01-30 07:24

Ek het al 15 jaar rekenaarwetenskap op universiteitsvlak onderrig, en hoewel my kundigheid meer aan die programmeringskant is, bestee ek nogal baie tyd aan die dekking van standaardalgoritmes vir soek en sortering. Uit 'n onderrigoogpunt is die sentrale kwessie die berekeningskompleksiteit: hoeveel tyd benodig elke algoritme, gegewe insette van 'n spesifieke grootte? Maar daar is talle nuanses. Het die algoritmes byvoorbeeld verskillende tydsduur, afhangende van die spesifieke invoerwaardes (in teenstelling met die grootte)? In watter gevalle sou u een sorteeralgoritme bo 'n ander kies? Alhoewel ons hierdie kwessies in die opsomming bespreek, het dit my altyd ontstel dat daar geen maklike manier was om te sien hoe verskillende algoritmes onder verskillende omstandighede werk nie.

Doelwitte

My oorhoofse doelwit vir hierdie projek was om 'n interaktiewe vertoning vir studente te skep om algoritmes te visualiseer en te verken. Ek het my beperk tot algoritmes wat werk met waardes (heelgetalle), sodat ek 'n adresseerbare RGB LED -strook kan gebruik om die skikkinginhoud te visualiseer. Die skikking het 100 elemente en elke heelgetal word in 'n reënboogvolgorde in 'n kleur gekarteer, sodat dit onmiddellik duidelik is wanneer die skikking gesorteer, gedeeltelik gesorteer of gerandomiseer word. Benewens die waardes, wou ek egter 'n manier hê om beheeraspekte van die algoritme te visualiseer - byvoorbeeld watter elemente van die skikking tans vergelyk of verruil word.

Die spesifieke doelwitte is:

- Bied 'n verskeidenheid soek- en sorteeralgoritmes

- Visualiseer die waardes in die skikking op 'n manier wat die vordering van die algoritme beklemtoon

- Visualiseer algoritmebeheer; veral die elemente wat oorweeg word.

- Laat gebruikers toe om die invoerdatapatrone te kies eerder as om altyd ewekansige waardes te genereer

- Laat gebruikers toe om die snelheid te beheer en die algoritme te onderbreek

-Laat gebruikers toe om gedrag in die beste geval, in die ergste geval, in gemiddelde gevalle (algoritmespesifiek) te dwing

- Toon die aantal stappe soos die algoritme verloop

Visualisering

Vanuit 'n fisiese ontwerpoogpunt is die mees interessante deel van hierdie projek die visualisering van die skikking. Ek het gesukkel met hoe om die data en beheer te wys, en hoe om die skerm self te bou. My doel was om die datawaardes as gekleurde sirkels te wys en die kontrolepunte as gekleurde pyle wat na die datawaardes wys. Na 'n bietjie eksperimenteer het ek besluit op 'n ontwerp met twee parallelle stroke van 100 RGB LED's (WS2812) met 'n sirkelmasker oor elke data LED en 'n driehoekige masker oor elke LED. Ek het 'n 3D -model van die masker gemaak met 10 paar sirkels en driehoeke, en daarna het ek 10 van hierdie modules in 'n totaal van 100 sirkels en 100 driehoeke gedruk. Die grootte en spasiëring van my masker is ontwerp vir stroke met 100 LED's per meter. Die 3D -model lêers word later in hierdie beskrywing verskaf.

Elektronika en omhulsel

Die res van die toestel is eenvoudig, vanuit elektroniese oogpunt. Benewens die twee LED-stroke, is daar 'n klomp kort knoppies, 'n draaikodeerder (vir die snelheidsbeheer) en 'n 7-segment-skerm (om stappe te wys). Met soveel knoppies en kontroles het ek gekies om 'n ESP32 -mikrobeheerder te gebruik omdat dit baie penne blootstel en omdat dit redelik kragtig is. Ek sal die bedradingstrategie bespreek, maar dit is redelik basies. U kan waarskynlik iets slim met skofregisters doen as u minder penne wil gebruik.

U kan die omhulsel vir hierdie toestel in baie verskillende vorme bou. Ek het dit aanvanklik voorgestel as 'n groot reghoekige bord met die LED -strook aan die bokant, en 'n rooster knoppies in die middel. Die vorm waarmee ek beland het, is geïnspireer deur 'n soort siening van die tegnologie van die ruimte-eeu uit die 1960's. U kan dit ook bou met die LED -stroke in 'n vertikale oriëntasie. Of maak die LED -deel baie groter - vul 'n hele muur - met 'n aparte bedieningspaneel.

Sagteware

Die kode vir hierdie toestel is gratis beskikbaar op GitHub, en ek het my bes gedoen om te dokumenteer hoe dit werk en hoe om dit op te stel. Die enigste eksterne biblioteek wat u benodig, is FastLED om die WS2812 -stroke te bestuur.

Voorrade

Elektronika

1 ESP32 -ontwikkelbord (bv.

2 WS2812 of soortgelyke LED -stroke, digtheid 100 LED's per meter (bv.

1 "begin" -knoppie van die driehoek (bv.

12 kortstondige knoppies (byvoorbeeld https://amzn.com/B01N4D4750) - verskillende vorms as u wil

1 pak (20) voorbedrade knoppieverbindings (byvoorbeeld

1 Pak JST -verbindings (byvoorbeeld

1 Rotary encoder (bv.

1 Knop vir draaikodeerder (bv.

1 Pak Dupont -verbindings (byvoorbeeld https://amzn.com/B014YTPFT8) - dit is ook die moeite werd om die krimpgereedskap te kry.

1 vataansluiting (vir krag) (byvoorbeeld

1 TM1637 7-segment numeriese vertoning (byvoorbeeld

Soldeer- en bedradingstoerusting

3D -model lêers

U kan die 3D-model vind vir 'n paar 10-lig modules op Thingiverse:

www.thingiverse.com/thing:4178181

U moet hierdie model vyf keer druk vir 'n totaal van 10 modules.

Sagteware

github.com/samguyer/AlgorithmMachine

Omhulsel

Hout, plexiglas, boute en skroewe van vlekvrye staal

Verspreidingsmateriaal. My gunsteling is Lee Filters #216 vol wit diffusie, maar daar is ander opsies. Selfs gewone wit papier doen goeie werk.

Stap 1: Algoritmes 101

Baie mense dink dat rekenaarwetenskap in wese die studie van programmering is. Maar die ware hart en siel van hierdie veld is algoritmes: die studie van sistematiese prosedures vir die oplossing van probleme en die koste daarvan (gewoonlik hoe lank dit neem). Vooraanstaande persone in die veld, soos Alan Turing, Alonzo Church en Edsger Dijkstra, het aan hierdie idees gedink voordat rekenaars soos ons dit ken nog bestaan.

Die belangrikste kenmerk van 'n algoritme om 'n spesifieke probleem op te los, is dat dit gedetailleerd en presies is, sodat iemand dit kan gebruik om 'n oplossing te kry sonder om te verstaan hoe dit werk; volg net die stappe meganies en u kry die regte antwoord. U kan sien hoe dit help met die programmering van rekenaars, aangesien dit hierdie detailvlak benodig. 'N Rekenaar kan nie ontbrekende besonderhede invul of oordeel neem nie, net soos 'n persoon dit kan.

Hoe lank sal dit neem?

As ons eers 'n gedetailleerde prosedure het, is 'n natuurlike vraag: hoe lank sal dit neem om die antwoord te kry? Ons kan nie gewone tydseenhede gebruik nie, aangesien dit afhang van wie die werk verrig (vergelyk hoe vinnig 'n persoon iets teenoor 'n superrekenaar kan bereken). Boonop hang dit af van hoeveel data ons het. Dit is duidelik dat dit langer neem om 'n lys met 'n miljoen telefoonnommers te soek as 'n lys van honderd.

Om die koste van 'n algoritme te beskryf, kies ons eers 'n bewerking in die prosedure wat 'n 'stap' verteenwoordig - gewoonlik iets eenvoudig, soos om twee getalle te vergelyk of by te voeg, wat 'n vaste tyd neem. Dan kry ons 'n formule wat beskryf hoeveel stappe die algoritme sal neem, gegewe 'n aantal data -items. Om historiese redes dui ons byna altyd die aantal data -items met 'n hoofletter N.

Byvoorbeeld, deur 'n lys van N telefoonnommers te kyk, neem N stappe. Om twee keer deur die lys te kyk, neem 2N stappe. Albei word lineêre tydalgoritmes genoem - die totale aantal stappe is 'n veelvoud van die invoergrootte. Ander algoritmes is kwadraties (N kwadraat tyd) of kubieke (N blokkies) of logaritmies (log N) of 'n kombinasie hiervan. Sommige van die moeilikste rekenprobleme vereis eksponensiële tydalgoritmes (2^N).

OK, so wat?

As die aantal data -items N klein is, maak dit nie veel saak nie. Byvoorbeeld, vir N = 10, 10N is die naam as N in vierkant. Maar wat van N = 1000? of N = 1000000? 'N Miljoen kwadraat is 'n redelike groot getal. Selfs op 'n baie vinnige rekenaar kan 'n kwadratiese algoritme lank neem as die insette groot genoeg is. Eksponensiële algoritmes is baie lastiger: vir N = 50 sal 'n eksponensiële algoritme twee weke neem om te voltooi, selfs op 'n rekenaar waar elke stap slegs 'n nanosekonde (1 miljardste van 'n sekonde) is. Ai!

Aan die ander kant van die skaal het ons logaritmiese tydalgoritmes, wat baie vinnig is. Logtyd is die teenoorgestelde van eksponensiële tyd: gegewe invoergrootte N, is die aantal stappe die eksponent T in die formule 2^T = N. As ons insetgrootte byvoorbeeld een miljard is, benodig 'n logtydalgoritme slegs 30 stappe, aangesien 2^30 = 1, 000, 000, 000. Hoe soet is dit?! ??!

U wonder miskien: wie gee om vir insetgroottes van miljoene of miljarde? Dink daaraan: hoeveel gebruikers is daar op Facebook? Hoeveel webblaaie word deur Google geïndekseer? Hoeveel basispare is daar in die menslike genoom? Hoeveel metings gaan in 'n weersimulasie?

Stap 2: Die algoritmes

Die algoritme -masjien implementeer tans die volgende algoritmes. Twee daarvan is soekalgoritmes (vind 'n bepaalde waarde in die lys), die res is algoritmes om te sorteer (plaas die waardes in volgorde).

Lineêre soektog

Soek een vir een deur die lys waardes, van die begin af. Vereis lineêre tyd.

Binêre soektog

Soek 'n lys deur dit herhaaldelik in twee te verdeel. Vereis logtyd, maar die lys moet gesorteer word sodat dit kan werk.

Borrel sorteer

Sorteer 'n lys en herhaaldelik uitruil naburige elemente wat nie in orde is nie. Vereis kwadratiese tyd.

Invoeging sorteer

Sorteer 'n lys deur elke element op die regte plek in die lys met reeds gesorteerde waardes te plaas. Vereis kwadratiese tyd.

Quicksort

Sorteer 'n lys deur die lys herhaaldelik in twee te verdeel en al die waardes minder as die mediaan na die eerste helfte en al die waardes groter as die mediaan na die tweede helfte te skuif. In die praktyk kan ons die mediaan nie effektief vind nie, dus kies ons 'n willekeurige waarde. As gevolg hiervan kan hierdie algoritme in die ergste geval kwadraties wees, maar benodig gewoonlik N * logN -tyd.

Sorteer saam

Sorteer 'n lys deur dit in twee te deel, die twee helftes afsonderlik te sorteer (met behulp van saamvoeging) en dit dan saam te smelt deur die waardes in te skakel. Vereis altyd N * logN -tyd.

Hoop sorteer

Sorteer 'n lys deur 'n datastruktuur te bou wat 'n hoop genoem word, waarmee u die kleinste waarde in logtyd kan vind. Vereis altyd N * logN -tyd.

Bitoniese soort

Soortgelyk aan samesmelting en kwiksorting, deel 'n lys in twee, sorteer die helftes en kombineer dit weer. Hierdie algoritme benodig N * logN * logN -tyd, maar het die voordeel dat dit maklik kan paralleliseer.

Stap 3: LED -balk: 3D -druk die masker

Die eerste stap in die bou van die LED -balk is om die masker wat die ligte hul vorm gee, in 3D te druk. Elke module dek tien elemente van die skikking, 10 waardes (sirkels) en 10 aanwysers (driehoeke), dus benodig u altesaam 10 modules. Die STL -lêer wat ek hier verskaf, bevat twee gevalle van die module, dus u moet vyf druksiklusse uitvoer. Ek het nie die beste 3D -drukker nie, daarom moes ek dit met die hand skoonmaak met 'n lêer en skuurpapier. Die belangrikste is dat die sirkelvormige en driehoekige gate skoon is.

Op die foto's sien u my toetsopstelling: ek plak die twee LED -stroke vas en heg dit aan 'n broodbord met 'n mikrobeheerder. Hierdie stap is nie nodig nie, maar ek wou sien hoe dit sou lyk voordat ek die omhulsel begin monteer. Ek het die maskermodules op die twee LED -stroke opgestel en 'n eenvoudige skets met ewekansige kleure uitgevoer. Met 'n strook diffusiemateriaal verskyn die vorms en kleure regtig.

Stap 4: LED -balkalternatiewe

Toe ek die eerste keer met hierdie projek begin, het ek geëksperimenteer met ander maniere om die LED -masker te maak. As u nie 'n 3D -drukker het nie, kan u een van hierdie opsies oorweeg. Ek sal eerlik wees: dit is 'n groot pyn om hierdie dele te maak.

Vir die sirkels het ek 'n 13/32 koperbuis gekoop, wat amper 1 cm in deursnee is. Ek sny dit in honderd segmente van 1 cm en spuit dit dan wit.

Vir die driehoeke gebruik ek swaar aluminiumfoelie wat uit 'n weggooibare bak gesny is. Ek het 'n driehoekige vorm van hout gemaak en toe kort repies foelie om die vorm gedraai en dit vasgemaak. Weereens, u benodig honderd van hierdie dinge, so dit verg tyd en geduld.

Stap 5: LED -balkomhulsel

My omhulsel is redelik eenvoudig: twee stroke hout aan die kante en twee stroke plexiglas aan die bokant en onderkant. Al die dele is ongeveer 102 cm lank (1 meter vir die LED's, plus 'n bietjie ekstra vir die bedrading). Die sye moet 'n bietjie langer as 1 cm wees om plek te maak vir die LED -stroke. Nadat ek die stroke gesny het, het ek die 3D -gedrukte maskerstukke tussen hulle vasgemaak om die breedte van die plexiglas te meet. Sny twee stukke plexiglas in die breedte en lengte van die staaf. Sny laastens 'n strook van die diffusiemateriaal om oor die masker te pas.

Vir diffusie hou ek baie van Lee Filters #216 (vol wit diffusie). Dit is 'n dun plastiekvel wat egalige verspreiding gee sonder om baie lig te verloor. Maar dit is duur goed. Soms kan u kleiner velle aanlyn te koop kry, maar 'n hele rol kos u $ 125 terug. Ander opsies is wit papier of enige ander soort satyn of ryp plastiek. 'N Gewilde keuse is dun plastiek snymatte.

Voordat u die LED -balk monteer, moet u seker maak dat u die regte verbindings aan die LED -stroke gesoldeer het. Daar is baie stroke wat vooraf gesoldeer is, sodat u dit net kan gebruik.

Ek het die samestelling begin deur die boonste stuk plexiglas aan die houtkante vas te skroef (sien foto). Toe draai ek dit om en plaas die diffusiestrook, gevolg deur die 10 maskerstukke. Toe ek tevrede was met die afstand, het ek dit met 'n paar kolletjies warm gom vasgemaak.

Plaas die twee LED -stroke langs mekaar bo -op die maskers. Maak seker dat die LED's na onder wys en maak seker dat elke LED ooreenstem met die ooreenstemmende gaatjie in die masker. Voeg 'n bietjie warm gom of plakband om die LED -stroke vas te hou. Skroef laastens die agterkant van plexiglas vas.

Doen 'n toetspatroon. Mooi werk! Jy het die moeilikste deel gedoen!

Stap 6: Configuratiescherm

Die bedieningspaneel is die deel wat die meeste kreatiewe vryheid bied. Dit hoef net al die kontroles en elektronika saam met die LED -balk te hou. Die eenvoudigste ontwerp is 'n reghoekige planke: boor gate vir die knoppies en bedieningselemente, en heg die LED -balk vas. Ek kombineer graag hout, plexiglas en ander materiale om 'n soort steampunk / retro-moderne voorkoms te gee. In hierdie geval sny ek 'n stuk swaar plexiglas om die belangrikste algoritme-knoppies vas te hou, en 'n houtstaaf om die res van die elektronika te hou. Ek het gate geboor wat ooreenstem met die grootte van die arcade -knoppies. Die bedrading wys agterop, maar ek hou daarvan!

Ek het ook ruimte geboor vir die 7-segment-skerm, die draaikodeerder en 'n paar bedrading aan die agterkant. Ek sny 'n dado aan die bokant om die LED -balk vas te hou.

Stap 7: Knoopsnoer

Om baie knoppies aan te sluit, kan baie pyn veroorsaak. Gelukkig het die mense wat arcade -masjiene vervaardig, 'n paar standaardverbindings gekry wat u kan gebruik. Elke knoppie -aansluitkabel het twee drade, een vir VCC en een vir grond. Die een kant het spadeverbindings wat by die leidings aan die agterkant van die knoppie pas - maak die grond vas aan die "normaal oop" lood en VCC aan die "gewone" lood. As die gebruiker in hierdie konfigurasie op die knoppie druk, is die kring voltooi en die mikrobeheerder lees HOOG op die ooreenstemmende invoerpen.

Die ander kant van die kabel het 'n JST -aansluiting (die klein wit dingetjie). Wat aangenaam is met hierdie verbindings, is dat hulle slegs op een manier in die houer kom, sodat VCC en grond nie per ongeluk omgedraai kan word nie.

Wat ek gedoen het, is om 'n klein harnas vir hierdie verbindings te bou. Ek soldeer 'n reeks JST -houers op 'n stuk protobord en voer dan drade terug na Dupont -aansluitings wat ek in die mikrobeheerder aansluit. Die rooi draad is die VCC -lyn en sluit aan by al die JST -houers. Die blou drade is die een wat afsonderlik is vir elke knoppie.

Stap 8: Rotary Encoder

Met die roterende enkodeerder kan die gebruiker die snelheid van die algoritme beheer. Ek gebruik 'n module wat as 'n uitbreekbord kom, met optrekweerstands vir die twee datalyne (geel drade). Hierdie een is ook 'n knoppie, maar ek gebruik die funksie nie. Die ander twee drade is VCC en gemaal. Ek het ook 'n lekker vet knop gekry.

Wat ek van 'n draaikodeerder hou, in teenstelling met 'n potensiometer, is dat dit net 'n draai (met die kloksgewys en teen die kloksgewys) na die mikrokontroleerder dui, dus dit is maklik om te verander hoe die waarde geïnterpreteer word. U kan dit byvoorbeeld 'n gevoel van versnelling gee (soos 'n muis) as die gebruiker dit vinnig draai.

Stap 9: 7-segment vertoon

Hier is nie veel om te sê nie. Hierdie dinge is oral. Die LED's word beheer deur 'n chip genaamd TM1637, wat met 'n eenvoudige seriële protokol met die mikrokontroleerder kommunikeer. Ek gebruik 'n bestaande biblioteek waarmee ek kan vertel watter nommer ek wil wys, en die res.

Die agterkant het vier penne: VCC, grond en twee drade vir die seriële protokol. Ek het 'n 4-pins stuk kopstuk gesoldeer wat aansluit by 'n ooreenstemmende Dupont-aansluiting wat aan die mikrobeheerder gekoppel is.

Stap 10: Hoofbeheerraad

Die hoofbeheerbord bevat die mikrobeheerder self en al die verbindings met die kontroles (knoppies, skerm, LED's). Die mikrobeheerder is 'n ESP32, wat baie rekenaarkrag en geheue bied, en baie penne blootstel. Die bedrading is redelik standaard, maar ek wys 'n paar interessante stukkies op.

OPMERKING: U wil dalk na die kode kyk (https://github.com/samguyer/AlgorithmMachine) voordat u die hoofbord aansluit, sodat u speldkonfigurasie by my pas.

Ek het 'n vataansluiting op die bord gesoldeer vir krag, en twee stewige koperdrade aan die krag- en grondrails van die bord gekoppel. Die rede hiervoor is dat die LED -balk baie krag kan trek as die helderheid hoog is, en ek wil nie al die krag deur die USB -aansluiting op die mikrobeheerder trek nie.

Om die bedrading van die knoppie te vereenvoudig, het ek 'n strook reghoekige kop van man-tot-vrou langs die hele kant van die mikrokontroleerder (boonste kant van die bord, soos getoon), gesoldeer. Die Dupont -verbindings van die knoppieharnas word direk in hierdie kop geplaas.

BELANGRIK: die krag vir die knoppies (die rooi draad) moet aan die 3.3V -kraglyn op die mikrobeheerder gekoppel word. Die ESP32 is 'n 3.3V -chip, dus moet slegs 3.3V -bronne aan die datapennetjies geheg word.

Die mikrokontroleerder trek krag (of druk krag) na die relings (onderkant van die bord soos getoon) deur die 5V USB -pen en grond. Al die ander rooi/swart drade is VCC en gemaal.

Die twee blou drade is die data lyne vir die LED stroke (die WS2812s). Die geel/groen paar is die data lyne vir die roterende encoder, en die geel paar is die seriële verbinding met die 7-segment skerm.

Stap 11: Montering

Hierdie reeks foto's toon die finale samestelling en bedrading. Ek het ook die hoofbeheerbord aan die bokant aan die bokant vasgemaak.

Voordat ek dit aanskakel, het ek 'n paar keer gekontroleer om nare verrassings te vermy. In die besonder, om seker te maak dat ek geen krag/grondaansluitings agteruit het nie, en geen kortsluitings nie. Stel u multimeter in om te toets vir kontinuïteit - dit sal piep as daar 'n elektriese pad tussen die twee leidings is. Heg een draad aan die gewone VCC -lyn aan die knoppies. Heg dan die ander draad een vir een aan elke pen van die harnas vas. Die multimeter moet slegs piep as u op die knoppie druk. As u 'n ander pieptoon kry, beteken dit dat u 'n ommekeer of 'n kort het. Volg dit op en maak dit reg voordat u die krag aanskakel!

Stap 12: Kode

Maak eers u Arduino IDE oop en maak seker dat u die FastLED -biblioteek geïnstalleer het.

Laai die algoritme -masjienkode af van GitHub:

github.com/samguyer/AlgorithmMachine.git

U kan dit direk in u Arduino -gids kloon, of dit met die hand kopieer.

Voordat u dit oplaai, moet u seker maak dat die peninstellings by u hardeware -opset pas. Ek het al die peninstellings bo -aan die lêer geplaas.

Laai op en geniet!

Stap 13: Hoe om dit te gebruik

Die algoritme -masjien is eenvoudig om te gebruik en byna elke kombinasie van knoppies is ok!

Gebruik eers die dataknoppies om die waardes in die skikking te initialiseer. Daar is drie keuses: (1) ewekansig, (2) voeg een ewekansige waarde by en (3) keer die skikking om. Let op dat die waardes aanhoudend is, sodat u dinge kan doen soos om dit eers te sorteer, dan 'n bietjie geraas by te voeg en dan 'n ander sorteer- of soekalgoritme uit te voer.

Kies 'n soek- of sorteeralgoritme uit die ander knoppies. Tans is daar geen terugvoer as u hierdie keuse maak nie (iets vir toekomstige werk). Druk dan op die "speel" -knoppie.

Die knop beheer die spoed. U kan ook "speel" druk om die algoritme te onderbreek en te onderbreek.

Dit sal outomaties stop as dit klaar is. U kan ook te eniger tyd 'n ander algoritmeknoppie druk. Die masjien stop die huidige algoritme en initialiseer die nuwe, maar hou die data presies soos die vorige algoritme dit verlaat het.

Groot prys in die STEM -kompetisie