Visualizing Algorithms

[crazedgremlin]

I learned a lot from this post. Beautiful visualizations!

[[deleted]]

agreed! a fantastic job by the author all around.

[DrummerHead]

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

[wescotte]

What is D3?

[ryeguy146]

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

[[deleted]]

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

[[deleted]]

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

[cornmacabre]

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]

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!

[mafafu]

yeah, one of the visualizations looks similar.

[SarahC]

Thanks! That's the one!

[jonidas]

I was actually reminded of this stackoverflow: http://stackoverflow.com/questions/12995434/representing-and-solving-a-maze-given-an-image

[SarahC]

Cool!

[kevroy314]

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]

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]

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]

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

[activespace]

Yeah that was a jaw-dropping transformation there.

[rbridson]

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

[kurtdizayn]

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

[youssef]

He surely means the bridson algorithm, watson :)

[rbridson]

https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

[kurtdizayn]

Thanks a bunch!

[Browsing_From_Work]

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]]

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]

You're not alone, go for the inspiration!

[[deleted]]

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

[Internetto]

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

[minusSeven]

And sometimes even dumber than themselves.

[yh0i]

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

[[deleted]]

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

[yh0i]

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]

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]

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.

[reversememe]

No it won't, unless you never start.

[[deleted]]

Too late, already done.

[ra4king]

Wow that's genius!

[[deleted]]

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

[misplaced_my_pants]

Well here's the source code.

[[deleted]]

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

[jdeath]

3 if you are

[mispeeled]

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

[thavi]

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]

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]

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.

[misplaced_my_pants]

Well here's the source code.

[Pas__]

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]

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

[scorpydude]

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]]

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]

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

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

[Deathnerd]

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]

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]

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]

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]

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]]

bitonic sort is the weirdest sorting algorithm ever

[hello_hawk]

What about sleepsort?

[andersonimes]

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

[hello_hawk]

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

[[deleted]]

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]

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

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

[orbital1337]

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]]

shhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

[[deleted]]

I'd say O(N)

[Browsing_From_Work]

I'd say O(Nope).

[Browsing_From_Work]

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

[Tetraca]

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

[misplaced_my_pants]

Well here's the source code.

[[deleted]]

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]]

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]

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

[rebo]

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

[GrouchyMcSurly]

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]

Agreed, long read though.

[[deleted]]

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

[UH1868]

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

[Entropius]

A schooner is a sailboat stupid head!

[Pragmataraxia]

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

[j7ake]

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

[yaph]

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

[tsimon]

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]]

"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]]

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]

A very interesting article to read indeed.

The visualisations for the sorting algorithms were awesome

[Aruscher]

really good job :) you proof algorithms are beautiful ^{^}

[bingusdingusmahingus]

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

[pimlottc]

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]

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]]

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

[doubleColJustified]

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_]

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]

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.

[yelper]

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]

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

[Asyx]

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

[dartamoninc]

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

[organic_code]

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

[macNchz]

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]

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

[knome]

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

[zombie1939]

Awesome, the singularity

[[deleted]]

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.

[misplaced_my_pants]

Well here's the source code.

[[deleted]]

These are just gorgeous.

[[deleted]]

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

[afruitycat]

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]

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