| |||||||||||||
Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)Posted Jul 1, 2010 14:24 UTC (Thu) by Wol (guest, #4433)In reply to: Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs) by NRArnot Parent article: Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)
"In computer science I recall sort algorithms that are almost always fast, but in the worse cases horribly slow."
Or are usually slow but can be incredibly fast :-) Hence the need to know your data!
The sort you are thinking of is the quick sort - under most circumstances it's the fastest.
The one I'm thinking of is the bubble sort :-) The watermark-optimised version, run over a already-sorted input set, is provably the fastest sort possible! And this is also the quick-sort worst case!
I'm a regular user of the bubble sort and variants, but oftentimes I know my datasets are approximately sorted before I start.
Cheers,
(Log in to post comments)
Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs) Posted Nov 10, 2010 7:48 UTC (Wed) by Blaisorblade (guest, #25465) [Link]
A trivial insertion sort also takes linear time (and performs no permutation) on already-sorted data; moreover, . Donald Knuth already pointed out how bad bubble sort is, and other researchers recommended that bubble sort should not even be taught. See:
http://en.wikipedia.org/wiki/Bubble_sort#In_practice
|
|||||||||||||