Merken

Sorting Rubyists

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
genes and here and uh at always where got the Griffin doors enchanted sorting at and I don't usually do interest for my doctor because the idea is you give a bio is to get you into the room and all of you are already here the but is somewhat like hi my name is Caleb as you can see this morning I was at a hundred hour 970 followers and loved it a thousand that means that I need to get 30 people to follow me the and there's at least 30 people in here so I think we can make this happen the itself if you like what you hear with they get fonts and follow me at killed Compton also on the slide we have joined Zhang giving a truism a little bit of information behind the scenes on what it takes to get up on the stage mostly not preparing for your talk right that this talk is
not for people who study computers if you know a big Oh notation is great sit back hopefully the son of a good time but I might not be teaching anything this talk is for
people who call sort and have no idea where demons removing strings around in the array you get back sorted and that's pretty cool you would like to learn a little bit more so would stay understand what Ruby or plus crest deal when you call sort we need to talk about algorithms Annual algorithms are a bit of a scary word but what it comes down to is over them they're just a set of step by step instructions a recipe for chocolate chip cookies is a novel I don't have to understand chemistry a gastronomy when I followed the instructions when I realize that this was just it was a good example I just found a recipe for chocolate chip cookies and made a batch immediately procrastinating on preparing for my talk and
I think the the all of
them of the before
we get too far else wanna talk about big o so this is another scary concept especially when you see it written out next to some over them or something and well you know I usually assume that it's for math people and I make websites placated said were not computer scientists so it's probably not me know it comes down to is the goes not really that's here
it's how we answer the question how fast is novel and how we can take that answer compared to other algorithms it's based on the assumption that the basic operations involved in an algorithm will take the same amount of time between different algorithms to in sense of the so what it does is allow us to compare using the number of operations as a function of the inputs as a instead of actual time taken in in running the of the operations the so the state I a
look at a couple of examples of algorithms for cutting out squares from paper when I previously give this talk the it was pointed out to me that our a little bit smaller heart disease and actually the 1st thing I did was by John pair of scissors and they are all In a giant panda Post-it notes so he could see so hopefully you can see the step butterfly appeared by flying right so each time I end up with another piece of paper that's can 1 operation we it in you know the 1 of the this is due to an end to what it the the we did in all of our the 2nd so you know what the the I had to go these lines because I kept on getting like really weirdly shaped pieces it what we I has had the scissors who came up with this idea uh it it I think so the the I think that the had fun facts this is actually the 1st time I've kept on board the accessible the so the to nodes on we what the it already In the then right so we ended up with 16 squares of paper that makes this algorithm uh an order of N squared times quadratic kind of were entirely linear for them the slide and so as you can see that the growth is linear goes right across the screen if I wanted to cut out 32 squares would take me 31 cuts now that's a different number that's not in so in is the number of squares that I need and so you know it's 15 and not 16 it's 31 and 32 but it doesn't matter because be goes a little bit lossy and the growth is linear and that's what we're really looking at in Figure notation right so they didn't expect this story look at another algorithm cutting up pieces of paper you think of the fact that this was a little bit better in the and if you what the will pay per a you have to really is a the all right and we still have 16 pieces of paper if I wanted 32 pieces of debris would take me only 1 market 5 cats which makes this on a logarithmic time or order of log in our the so much more much more performance than the original despite these kinds this is an example of a lot of different representations the fairly common for bigger down at the bottom that in orange and yellow FIL is actually behind Green the we have of the order of log n and order of n time algorithm so you can see that there's some very big ones here and the the 2 that we shall we we actually looked at the graphs already for her order and an order of organ you can see that the little it's more that's because of it scale down the y axis to tender 1 just to show how big somebody's bigger ones so in squared to the end and ends of In factorial very large if you don imaginary line diagonally through this chart then when you really wanna sheep or is the big notation that are below for a performer now algorithm rather than ones that are above zooming back into 1 1 we can see that there's still a big difference even between order of an order of log it at its eventual that 1st time counts when updating user record on log n it if you've understood everything so far I'm really honored today the had debugger maps we all know this guest start log so what happens when you buy something I promise is the last 1 body so you on this is a dumb question at simple rules at a talk about big omega this is going to be a little bit easier to understand because it's exactly the same as big O except rather than worst-case performance were talking about best-case performance which is why it has the little tails the bottom because it's the lower bound for how fast now written in the tha
all sort is a nice and simple algorithm so a great place to start jumping in explaining sorting nobody is that for each pair of elements compared if they're in the wrong order swap them the new 1 over and the guy keep doing that in the in the hippy in the set and then start over you don't have to look at the last 1 because the last 1 30 bubbled up to be in the correct position so you can go through an entire iteration and no changes are made then your set is sort of can short circuit power so my volunteers volunteered folks please come over here With the papers are what if the your pi the right the the history run volunteered and say the people goal here to the the you have that OK you can go and say the line over there with the late in your eyes the the the half of the correct what and the self and the and cheat sheet we the these are anemic everybody a little text at 5 . 1 is it out yet the high recall 1 4 1 5 9 2 6 5 3 5 the 2 . 1 8 2 8 1 8 2 8 where like etc. 9 doesn't want it over 9 thousand cell 42 the over here the 9 thousand 1 the the 5 . 1 and the so you just shuffle them great according to go through the bubble sort algorithm the we here I would like so the algorithm is we compare each number to the number 2 in class so 42 is less than 9 thousand 1 so it's in the right place no changes that shows 9 thousand 1 is definitely bigger the 5 . 1 bring a swap positions had already moved so we only to move again 9 thousand 1 is bigger than pi herself places you fiery hot 9 thousand 1 greater than ESA result places again that's the 1st iteration easy we know that 9 thousand 1 is in the right place now because it's been bubbled up all the way right that to 42 42 is greater than 5 . 1 so there is some places 42 grade and by some places 42 greater than a place or places right the pretty easy that OK 42 and 9 thousand 1 both in the right place right rails the version we don't have yet to be a pretty big so can be bigger than by assault places and that would be given a soreness or places the 10 all the way to the end again and again we're not needing to go past but we ready bubbled up so is better than bigger than E not better to stick so result places but it also that's the 2nd last iteration now where to go through this entire set the doesn't have anything comparatives we've made no slots and were sort right through a thank you friends may take your seats on the you going and keep going toward
this bubble sort works in in squared times for the purposes of sorting of events In is in this length of the set so since bubble sort operates in quadratic time so that means that it we compare each element every other element In the worst case even though we have some optimation optimization so you're not actually comparing every element every other element like skipping the ones that were even bubbled up 1 receding in algorithms complexity we still say in squared because again that's the grow quadratic growth for bubble sort order in squared is also the average case complexity such as on a randomized direct it has a big omega for lower bound best-case time of in which means that awards best-case bubble sort is sorted and returns a sorted set in linear time the so if we had instead of instead of 42 9 thousand 1 5 . 1 i.e. if we had the pi 5 . 1 142 9 thousand 1 then we would've just had to go through each person wants check that they're in the right order and then we would have been done as we saw before in squared is not that great is this red line here and again that's above the imaginary line that we want to avoid it's bad because it means that the number of operations taken is much higher which generally means more time spent in the other we want to be in 1 of these 4 small islands big o of n log n or big o of n or ideally order of login or order of 1 however 1 would only work in a perfect world where every set is already sorted and so the sorting algorithm is returned the sorted set this it is school civilization of how these algorithms work on different heads and topple has this great sort of visualizations that show bubble sort operating over different types the difference sorted sets this cannot be sort of build an intuition about how bubble sort will work on these different types of the red arrows here indicator subjects black arrows are sorted and Gray arose have yet to be so we have random nearly sorted reversed and unique sets of input data this takes quite a bit of new sort of finished but rather watch the be because it takes over man and I'm on a timer
insertion sort is another simple sorting out it's very efficient at sorting nearly sorted sets and very small sets insertion sort is called the so called because it inserts the sorting the subject element into the set of previously sorted elements in the correct order by comparing it until it's greater than 1 of the position of 1 the previous elements and inserting right after that so the organism
for each element consider all elements to its left continue until you reach 1 that's smaller than the element or you run out of elements check against the if you found anything smaller move the element just after the place and shift everything also let's cyclic the all stop 1st with this 1 and we're gonna compare to everything that's left this is a pretty easy steps there's nothing to its left sort of there were to consider the next element it's the red were comparing 2 is not bigger than the green subject so we're not gonna move anything here is this subset of already sort on to the next green subject will compare each of these and see both smaller the this was so this 1 and this 1 sort move this to the beginning now the 1st 4 elements are in order will repeat this until the whole set of certain what speed through that the
of of how hello with we find any relevant model components can only fit to the data presentations never work that's another insider tips and the the great so now we have a sorted sets insertion source upon 1 because it's 1 of the simplest sorting algorithms to
like bubble sort insertion sort operates in quadratic time and in for the worst case and in quadratic time for the average also like bubble sort and insertion sort has the best case of n squared or in time because the inherent glossiness of big O notation this ignores insertion sort is almost always faster than novels but is simply not a fantastic way to sort a large set it it does work
very well on nearly sorted arrays 30 finished because it is insertion sort is sometimes used as a finishing step for quicksort which will look at next it shares the benefited bubble sort has of returning an already sorted set in linear time you can see that it's working much better on the reverse set and is generally faster despite having the same complexity representations and bubbles or again the stakes allows 1 not what and
quicksort often considered the state of the art in comparison sorting out this is because the average case complexity for the soaring organ is very low compared to others in the same class of Allah it'll only different than insertion a bubble sort rather than taking something and using it as a subject and moving it based on how it compares to other elements we're going to take a pivot which is the same thing as the subject but it's different to defer work for quicksort and remove everything else around it based on whether it's larger or smaller so if it's larger than it'll go to the right if it's model that left if it's equal we want do anything they'll stay in the same or the who have of the so quicksort doesn't specify we should use for the pivot but in general it makes the most sense to take either a random or the middle element rather than the 1st relax elements and we'll get into why that is later but let's take a look at the actual the for a star with 8 of 8 and we're gonna compare to everything on its left and right and then we're gonna move cards around so they're in the right or so 8 is greater than 2 so that's the right or is is greater than Jack so Jack needs to move over beyond where it was but with this shift everything down but and go ahead and flip the jack over and the 2 over because we've already looked at bands we'd only be looking for so now I need to compare it to the joker but don't know a jokers are jokers wild so which we use for job but economic preferably 1 of these numbers the have we know 6 6 at its and if right so 8 is 6 is less than a so the jokers mysterious 6 is also less than 8 the so the sixers guess they were at now it's important the note that because the joker in the 6 started joker here and 6 here they're not gonna change that's because in a quick sort is a stable sorting out the which means that for values that are equal they will stay in the initial ordered state the so we 8 here 5 is less than 8 so it's gonna move over and you look at in King is greater than 8 so it's in the right place bases depending on the game is can be lower which really the but right will place clean greater than it generate place sword and all these sorts of them over to and I but nothing that nothing ever works that it the the it will have at 8 and to set it down the that's funny but it's also because aid is in the right place now it's not gonna move again so when not can move this is going to be out of the way Sonora start with the lowest set things that were lower than a and again were in a repeat this process where is going to pick up pivot that where and pick the midpoint rounded down so since there's 4 elements here we're gonna take the 2nd element which is the joker Joker again is 6 so 2 is less than 6 so it's in the right place 6 is equal the set at 6 and so it's not going to move and 5 is less than 6 so moved before the dog and the joker goes down because the jokers in the right place a lot so again we're going to continue this process there's only 2 all in tears terrific the first one of midpoint render down 5 is greater than 2 so it's in the right place we'd be done with still not look at 5 there's nothing to compare 2 survivors and requests now we go the things that were greater than the Joker which is just the sex 6 in the right place really the right now finally we don't really look at things that were greater than the 8 original student work will last time but let's see how does this the gets so in picked that King making is going to be opposite Joker or Jack is less than going so it's correct these witches is high so it's greater than going it's always greater than everything else and queen is going to be less than the games ordered it over great for the king is done not model look at the Deccan queen queens greater than Jack so it seems readers and Jack is done now we look at the Queen nothing compared to to the right place simply it's nothing compared to so can request so now we have an ordered set using quicksort sort of great and I we also so it took forever to do that demo and so you might not be surprised that big o of of quicksort is also in square In the case of coca Weber is very unlikely would actually hit in squared operations to be an squared you'd have to always select the pivot that was not the smallest or largest element In the entire such that the remaining subsets to be quicksort A of size n minus 1 and say 0 to illustrate that cyclic here so we pick the midpoint as the pivot which is going to be the tallest bar so it moves over we've got a set that's everything except for that it's so in minus 1 and a set of size 0 to quicksort if this happened for every single operation every single time through the other and then it would take in squared uh in squared operations to complete and this is why you don't want to use a the 1st or last element necessarily quicksort because you handed a sorted set and it takes the 1st a last element it would always end up quick sorting In this case we've got a set of size 0 and set of size n minus 1 the magic quicksort those that the average case complexity is linearithmic which is a fancy word for n log n time so when your time times logarithmic time linearity the average case here is not just intuition like we said for bubble sort like it's probably the at the end of the following a taken with this lecture several mathematical proofs that show that quicksort runs in 1 year at a time but they're over my head and out of scope stock linearithmic or in log performance is also the best case for quicksort so while at all is not always the fastest algorithm and can be just as slow as insertion a bubble sort with specific types of input data it's average case is the best case and the best case is faster than just about anything else in a any other comparisons worry however for general purposes meaning integers strings whatever this is the green across the that
said it does have its weaknesses you can see here that it does agree with the reversed set and the nearly sorted set and the random set but it's having trouble with a few unique set the the you can see the same visualizations that we looked at for every each type of other all compared together as a different algorithms work and finish eating get idea that some of them are better suited for specific tasks the random set in the 1st column the does give a fair approximation of the average case and you can see the quicksort works very quickly that it also makes short work of the reversed said and which principle of soaring our insertion sort which very quickly on the nearly sorted set and bubble sort surrogate anything of Digital's right use the on the other hand is very difficult to beat the average case performance for quicksort which is why I that's what Ruby users in it sort implementation of the like to
think my employer broken for supporting incoming real stuff this year you may have heard about the new automated certificate management offering which let news you free let's encryptor certificates for repay dinos at any tier this video shows how easy it is let's say the
order of 1 complex the you should check it
out if you haven't yet
and if you he sees speak now
but if you're interested in hearing from other OK and you're welcome to check out the speaker schedule we included in this slide which has the listing apart from John and his next Richard need in me and Stella you give me questions about sorting
ACM or really anything you open it and the office hours at the OK with in the exposition all on Wednesday and Thursday were older speakers will be hanging out for a bit usually right after the talks but the Excel explore all an open today so John and I will be later so and you can also find me in the whole or ask questions on Twitter is uniformly remember the thank
you but the there
so that he reviews of reward
Demoszene <Programmierung>
Rechenschieber
Hypermedia
Mailing-Liste
Bit
Rechter Winkel
Information
Computeranimation
Bit
Zahlensystem
Algorithmus
Menge
Cookie <Internet>
Wort <Informatik>
Computerunterstütztes Verfahren
Dämon <Informatik>
Stapelverarbeitung
Quick-Sort
Computeranimation
Web Site
Mathematisierung
Vorlesung/Konferenz
Informatik
Subtraktion
Bit
Selbst organisierendes System
Quadratische Gleichung
Selbstrepräsentation
Zahlenbereich
Ungerichteter Graph
Login
Whiteboard
Eins
Datensatz
Zahlensystem
Knotenmenge
Logarithmus
Algorithmus
Minimum
Zeitkomplexität
Figurierte Zahl
Schnitt <Graphentheorie>
Gerade
Touchscreen
Lineares Funktional
Nichtlinearer Operator
Green-Funktion
Schlussregel
Ein-Ausgabe
Mapping <Computergraphik>
Rechenschieber
Quadratzahl
Debugging
Computerunterstützte Übersetzung
Ordnung <Mathematik>
Steuerwerk
Aggregatzustand
Resultante
Bit
Subtraktion
Ortsoperator
Quadratische Gleichung
Minimierung
Mathematisierung
Klasse <Mathematik>
Versionsverwaltung
Zahlenbereich
Iteration
Zellularer Automat
Baumechanik
Element <Mathematik>
Login
Komplex <Algebra>
Eins
Komplexitätstheorie
Zufallszahlen
Algorithmus
Datentyp
Visualisierung
Zeitrichtung
Zeitkomplexität
Indexberechnung
Quick-Sort
Gerade
Metropolitan area network
Leistung <Physik>
Nichtlinearer Operator
Dicke
Eindeutigkeit
Paarvergleich
Ein-Ausgabe
Ereignishorizont
Quick-Sort
Linearisierung
Menge
Rechter Winkel
Digitaltechnik
Ordnung <Mathematik>
Teilmenge
Einfügungsdämpfung
Ortsoperator
Menge
Selbst organisierendes System
Element <Mathematik>
Quick-Sort
Ordnung <Mathematik>
Einfügungsdämpfung
Quick-Sort
Verschiebungsoperator
Zahlensystem
Informationsmodellierung
Einfügungsdämpfung
Algorithmus
Menge
Mittelwert
Quadratische Gleichung
Zusammenhängender Graph
Quellcode
Kombinatorische Gruppentheorie
Quick-Sort
Sichtbarkeitsverfahren
Einfügungsdämpfung
Demo <Programm>
Prozess <Physik>
Selbst organisierendes System
Mathematisierung
Klasse <Mathematik>
Selbstrepräsentation
t-Test
Zahlenbereich
Element <Mathematik>
Komplex <Algebra>
Informationsmodellierung
Zufallszahlen
Logarithmus
Algorithmus
Reverse Engineering
Spieltheorie
Gruppe <Mathematik>
Datentyp
Volumenvisualisierung
Stützpunkt <Mathematik>
Zeitkomplexität
Quick-Sort
Verschiebungsoperator
Schreib-Lese-Kopf
Array <Informatik>
Umwandlungsenthalpie
Nichtlinearer Operator
Mathematik
Pivot-Operation
Ausnahmebehandlung
Paarvergleich
Ein-Ausgabe
Quick-Sort
Chipkarte
Linearisierung
Teilmenge
Generator <Informatik>
Menge
Ganze Zahl
Rechter Winkel
Beweistheorie
Ablöseblase
Wort <Informatik>
Aggregatzustand
Zeichenkette
Einfügungsdämpfung
Digitales Zertifikat
Approximation
Freeware
Implementierung
Quick-Sort
Computeranimation
Videokonferenz
Task
Zufallszahlen
Datenmanagement
Algorithmus
Menge
Rechter Winkel
Softwareschwachstelle
Randomisierung
Visualisierung
Zeitkomplexität
Eindeutigkeit
Einfügungsdämpfung
Rechenschieber
Scheduling
Mailing-Liste
Ordnung <Mathematik>
Computeranimation
Quantisierung <Physik>
Gammafunktion
Spezialrechner
Algorithmus
Hypermedia
Software
Bit
Twitter <Softwareplattform>
Visualisierung
Schlussregel
Office-Paket
COM

Metadaten

Formale Metadaten

Titel Sorting Rubyists
Serientitel RailsConf 2017
Teil 53
Anzahl der Teile 86
Autor Thompson, Caleb
Lizenz CC-Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Unported:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/31284
Herausgeber Confreaks, LLC
Erscheinungsjahr 2017
Sprache Englisch

Inhaltliche Metadaten

Fachgebiet Informatik
Abstract Let's take a peek under the hood of the magical "sort" method, learning algorithms... by sorting audience members wearing numbers! Intimidated by the word "algorithm? Not sure what performance means? Confused by "Big O Notation"? Haven't even heard of best-, worst-, and average-case time complexities? No problem: we'll learn together! You can expect to come out knowing new things and with Benny Hill stuck in your head.

Ähnliche Filme

Loading...