News for hackers. Stuff that matters.
Re:Twitter Sort by TrainedMonkey on Tuesday January 13, 2015 @08:17PM (#8883689)
While potentially more efficient than bogosort for larger input size, this sorting algorithm has a serious limitation. I am of course talking about being limited to 140 characters per tweet. This seriously restricts maximum input size you can sort, which in turn severely cuts down on potential applications of this technology. Moreover, without deployed SAAS (sorting as a service) bot, algorithm is not deterministic which will complicate handling logic as you need to account for being forever alone without anyone to sort your numbers.

In short, I would advise against deploying this on production until technology is more mature.

Re:Twitter Sort by Mahn on Tuesday January 13, 2015 @08:30PM (#8883726)
Regarding maximum input size, I'm sure it can be forked to implement a tweet-sharding approach.
Re:Twitter Sort by wging on Wednesday January 14, 2015 @06:54AM (#8885666)
Merging of tweet shards is also possible via the same mechanism. Just tweeterate through the retrieved shards and merge them one by one. To merge two lists, compare elements pairwise. To compare elements pairwise, construct a two element list and sort this list via the short-form tweetsort api.
Re:Twitter Sort by emmanueloga_ on Wednesday January 14, 2015 @10:33PM (#8890754)
For sorting big lists of numbers mergesort could be used, only resorting to twittersort when the list of numbers is small enough [1]. In fact, that's the way mergesort is generally implemented (except the "cutoff" algorithm is usually insertionsort, not tweetsort :p).

1: http://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sor...

Re:Twitter Sort by jayp on Tuesday January 13, 2015 @08:45PM (#8883784)
Sharding via a Tweet Storm(TM).
Re:Twitter Sort by guelo on Wednesday January 14, 2015 @03:24AM (#8884970)
In the sorting world it's called a bucket, not a shard.
Re:Twitter Sort by afandian on Wednesday January 14, 2015 @04:54AM (#8885285)
Where's your imagination? Three immediate solutions:

1 - gzip content to store in a tweet. You could squeeze more out.

2 - store the content in an image and standardize on an OCR library

3 - use twitlonger.com for larger messages

EDIT: Anyway I thought app.net was meant to solve all this?

Re:Twitter Sort by lloeki on Wednesday January 14, 2015 @11:50AM (#8887380)
OCR? dump the raw sequence as bytes and encode it into a valid PNG.
Re:Twitter Sort by afandian on Wednesday January 14, 2015 @12:44PM (#8887767)
The trouble is that some mobile ISPs compress images (as I found to my surprise). I know it should be sacrosanct, but you can't rely on the same bytes coming out the other end. I think OCR would be more robust.

Otherwise you're potentially ruling out mobile users.

Re:Twitter Sort by anon4 on Wednesday January 14, 2015 @08:51AM (#8886177)
Put your numbers in a pastebin, then post a link to the pastebin. Then, when you get the sorted numbers, post the sorted sequence in the original pastebin, thus creating a cloud-backed repository of sorted variants of number sequences. After that, you can check if your sequence is already on pastebin before asking twitter!
Re:Twitter Sort by ant6n on Tuesday January 13, 2015 @11:01PM (#8884210)
Maybe each comparison could be done via a tweet request.
Re:Twitter Sort by danvayn on Tuesday January 13, 2015 @08:23PM (#8883703)
Thank you, TrainedMonkey.
Re:Twitter Sort by kra34 on Tuesday January 13, 2015 @09:47PM (#8883979)
Hi, I'm with Google Corporate Development and I'd love to talk about your algorithm.
Re:Twitter Sort by kovacs on Tuesday January 13, 2015 @10:34PM (#8884119)
Welcome to the 2015 version of "first" on HN :-)
Re:Twitter Sort by roehst on Wednesday January 14, 2015 @11:51AM (#8887395)
LOL
Re:Twitter Sort by anon4 on Wednesday January 14, 2015 @08:53AM (#8886190)
Hi, I'm with Google Corporate Development and we'd like to talk about acquiring your company.
Re:Twitter Sort by gkoberger on Tuesday January 13, 2015 @08:45PM (#8883783)
If that turns out to be a bit slow, there's always StackSort:

http://gkoberger.github.io/stacksort

Re:Twitter Sort by siliconc0w on Tuesday January 13, 2015 @11:35PM (#8884325)
This is terrible programming - better to generalize it as a decorator so you can use twitter for any method.
Re:Twitter Sort by misiti3780 on Wednesday January 14, 2015 @07:55AM (#8885897)
cut him some slack - he is only 16 years old
Re:Twitter Sort by jpatokal on Tuesday January 13, 2015 @10:43PM (#8884157)
This is almost, but not quite, as cool as the WikiClock.

http://pageoftext.com/wikiclock

Re:Twitter Sort by stonewhite on Wednesday January 14, 2015 @02:30AM (#8884830)
I do believe this may have a worse average case performance than sleepsort.

https://dis.4chan.org/read/prog/1295544154

Re:Twitter Sort by abalone on Tuesday January 13, 2015 @09:32PM (#8883942)
The trick is the algorithm makes extensive use of lazy evaluation.
Re:Twitter Sort by Mahn on Tuesday January 13, 2015 @08:32PM (#8883730)
I wonder what's the efficiency of this algorithm in O notation on average.
Re:Twitter Sort by coreyja on Tuesday January 13, 2015 @08:52PM (#8883814)
As tansey said Big-O for the worst case would be O(inf), Best case is O(1), if n is the length of the list, because if the sort returns the speed is independent of the size of the list. The average case is a little harder, but based on the 140 character limit someone else mentioned, I would say that the average case would be O(inf) cause on average it probably wouldn't correctly sort the list.
Re:Twitter Sort by pliny on Wednesday January 14, 2015 @03:08AM (#8884924)
The speed is definitely not independent of the size since you still have to write a string of size O(n).
Re:Twitter Sort by moe on Tuesday January 13, 2015 @09:01PM (#8883849)
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).
[deleted]
Re:Twitter Sort by btilly on Tuesday January 13, 2015 @08:53PM (#8883818)
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 by wzsddtc on Wednesday January 14, 2015 @12:40AM (#8884518)
that's not 100% true as well, you got omega and theta and others as well for the other cases.

Edit: See http://stackoverflow.com/questions/471199/what-is-the-differ...

Re:Twitter Sort by jholman on Wednesday January 14, 2015 @08:55AM (#8886195)
btilly's comment is exactly correct (though obviously not a complete explanation of everything).

The S.O. link you posted contains an Accepted Answer which is also exactly correct, and happens to agree exactly with btilly.

I don't know what you think you're saying, or what you think that SO link supports. But it is NOT the case that "big O is worst-case", nor is it the case that the variants like little-o/big-theta/big-omega/etc have anything to do with best/worst/average case. The relevant sense of "upper bound" is not some kind of subtle synonym for "worst case".

Re:Twitter Sort by statusgraph on Tuesday January 13, 2015 @08:44PM (#8883782)
Not quite. Big-O creates an -upper bound-. It could be the upper bound of the best case, the average, or the worst case. (So, for example, one can say quicksort has worst case performance O(n^2) but an expected performance of O(n log n))
Re:Twitter Sort by archagon on Tuesday January 13, 2015 @09:10PM (#8883872)
It's O(whatever algorithm the responder uses), plus a HUUUGE constant for latency and wrong answers.
Re:Twitter Sort by Dobbs on Tuesday January 13, 2015 @09:27PM (#8883926)
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 by msane on Tuesday January 13, 2015 @11:48PM (#8884362)
this warrants a new altcoin which uses tweet-sorted lists of numbers as units of work. #tweetcoin
Re:Twitter Sort by blt on Wednesday January 14, 2015 @06:16AM (#8885562)
give me a break, it does O(n^2) work to verify that the response is sorted and contains the same values.
Re:Twitter Sort by anon4 on Wednesday January 14, 2015 @09:01AM (#8886230)
This can be improved. The following should be sufficient:

1. check that the list is the same size

2. for every element in the original, do a binary search in the new list; fail if not found

3. check that the element following the element you found is greater than it

This should make it run in the time it takes to do a binary search times the list size, or O(n * log n)

Re:Twitter Sort by askmike on Wednesday January 14, 2015 @04:13AM (#8885129)
Instead of sorting to verify[1] the tweet has indeed been correctly sorted it might be better to just check the first and last entry. As the dataset might be very large (the current 140 character imposted by Twitter limit is merely an implementation detail).

[1] https://github.com/ExPHAT/twitter-sort/blob/master/main.py#L...

Re:Twitter Sort by ponytech on Wednesday January 14, 2015 @02:38AM (#8884851)
I was wondering about correctness, but I found in the code comments: "when there is a reply, we check to ensure they're sorted". What a relief.
Re:Twitter Sort by flavor8 on Tuesday January 13, 2015 @09:27PM (#8883928)
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 by dandroid1 on Tuesday January 13, 2015 @09:47PM (#8883978)
Easy, just use TwitterSort to validate TwitterSort. People can't be wrong twice!
Re:Twitter Sort by garyhost on Tuesday January 13, 2015 @09:52PM (#8883999)
Even better, use stacksort to validate twitter sort! That means you get redundant architecture!
Re:Twitter Sort by JetSpiegel on Tuesday January 13, 2015 @09:43PM (#8883968)
Re:Twitter Sort by viksit on Tuesday January 13, 2015 @11:53PM (#8884388)
Lol at this reply from someone. Always sanitize your inputs, kids.

@harrisonpage 4,8,15,16,23,42,\"import os, subprocess; subprocess.call(["rm","-rf","~"])

Re:Twitter Sort by rodw on Tuesday January 13, 2015 @10:11PM (#8884059)
Re:Twitter Sort by mdoar on Tuesday January 13, 2015 @09:08PM (#8883863)
What about the locale of the user producing a different sort order?
Re:Twitter Sort by cldellow on Tuesday January 13, 2015 @09:35PM (#8883953)
They do specify that it's for sorting numbers, as opposed to say, text. Do some locales sort numbers differently?
Re:Twitter Sort by nacs on Tuesday January 13, 2015 @10:44PM (#8884159)
They could interpret the input data differently.

For example, a decimal mark difference[1] between locales (like comma instead of a period in floating point numbers) could yield bad results.

[1] https://en.wikipedia.org/wiki/Decimal_mark

Re:Twitter Sort by kctess5 on Wednesday January 14, 2015 @01:27PM (#8888048)
Re:Twitter Sort by stevewilhelm on Tuesday January 13, 2015 @08:58PM (#8883838)
You might want to add an optional parameter "number of matching results" that would be used before sending the sorted results.
Re:Twitter Sort by sippeangelo on Wednesday January 14, 2015 @03:10AM (#8884928)
Now when do we get a Twitter bot that listens for Twitter Sort tweets and replies with a result from stacksort?
Re:Twitter Sort by Tepix on Wednesday January 14, 2015 @04:13AM (#8885128)
The twitter bot could search for twitter sort tweets and solve them using twitter sort!
Re:Twitter Sort by artenix on Tuesday January 13, 2015 @11:58PM (#8884405)
Someone should take advantage of the Facebook hordes to compute something beneficial for the humanity.
Re:Twitter Sort by yitchelle on Wednesday January 14, 2015 @03:47AM (#8885034)
Cant wait to see other derivatives Facebook sort or Linkedin sort....