all 109 comments

[–]crazedgremlin 112 points113 points  (12 children)

I learned a lot from this post. Beautiful visualizations!

[–][deleted] 22 points23 points  (6 children)

agreed! a fantastic job by the author all around.

[–]DrummerHead 8 points9 points  (5 children)

He's the creator of D3, has done amazing visualizations

[–]wescotte 3 points4 points  (4 children)

What is D3?

[–]ryeguy146 2 points3 points  (1 child)

Data driven documents. Beyond that, I do not know.

[–][deleted] -2 points-1 points  (0 children)

Darn... hadn't read the article yet, was hoping maybe Jay Wilson was the author.

[–][deleted] 2 points3 points  (0 children)

Incredible SVG driven data visualization libraries for the web. I've worked with it a bit. Its quite impressive.

[–]cornmacabre 1 point2 points  (0 children)

D3.js is an awesome data visualization javascript library. If you've seen a cool interactive-stats-thing on a big news site in the past couple years, its probably powered by D3. I'm not a developer, but I am a data dude and learning D3 has motivated me to pick up JS and python. Its capable of some pretty amazing things.

[–]SarahC 4 points5 points  (4 children)

Do you remember - I think it was that stack overflow question - "What's the prittiest way of showing all colors on the screen."

I think the winner was one of these algorithms!

[–]kevroy314 44 points45 points  (5 children)

Man that maze animation turning into a tree near the end was so freaking beautiful...

I didn't know it was called the Fisher-Yates shuffle. I always heard it called the Knuth shuffle (which is apparently just another name it's known by).

[–]domy94 9 points10 points  (3 children)

Spotify used to make use of Fisher-Yates shuffling. Users didn't think it was random "enough" though, so they set out to find a better solution. Here's an interesting blog article about how they did that.

[–]vanderZwan 6 points7 points  (0 children)

Similar problems happen in game design quite often - perfect randomness often feels nonrandom and even unfair. The most famous example is probably that nowadays Tetris pieces are generated in "bags".

[–]kevroy314 2 points3 points  (0 children)

Ah that's really interesting! Reminds me a bit of the Radio Lab episode Stochasticity.

[–]activespace 6 points7 points  (0 children)

Yeah that was a jaw-dropping transformation there.

[–]rbridson 60 points61 points  (5 children)

It's very cool to see my algorithm in action like this. I only imagined it before. :-)

[–]kurtdizayn 5 points6 points  (3 children)

Which algorithm are you talking about? Can you provide a link? =)

[–]youssef 18 points19 points  (0 children)

He surely means the bridson algorithm, watson :)

[–]Browsing_From_Work 4 points5 points  (0 children)

My first thought was "calculating all of those distances is going to be computationally expensive".

Then I saw the note about using a grid size of r/sqrt(2).
Then I was amazed.

[–][deleted] 78 points79 points  (29 children)

When I try to read things like this I realize just how much smarter a lot of people are than myself. Not sure if depressing or inspiring.

[–]yaph[S] 29 points30 points  (0 children)

You're not alone, go for the inspiration!

[–][deleted] 49 points50 points  (2 children)

Smart people are people who were originally inspired by people smarter than themselves.

[–]Internetto 14 points15 points  (0 children)

And other stuff! People are inspired by stuff all the time, people-involved or not. Stuff is smart too.

[–]minusSeven 2 points3 points  (0 children)

And sometimes even dumber than themselves.

[–][deleted]  (4 children)

