Re: how to do effective sort in perl

If it's an efficient sort algorithm you're after, you should note that "In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm whose worst-case behavior is O(NlogN)." (perldoc). According to Numerical Recipes, "For the basic task of sorting N elements, the best algorithms require on the order of several times N log₂ N operations." That means that mergesort is just about as efficient as you can get.

Incidentally, Numerical Recipes is an astonishingly good book. Knuth may be the definitive reference, and nag may have many algorithms fine-tuned to specific cases, but NR is exceptionally good value for money. You can even download free source code in FORTRAN or C. If you're new to Perl, I'd see the lack of a Perl version as a good thing. I think it's a useful exercise in learning a language to try translating into it.

Update: Of course, all of this is overkill for the number of items likely to be found in any sensible directory!

Polonius

Comment on Re: how to do effective sort in perl

Replies are listed 'Best First'.
Re^2: how to do effective sort in perl by graff (Chancellor) on May 04, 2006 at 02:35 UTC
Of course, all of this is overkill for the number of items likely to be found in any sensible directory! heh. I've actually had to scold some of my co-workers, telling them they really should not be putting 300,000 files in a single directory, and there are easy enough ways to avoid this... Even 50,000 seems like too much to me (but then, I learned programming on a pdp 11-10, and my sense of scale may be a bit old-fashioned).	[reply]
Re^3: how to do effective sort in perl by Polonius (Friar) on May 04, 2006 at 14:57 UTC
heh. I've actually had to scold some of my co-workers, telling them they really should not be putting 300,000 files in a single directory, and there are easy enough ways to avoid this... Anything more than a screenful seems excessive to me! But then, I grew up on a Data General S-250, IIRC (Think PDP 11-70 - that sorta era, but less successful.) Polonius	[reply]
OT: Re^3: how to do effective sort in perl by MidLifeXis (Monsignor) on May 04, 2006 at 17:37 UTC
Been a while since I have referred anyone to this, but it is a pretty good introductory discussion <shamelessplug>(and response)</shamelessplug> on why some directory structures slow down after a certain number of documents are included. Not necessarily useful for those Old System Administrators¹. 1 - OSA's never die, they just put down roots. --MidLifeXis	[reply]