Twitter Sort • Hacker News Board

Re: Twitter Sort

#11

Post by btilly » Wed, Jan 14, 2015, 1:53 AM UTC

[deleted] wrote: post #6

Mahn wrote: post #5

I wonder what's the efficiency of this algorithm in O notation on average.

[deleted]

Big-O notation refers to the worst case runtime of an algorithm.

I have no idea where this misconception comes from.

Big-O notation is a type of bound on a function's growth rate. That function can represent anything. Best case performance, worst case performance, average case performance, memory usage, how many times you are likely to phone someone while you wait, etc.

The standard example showing this is that hash lookups are O(1) or O(n) depending on whether you are asking about the average case or the worst case.

Re: Twitter Sort

#12

Post by stevewilhelm » Wed, Jan 14, 2015, 1:58 AM UTC

You might want to add an optional parameter "number of matching results" that would be used before sending the sorted results.

Re: Twitter Sort

#13

Post by moe » Wed, Jan 14, 2015, 2:01 AM UTC

Mahn wrote: post #5

I wonder what's the efficiency of this algorithm in O notation on average.

The probability of the original input list being in the exact order it's in is 1/(n!). If that's the order you wanted then the algorithm might very well approach O(0).

Re: Twitter Sort

#14

Post by mdoar » Wed, Jan 14, 2015, 2:08 AM UTC

What about the locale of the user producing a different sort order?

Re: Twitter Sort

#15

Post by archagon » Wed, Jan 14, 2015, 2:10 AM UTC

Mahn wrote: post #5

I wonder what's the efficiency of this algorithm in O notation on average.

It's O(whatever algorithm the responder uses), plus a HUUUGE constant for latency and wrong answers.

Re: Twitter Sort

#16

Post by Dobbs » Wed, Jan 14, 2015, 2:27 AM UTC

I thought this was going to return them sorted in random order, making a joke about how unreadable the way Twitter sorts conversations is.

Re: Twitter Sort

#17

Post by flavor8 » Wed, Jan 14, 2015, 2:27 AM UTC

Hardcoding the validation of the reply is an unfortunate obstacle to scaling this - the server would very quickly become CPU bound. They should really have made a TwitterSortValidationService which sends the answer out to the Twitter API, and then listens for a response confirming whether or not the original sort was correct.

Re: Twitter Sort

#18

Post by abalone » Wed, Jan 14, 2015, 2:32 AM UTC

The trick is the algorithm makes extensive use of lazy evaluation.

Re: Twitter Sort

#19

Post by cldellow » Wed, Jan 14, 2015, 2:35 AM UTC

mdoar wrote: post #14

What about the locale of the user producing a different sort order?

They do specify that it's for sorting numbers, as opposed to say, text. Do some locales sort numbers differently?

Re: Twitter Sort

#20

Post by JetSpiegel » Wed, Jan 14, 2015, 2:43 AM UTC

https://duckduckgo.com/?q=!twitter+Those+numbers+aren%27t+so...

Still no uses of this in the wild.