[HN Gopher] Pessimal Algorithms and Simplexity Analysis [pdf]
___________________________________________________________________
Pessimal Algorithms and Simplexity Analysis [pdf]
Author : belter
Score : 44 points
Date : 2021-04-12 10:50 UTC (1 days ago)
(HTM) web link (www.mipmip.org)
(TXT) w3m dump (www.mipmip.org)
| jojohohanon wrote:
| This ranks next to COMEFROM (which is observably superior to GOTO
| of the same era) as my favorite computer science jokes.
| quchen wrote:
| One of my favourite papers of all time.
|
| Most of the paper is a good joke, but Slowsort takes it a step
| further. It is just _so_ inefficient I can't help but laugh out
| loud each time I revisit the paper and re-understand the
| algorithm.
|
| It ticks all the nice boxes, such as being easily proven correct,
| easy to implement, easy to parallelize, stable, no time wasted on
| unnecessary steps, can produce output as it sorts the rest.
|
| At the same time, it's Mergesort with a ridiculous merging step.
| But that means one can simply add a parameter to tune between
| Mergesort and Slowsort - if(rand(1,10) > 8) then slow else merge
| - so the code becomes tunable in terms of speed. Someone needs
| faster software? OK, I've got just the parameter for you :-D
|
| If you haven't implemented it yourself, give it a shot. It's a
| transformative experience to see your computer struggle sorting
| an already sorted 100-entry array ;-)
| ruph123 wrote:
| Slowsort seems to be another name for the (to me) more common
| name Bogosort:
|
| https://en.wikipedia.org/wiki/Bogosort
| whatshisface wrote:
| Slowsort is guaranteed to take a long time but Bogosort could
| finish in one step.
| chriswarbo wrote:
| Bogosort is at best linear, since we have to check if the
| list is sorted.
|
| Quantum Bogosort guarantees the best performance, since it
| destroys all universes where the list remains unsorted
| after the first shuffle.
| whatshisface wrote:
| I'd like to contribute an algorithm to this field of study. I
| call it, "Spend several months researching a novel algorithm when
| brute force would have been effective for all real-world problem
| sizes."
| skit wrote:
| Didn't realize this was a joke. I was scratching my head, "There
| are engineering problems that intentionally aim to slow
| performance? Because if so all they have to do is just hire
| me..."
| jaratec wrote:
| The keyboard layout (inherited form the typewriters) comes to
| mind.
| aw1621107 wrote:
| "QWERTY was designed to slow typists down" appears to be
| somewhat disputed claim, at least going by Google results.
| There are a few articles [0, 1] based on a paper [2] saying
| that the design was more due to feedback from telegraph
| operators rather than anything to do with typewriter
| mechanics.
|
| On the other hand, if you subscribe to the "reduced jams"
| view, then that would arguably have the effect of _speeding
| up_ typing due to having to deal with jams less frequently.
|
| [0]: https://www.smithsonianmag.com/arts-culture/fact-of-
| fiction-...
|
| [1]: https://www.theatlantic.com/technology/archive/2013/05/t
| he-l...
|
| [2]: http://kanji.zinbun.kyoto-u.ac.jp/~yasuoka/publications/
| PreQ...
| chriswarbo wrote:
| Some hash functions do this, e.g. bcrypt and scrypt.
| Theoretically, their output is no more secure than faster
| algorithms like SHA; but it's less _practical_ to brute-force
| lots of guesses.
|
| Hashcash (as found in Bitcoin) is another example, albeit more
| egregious.
| nayuki wrote:
| I love multiply-and-surrender paradigms!
___________________________________________________________________
(page generated 2021-04-13 23:02 UTC)