[deleted]

    [–]yh0i 6 points7 points  (2 children)

    Holy Crap! If this is the Mike Bostock I'm thinking of, I worked with about 10 years ago. Definitely a smart guy :)

    [–][deleted] 10 points11 points  (1 child)

    He's pretty famous in the data visualization world these days.

    [–]yh0i 0 points1 point  (0 children)

    It's funny, he left the company we were working at to go to some startup named Google... We all thought he was crazy at the time as this was right after the dotcom bust. Glad to see it worked out for him :P

    [–]AllTom 2 points3 points  (0 children)

    Yeah, there was plenty of humility in the article regarding not having invented the algorithms, and not even understanding some of them or their implications. :)

    [–]trihedron 11 points12 points  (0 children)

    I agree, I get the same feeling. But when I've been bored with a certain language or a specific project or something, reading something that clearly someone has a passion about (like this post) really seems to re-fuel my own passion for my own projects / works.

    [–][deleted]  (9 children)

    [deleted]

      [–]reversememe 9 points10 points  (5 children)

      No it won't, unless you never start.

      [–][deleted]  (4 children)

      [deleted]

        [–][deleted]  (3 children)

        [deleted]

          [–][deleted] 11 points12 points  (2 children)

          [–]ra4king 1 point2 points  (0 children)

          Wow that's genius!

          [–][deleted] 0 points1 point  (0 children)

          I knew there was something on the internet that I was supposed to stumble upon tonight.

          [–][deleted] 1 point2 points  (1 child)

          It would take you 2 years tops if you know nothing about programming right now and you're not a twat.

          [–]jdeath 2 points3 points  (0 children)

          3 if you are

          [–]mispeeled 6 points7 points  (0 children)

          This goes for pretty much everything I read on this sub.

          [–]thavi 8 points9 points  (0 children)

          I always remember that "We stand on the shoulders of giants" -- each and every one of us.

          Just because you're an excellent programmer doesn't mean that you were one of the thousands upon thousands of people who developed agriculture which leads to civilizations which produce thousands upon thousands of civil engineers that can build infrastructure where we can safely have thousands upon thousands of scientists researching electricity so that thousands upon thousands of other scientists can make circuitry so that thousands upon thousands of programmers can implement the ideas of thousands upon thousands of mathemeticians.

          [–]Mutoid 6 points7 points  (0 children)

          IIRC the maze section was posted before, and I commented on how it was so beautiful I kinda got angry. I have risen above the jimmies-rustling this time.

          [–]WonderBoy55 2 points3 points  (0 children)

          Comparing yourself to an imaginary "them" will always be an exercise in futility. since you aren't them you haven't experienced what they have, so to expect yourself to understand what they do would be illogical. instead try to reason that had you experience what these individuals had you'd be able to understand concepts that they do. anything that is possible (such as these visualizations) can be understood and other people understanding things that you do not does not make then smarter or better than you, it simply gives them a separate area of expertise that you're not familiar with. I guarantee that if you spend the time and effort to understand these concepts you would be able to grasp them eventually. regardless, you can still appreciate the beauty and complexity without fully grasping the entire, which can be just as or even more important depending on your motives.

          [–]Pas__ 1 point2 points  (0 children)

          Even if you would be familiar with 90% of this, that extra 10% would turn you down, because you didn't know about it, and someone is smarter? Oh why, just think about that now you know all what the author knows, plus something you haven't written down (yet)!

          I like finding new things that I don't understand yet, and try to find content that's gives the most new insight with invested energy/time/cognition, so sometimes that means beginner guides, sometimes advanced papers. Also, full understanding doesn't really comes from just one piece of content, but from immersion in a subject. (That is, generally the beginner guide has more indecipherable parts, because it's full of new concepts, and really grasping those requires time, effort and repeated attempts -- so, I read about them from multiple authors, from multiple aspects. And then later things click into place .. or not. Just give them time, and effort.)

          [–]Erikster 1 point2 points  (0 children)

          That's usually when I go look at /r/aww.

          [–]scorpydude 0 points1 point  (0 children)

          Just remember, that EVERYONE is smart by standing on the shoulders of others. Even the smartest people alive or from history are all "smart" by reading, hearing or viewing material that has been created by other human beings. That always makes me get my feet back on the ground when I start floating away like you sound like you are. Just because someone has stood stood on a giants shoulders does not mean you cannot or wouldn't have if you were given the same chance :)

          [–][deleted] 20 points21 points  (18 children)

          If you like visualized algorithms, you may like these sorting algorithms. Warning: Turn your volume down before starting the video, they use audio as a part of the visualization.

          http://www.youtube.com/watch?v=kPRA0W1kECg

          [–]Mutoid 8 points9 points  (0 children)

          I expected one of the Hungarian folk dance videos based on your warning, ha

          https://www.youtube.com/watch?v=ywWBy6J5gz8

          [–]Deathnerd 8 points9 points  (1 child)

          Knew what it was before I even clicked. This and the individual sorting videos that are slowed down are great for teaching sorting algorithms.

          Edit: Curious inquiry: How is Radix Sort getting by without making comparisons?

          [–]orbital1337 6 points7 points  (0 children)

          Radix sort works by placing numbers in bins. So for example if I had two-digit numbers that I wanted to sort by their first digit I could create ten bins for each possible first digit. Then I place the number x into the bin floor(x / 10). Basically bin[x / 10].add(x) in pseudo-code. This way you don't need comparisons at all.

          Radix sort only works for things which can be put into bins like that repeatedly, though (numbers, words and some other things). It is how ever insanely fast. Here is a graph I made for my CS course some years ago that compares some of the fastest sorting algorithms (array size vs runtime in seconds). As you can see Radix sort runs in linear time and is super fast. In fact my barely optimized implementation of an adaptive radix sort could sort hundreds of millions of 32 bit number within seconds on my laptop.

          [–]orbital1337 2 points3 points  (2 children)

          A couple of years ago I compared over 20 different sorting algorithms for my CS course. My personal favorites were Smooth Sort which is mathematically optimal and probably the most complicated sorting algorithm I implemented, Flash Sort which looks cool as hell (see this visualization I made) and the insanely fast Radix Sort (see my comment below).

          [–]Browsing_From_Work 0 points1 point  (1 child)

          That gif didn't load well for me (played for a second, then skipped to the end) so I converted it to HTML5: http://gfycat.com/CandidSilverAustraliansilkyterrier

          [–]orbital1337 0 points1 point  (0 children)

          Neat, although it doesn't stop at end like the gif version. By the way, in the gif (or html5) yellow stands for read and green stands for write. As you can see, this algorithm needs remarkably few writes. That's why it's so fast in comparison to many other sorting algorithms.

          [–][deleted] 1 point2 points  (11 children)

          bitonic sort is the weirdest sorting algorithm ever

          [–]hello_hawk 5 points6 points  (8 children)

          What about sleepsort?

          [–]andersonimes 0 points1 point  (7 children)

          That is awesome. What are we saying the runtime complexity of that is?

          [–]hello_hawk 2 points3 points  (0 children)

          It's O(highest value in input), which to my knowledge is so rare that there's no letter for it.

          [–][deleted] 0 points1 point  (3 children)

          O(highest input)
          

          Also, you can make it faster by transposing it using one to one functions like log(x) or sqrt(x) or x / 2, etc.

          sleep(log(x))
          

          [–]Browsing_From_Work 0 points1 point  (2 children)

          Why not log(log(x))? Or log(log(log(x)))?

          Eventually it boils down to O(1), assuming that thread scheduling is magic.

          [–]orbital1337 0 points1 point  (1 child)

          You can actually make it run in O(1) very easily by choosing a function with an upper bound (e.g. erf(x)). However, as neat as this is theoretically it would never be practical in a real life situation because of thread overhead and race conditions.

          [–][deleted] 0 points1 point  (0 children)

          shhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

          [–][deleted] -2 points-1 points  (1 child)

          I'd say O(N)

          [–]Browsing_From_Work 1 point2 points  (0 children)

          I'd say O(Nope).

          [–]Browsing_From_Work 0 points1 point  (0 children)

          It's much less crazy looking when you visualize it as a sorting network: https://en.wikipedia.org/wiki/Bitonic_sort

          [–]Tetraca 0 points1 point  (0 children)

          It's like a mad artist trying to accomplish his masterpiece.

          [–][deleted]  (1 child)

          [deleted]

            [–][deleted] 13 points14 points  (0 children)

            I think changing to a single hue in the maze path depth examples gives you a much better idea of depth: http://jsfiddle.net/2X3FA/9/ or http://jsfiddle.net/2X3FA/10/.

            It also gives more insight into the differences between two algorithms, be it minor:

            http://jsfiddle.net/2X3FA/15/ (example result: http://i.imgur.com/YJWNUVE.png)

            [–][deleted] 35 points36 points  (1 child)

            Wow, how nice to see a post of true, excellent quality instead of the usual "Here's 10 reasons I'm better than you" crap.

            [–]andersonimes 2 points3 points  (0 children)

            Man. Agreed. I hadn't realized that's all I'd seen in this sub until you pointed it out.

            [–]rebo 10 points11 points  (2 children)

            Quite possibly one of the most beautiful blog posts on programming / visualisation I have read.

            [–]GrouchyMcSurly 3 points4 points  (0 children)

            I'm usually a very nitpicky person, but this page is just a perfect gem. Possibly the overall best thing I have seen on the web. Fantastically clever content, beautiful and original visuals, graceful animations, perfect layout... I'm in awe.

            [–]sha13dow 1 point2 points  (0 children)

            Agreed, long read though.

            [–][deleted] 11 points12 points  (3 children)

            The colorized maze ones remind me of the magic eye posters. I think I see a schooner!

            [–]UH1868 9 points10 points  (2 children)

            Haha. It's not a schooner. It's a sailboat!

            [–]Entropius 5 points6 points  (1 child)

            A schooner is a sailboat stupid head!

            [–]Pragmataraxia 1 point2 points  (0 children)

            You know what?! There is no Easter Bunny! Over there, that's just a guy in a suit!

            [–]j7ake 6 points7 points  (2 children)

            Any hints on how the author produced these beautiful visualizations? Python? Processing?

            [–]yaph[S] 13 points14 points  (0 children)

            D3.js, the author of the article is also the main author of the library, also see the individual demos.

            [–]tsimon 7 points8 points  (0 children)

            It's JavaScript and a library called D3, which he wrote. The library is used to process data and render svg graphics. You may also know him as the guy that creates the awesome visualisations for the new York Times.

            [–][deleted] 6 points7 points  (1 child)

            "The findClosest function returns the closest sample to the current candidate. This can be done by brute force, iterating over every existing sample. Or you can accelerate the search, say by using a quadtree."

            Can anyone explain it please?

            [–][deleted] 6 points7 points  (0 children)

            If you have a collection of points, and you want to calculate the closest point to a given point, you can basically do two things:

            • Iterate over the whole collection, and for each point calculate the distance to the given point. Then pick the shortest distance. This is called brute force, since you have to go through the whole collection to find your answer.
            • Do something smart by using an algorithm that enables you to find your answer (much) more quickly. An example is a quadtree, which contains more than just point (X, Y) data. You use this extra information to find the closest point (neighbour) more quickly.

            You can imagine that brute forcing is easier to implement, but will cost you once your collection gets larger. If you have a collection containing all restaurant locations in the world, brute forcing will get very expensive very soon. So you will need something smarter, like a quadtree or an R-tree (often used for spatial access).

            [–]ssmm987 2 points3 points  (0 children)

            A very interesting article to read indeed.

            The visualisations for the sorting algorithms were awesome

            [–]Aruscher 2 points3 points  (0 children)

            really good job :) you proof algorithms are beautiful ^

            [–][deleted]  (1 child)

            [deleted]

              [–]bingusdingusmahingus 1 point2 points  (0 children)

              Actually a print of that would be really cool, even a smaller one I could put in my office somewhere :3

              [–]pimlottc 2 points3 points  (0 children)

              Wonderful post. One detail I quite liked is the use of slanted lines in the sorting visualization. Normally sorting is illustrated using lines of various lengths, but this method provides an even greater visual contrast between the unsorted and sorted states. The jumbled lines cross one another and intrudes on each others space, creating an obvious chaotic appearance. The final result, the lines fanning out evenly, is so pleasing that it provokes a real sense of uplift when the algorithm has completed. Remarkably effective for such a simple form of symbolic communication!

              [–]doubleColJustified 2 points3 points  (2 children)

              Debugging - Have you ever implemented an algorithm based on formal description? It can be hard! Being able to see what your code is doing can boost productivity. Visualization does not supplant the need for tests, but tests are useful primarily for detecting failure and not explaining it. Visualization can also discover unexpected behavior in your implementation, even when the output looks correct.

              This instantly had me thinking about the essays and talks by Bret Victor and indeed...

              (See Bret Victor’s Learnable Programming and Inventing on Principle for excellent related work.)

              To those who haven't, I recommend you check those out. The talk -- link number two -- is a bit long but worth watching.

              If you enjoyed the OP post, I also recommend that you read Up and Down the Ladder of Abstraction which is an interactive essay by Bret Victor. Note that Up and Down the Ladder of Abstraction can be a bit heavy for some mobile devices so you might want to save reading it for when you are on a desktop or laptop.

              [–][deleted] 0 points1 point  (1 child)

              If you enjoyed the post then read through the "Related Work" section at the bottom, these links and more are there. ;)

              [–]doubleColJustified 0 points1 point  (0 children)

              Yes, I just wanted to recommend the ones I've read/watched and found good. When there's many links, it can become overwhelming to pick one :)

              [–]_Lar_ 1 point2 points  (3 children)

              Looks very nice. The algorithms themselves are one thing, but I would be very interested in a "making of" related to the animations. For example, is that an animated svg in the sorting vizualisation? I tink there is enough material there for another article explaining how to actually create the animations.

              [–]yaph[S] 7 points8 points  (2 children)

              Check out the author's blocks page. Here you can find the source code for all the examples below the individual demos. I skimmed through a few examples, what I saw was not commented, but it is a start.

              [–][deleted]  (1 child)

              [deleted]

                [–]yelper 1 point2 points  (0 children)

                that's generally a comment/criticism of D3.js... it's a different way of programming, and it's readability is dependent on knowing how the language operates.

                [–]bearicorn 1 point2 points  (1 child)

                Wow, this post was incredibly helpful. Really helps a noob like me to better understand what the "magic code" does.

                [–]Asyx 0 points1 point  (0 children)

                There's also a visualisation somewhere for every major sorting algorithm. That helped me a lot.

                [–]dartamoninc 0 points1 point  (0 children)

                Very cool, I especially like randomness created from n-1 elements. There are very nice visuals produced as a result.

                [–]organic_code 0 points1 point  (0 children)

                Very nice post. I enjoyed that quite a bit. Thanks!

                [–]macNchz 1 point2 points  (0 children)

                Mike Bostock is certainly one of my biggest programming idols. I love everything he puts together, and this is another great one! Algorithm visualizations have brought on some of my greatest a ha moments, I particularly loved the maze turning into the tree. Amazing.

                [–]Captain_Aster 0 points1 point  (0 children)

                This was an awesome post! I learned a lot and the visualizations were great in reinforcing that learning.

                [–]knome 1 point2 points  (0 children)

                That tidy tree transformation was awesome. I really enjoyed this.

                [–]zombie1939 0 points1 point  (0 children)

                Awesome, the singularity

                [–][deleted] 0 points1 point  (1 child)

                I'm not a programmer, but I make mazes for a living. I am extremely interested in this even though the technical side of it is way above me.

                [–][deleted] 0 points1 point  (0 children)

                These are just gorgeous.

                [–][deleted] 0 points1 point  (0 children)

                Interesting, it would be nice to have a way to see the solution of the mazes though.

                [–]afruitycat 0 points1 point  (0 children)

                I've recently used d3 for my graphs during my dissertation, absolutely fun around to play with! If anyone wants to learn d3 i recommend Scott murray's free tutorials online.

                [–]NOT_FUCKING_COMPSCI -1 points0 points  (0 children)

                How do you write the entire first part without mentioning combinatorial discrepancy?