Share
Dit artikel zal ingaan op de principes van algoritmeontwerp. Als je geen idee hebt waar ik het over heb, lees dan verder!
Wanneer u het woord 'algoritme' hoort, reageert u waarschijnlijk op een van de volgende drie manieren:
Als u een van de tweede twee bent, is dit artikel iets voor u.
Algoritmen zijn niet noodzakelijk een speciaal soort bewerking. Ze zijn conceptueel, een reeks stappen die je in de code neemt om een specifiek doel te bereiken.
Algoritmen zijn vaak in eenvoudige termen gedefinieerd als "instructies voor het voltooien van een taak". Ze zijn ook "recepten" genoemd. In Het sociale netwerk, een algoritme is wat Zuckerberg nodig had om Facemash te laten werken. Als je de film zag, herinner je je waarschijnlijk dat je zag wat een gekrabbelvergelijking leek op een raam in de slaapzaal van Mark. Maar wat heeft die bekende algebra te maken met Mark's eenvoudige "hete of niet" -site?
Algoritmen zijn inderdaad instructies. Misschien is een meer accurate beschrijving dat algoritmen patronen zijn om een taak op een efficiënte manier uit te voeren. Zuckerberg's Facemash was een stemsite om iemands aantrekkelijkheid ten opzichte van een hele groep mensen te bepalen, maar de gebruiker zou alleen opties tussen twee mensen krijgen. Mark Zuckerberg had een algoritme nodig dat beslist welke mensen op elkaar zouden aansluiten en hoe een waardering te waarderen ten opzichte van de voorgeschiedenis van die persoon en eerdere kanshebbers. Dit vereiste meer intuïtie dan alleen het tellen van stemmen voor elke persoon.
Stel dat u bijvoorbeeld een algoritme wilt maken om 1 toe te voegen aan een negatief getal en 1 af te trekken van een positief getal en niets aan 0 toe te voegen. U kunt zoiets doen (in JavaScript-achtige pseudo-code):
functie addOrSubtractOne (getal) if (nummer < 0) return number + 1 else if (number < 0) return number - 1 else if (number == 0) return 0;
Je zegt misschien tegen jezelf: "Dat is een functie." En je hebt gelijk. Algoritmen zijn niet noodzakelijk een speciaal soort bewerking. Ze zijn conceptueel - een reeks stappen die je in de code neemt om een specifiek doel te bereiken.
Dus waarom zijn ze een big deal? Het is duidelijk dat het toevoegen of aftrekken van 1 aan een getal tamelijk eenvoudig is.
Maar laten we het even over zoeken hebben. Als u naar een nummer in een reeks getallen wilt zoeken, hoe zou u dat dan denken? Een naïeve benadering zou zijn om het nummer te herhalen en elk nummer te vergelijken met het nummer waarnaar u zoekt. Maar dit is geen efficiënte oplossing en heeft een zeer breed bereik van mogelijke voltooiingsmomenten, waardoor het een grillige en onbetrouwbare zoekmethode is wanneer geschaald naar grote zoeksets.
function naiveSearch (needle, haystack) for (var i = 0; i < haystack.length; i++) if (haystack[i] == needle) return needle; return false;
Gelukkig kunnen we het beter doen dan dit voor zoeken.
Er is geen betere manier om een betere ontwerper voor algoritmen te worden dan om een diep begrip en waardering voor algoritmen te hebben.
Laten we zeggen dat uw array 50.000 vermeldingen heeft en u zoekt brute kracht (dat wil zeggen, zoek door de volledige array te herhalen). Het item dat u zoekt, in het beste geval, is het eerste item in de 50.000 invoerreeks. In het slechtste geval duurt het algoritme echter 50.000 keer langer dan in het beste geval.
In plaats daarvan zou u zoeken met binaire opzoekingen. Dit houdt in het sorteren van de array (waarover ik je alleen laat leren) en vervolgens de array in tweeën deelt, en controleer of het zoeknummer groter of kleiner is dan de markering halverwege in de array. Als het groter is dan het middenpad van een gesorteerde array, weten we dat de eerste helft kan worden weggegooid, omdat het gezochte getal geen deel uitmaakt van de array. We kunnen ook veel werk verwijderen door de buitenste grenzen van de array te definiëren en te controleren om te zien of het gezochte nummer buiten die grenzen bestaat, en zo ja, dan hebben we een handeling met meerdere iteraties genomen en deze omgezet in een enkele iteratiebewerking (die in het brute force-algoritme 50.000 bewerkingen zou hebben uitgevoerd).
sortedHaystack = recursiveSort (hooiberg); functie bSearch (needle, sortedHaystack, firstIteration) if (firstIteration) if (needle> sortedHaystack.last || needle < sortedHaystack.first) return false; if (haystack.length == 2) if (needle == haystack[0]) return haystack[0]; else return haystack[1]; if (needle < haystack[haystack.length/2]) bSearch(needle, haystack[0… haystack.length/2 -1], false); else bSearch(needle, haystack[haystack.length/2… haystack.length], false);
Neem het ogenschijnlijk gecompliceerde karakter van een enkel binair zoekalgoritme en pas het toe op miljarden mogelijke koppelingen (zoals zoeken via Google). Laten we daarna een soort classificatiesysteem toepassen op die gekoppelde zoekopdrachten om een volgorde van reactiepagina's te geven. Beter nog, pas een soort van schijnbaar willekeurig "suggestie" -systeem toe op basis van kunstmatige intelligentie sociale modellen om te identificeren wie je als vriend zou willen toevoegen.
Dit geeft ons een veel duidelijker begrip van waarom algoritmen meer zijn dan alleen een mooie naam voor functies. Op hun best zijn het slimme, efficiënte manieren om iets te doen dat een hoger niveau van intuïtie vereist dan de meest voor de hand liggende oplossing. Ze kunnen nemen wat zou kunnen vereisen een supercomputer jaar te doen en het veranderen in een taak die in seconden eindigt op een mobiele telefoon.
Voor de meesten van ons als ontwikkelaars ontwerpen we geen op hoog niveau geabstraheerde algoritmen op dagelijkse basis.
Gelukkig staan we op de schouders van de ontwikkelaars die voor ons kwamen, die native sort-functies schreven en ons in staat stelden om op een efficiënte manier naar substrings te zoeken met indexOf.
Maar we DOEN echter wel eigen algoritmen. We creëren voor loops en schrijffuncties elke dag; dus hoe kunnen goede ontwerpprincipes voor algoritmen het schrijven van deze functies informeren??
Een van de belangrijkste principes van algoritmisch ontwerp is om, indien mogelijk, uw algoritme zodanig te bouwen dat de invoer zelf een deel van het werk voor u doet. Als u bijvoorbeeld weet dat uw invoer altijd getallen zal zijn, hoeft u geen uitzonderingen / controles op tekenreeksen te hebben of uw waarden in getallen te forceren. Als je weet dat je DOM-element elke keer hetzelfde is in a voor loop in JavaScript, je zou niet naar dat element moeten zoeken in elke iteratie. Op dezelfde manier, in jouw voor loops, zou u geen gemaksfuncties met overhead moeten gebruiken als u hetzelfde kunt bereiken met (dichterbij) eenvoudige handelingen.
Accentsconagua
// doe dit niet: for (var i = 1000; i> 0; i -) $ ("# foo"). append ("bar"); // doe dit in plaats daarvan var foo = $ (" # foo "); var s =" "; for (var i = 1000; i> 0; i -) s + ="bar"; foo.append (s); Als u een JavaScript-ontwikkelaar bent (en u gebruikt jQuery) en u weet niet wat de bovenstaande functies doen en hoe deze aanzienlijk verschillen, is het volgende punt voor u.
Op hun best zijn [algoritmen] slimme, efficiënte manieren om iets te doen dat een hoger niveau van intuïtie vereist dan de meest voor de hand liggende oplossing.
Het is gemakkelijk om te denken dat dit vanzelfsprekend is. Er is echter een verschil tussen "weten hoe jQuery te schrijven" en "jQuery begrijpen". Als u uw hulpmiddelen begrijpt, betekent dit dat u begrijpt wat elke regel code doet, zowel onmiddellijk (de retourwaarde van een functie of het effect van een methode) en impliciet (hoeveel overhead is gekoppeld aan het uitvoeren van een bibliotheekfunctie of welke het meest efficiënt is). methode voor het aaneenschakelen van een string). Om geweldige algoritmen te schrijven, is het belangrijk om de prestaties te kennen van functies of hulpprogramma's op een lager niveau, niet alleen de naam en implementatie ervan.
Het ontwerpen van efficiënte algoritmen is een verbintenis van volledige betrokkenheid. Naast het begrijpen van je tools als een op zichzelf staand stuk, moet je ook begrijpen hoe ze omgaan met het grotere systeem dat voorhanden is. Als u JavaScript in een specifieke toepassing bijvoorbeeld volledig wilt begrijpen, is het belangrijk om inzicht te hebben in de DOM en prestaties van JavaScript in scenario's voor meerdere browsers, hoe beschikbaar geheugen van invloed is op rendering-snelheden, de structuur van servers (en hun antwoorden) waarmee u mogelijk te maken hebt, evenals een groot aantal andere overwegingen die ongrijpbaar zijn, zoals gebruiksscenario's.
Over het algemeen is het doel van algoritmeontwerp om een taak in minder stappen af te ronden. (Er zijn enkele uitzonderingen, zoals hash van Bcrypt.) Houd rekening met het volgende wanneer u uw code schrijft allemaal van de eenvoudige handelingen die de computer uitvoert om het doel te bereiken. Hier is een eenvoudige checklist om aan de slag te gaan op een pad naar efficiënter algoritmisch ontwerp:
Er is geen betere manier om een betere ontwerper voor algoritmen te worden dan om een diep begrip en waardering voor algoritmen te hebben.
.soort(), met bewerkingen op lager niveau. Als u niet wist wat een algoritme aan het begin van dit artikel was, heeft u hopelijk nu een meer concreet begrip van de enigszins ongrijpbare term. Als professionele ontwikkelaars is het belangrijk dat we begrijpen dat de code die we schrijven kan worden geanalyseerd en geoptimaliseerd, en het is belangrijk dat we de tijd nemen om deze analyse van de prestaties van onze code te doen..
Met een leuk algoritme oefen je problemen die je hebt gevonden? Misschien een dynamisch programmeerbaar 'knapzakprobleem' of 'dronkenwandeling'? Of misschien ken je een aantal best practices van recursie in Ruby die verschillen van dezelfde functies die in Python zijn geïmplementeerd. Deel ze in de reacties!
