Big-O is important

Except for when it's not.

I've seen a lot of people - not just developers but actual, real-life people, waste so much effort on micro optimizations at the expense of macro disadvantages.

That's not to say that you shouldn't have the good common sense to avoid O(n^2) when your real problem is more along the lines of O(2n), but there's no sense in going back to fix an O(n^2) in a list of root level navigation tabs on a website.

(Conversely I often have wondered why the gmail app takes whole seconds to search through a list of just a few thousand contacts on my phone - and Firefox OS has the same problem)

So how terrible is bogosort?

For the sake of argument / curiosity / fun (take your pick): At what number of elements does bogosort become "too slow"?

Let's define "slow" as "I could blink and not miss it" - roughly 300ms - and "too slow" as "I started thinking about / doing something else" - roughly 650ms.

Note: For those of you not in the know, bogosort is an "algorithm" for sorting lists - like putting numbers in order. The way the algorithm works is that it shuffles all of the items randomly and then checks to see if they're in the right order or not - meaning it would fail and try again if any preceding number is greater than its successor.

So here's our bogosort test:

After running it a few times, here's some of the result sets I get:

Number of itemsTime (ms)
10
20
30
40
51
61
769
839
9410
1030547
Number of itemsTime (ms)
10
20
30
40
50
61
710
8361
91725

Update

For comparison I used a better randomize algorithm (fisher-yates/knuth shuffle) and I was not surprised to see that it was an order of magnitude faster on average - even though and I'm fairly sure it's more computationally intensive.

Check out the optimized bogosort.

Here are some samples:

List SizeMilliseconds
10
20
30
40
51
61
70
87
9149
10754
List SizeMilliseconds
10
20
30
40
51
60
75
85
9180
10383
1017796

Using process.hrtime()

List SizeSeconds
10.000178629
20.000037074
30.000005097
40.000009899
50.000445547
60.000263364
70.004096409
80.004580194
90.150200741
100.793862271
1118.020675493

And, of course, with v8's jit optimizer kicking in after a few thousand loops, it starts to get a little faster before it gets much much slower. :D

Conclusions

Use fisher-yates/knuth shuffle, (see visual explanation) because if you use Math.random(), you'll get sued a la Microsoft MSIE ballot

If you had a personal blog and wanted to use it to sort your top-level navigation bar, it would probably do just fine.

If however, you wanted to sort your blog posts by date (or whatever), I'd have to recommend a different algorithm.

note: it would be interesting to see the number in terms of clock cycles or nano seconds or something where the scale is more apparent. I wouldn't be surprised if the reality of the jump is that by the time we get to 13 it takes hours. done!

rainy day todo: run the test 100 times and report the averages

Conclusion-ception: Writing this article, and especially coming back to update it with an optimized bogosort, is a perfect example of micro advantages as the expense of macro disadvantages.


By AJ ONeal

If you loved this and want more like it, sign up!


Did I make your day?
Buy me a coffeeBuy me a coffee  

(you can learn about the bigger picture I'm working towards on my patreon page )



Published

2015-1-17



Buy me a coffeeBuy me a coffee


  73% of Goal Reached


Want more like this?