Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Re: An informal introduction to O(N) notation

by demerphq (Chancellor)
on Jan 21, 2003 at 14:02 UTC ( #228679=note: print w/ replies, xml ) Need Help??


in reply to Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation

It should be noted that many algorithm's O time can be reduced.

True. But then it isnt the same algorithm. :-) Also care in implementation can make one version of an algorithm outperform another. For instance I think you will find that

my $tmp; for my $i (0..$#a-1) { # looping over already-sorted items is not needed for (0..$#a-1-$i) { if ($a[$_+1] < $a[$_]) { $tmp=$a[$_]; $a[$_]=$a[$_+1]; $a[$_+1]=$tmp; } } }
Is slightly faster than your version. :-) Its funny actually but Knuth discusses this exact issue as a justification as to why he used MIX instead of a high level programming language. People have a tendency to write code in as few characters as possible. (Perl gives an opportunity to take this way beyond reasonable so we can ignore that stuff.) However very often the constructs that take the least space for the human result in the most code being excuted. To take this further for a while I was working on implementing a bunch of the AoP algorithms in perl. Some of them are not feasable as perl doesnt allow low enough operations. I believe that you will find one of the linear search algorthms (you'd never think this would be tricky) is unimplementable in perl to be more efficient than the others (even though in MIX and assembler it is).

Also IIRC the following minor change makes Bubblesort get even faster

my $tmp; my $swapped; for my $i (0..$#a-1) { $swapped=0; # looping over already-sorted items is not needed for (0..$#a-1-$i) { if ($a[$_+1] < $a[$_]) { $tmp=$a[$_]; $a[$_]=$a[$_+1]; $a[$_+1]=$tmp; $swapped=1; } } last unless $swapped; }
As it allows it to bail once the list is sorted. (Atually you could probably be clever and not use one of the extra variables, although only if undef isnt legal in the data being sorted.)

update fixed typo in the second version. thanks jryan. :-)

--- demerphq
my friends call me, usually because I'm late....


Comment on Re: Re: An informal introduction to O(N) notation
Select or Download Code
Reaped: Re^3: An informal introduction to O(N) notation
by NodeReaper (Curate) on Jan 01, 2009 at 02:30 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://228679]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (10)
As of 2014-08-21 13:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (135 votes), past polls