Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Re: fastest way to compare two arrays

by BrowserUk (Pope)
on Apr 14, 2011 at 00:47 UTC ( #899317=note: print w/replies, xml ) Need Help??

in reply to fastest way to compare two arrays

This shoudl be a little quicker. It uses a bit vector rather than a hash which is a bit quicker to start. It then scans the bit vector 64-bits at a time until it finds a possibility and then by bit until it isolates the next value:

#! perl -slw use strict; my @ports = ( 50000..51545,51549,51555..51999, 65535 ); my $vec = ''; vec( $vec, $_, 1 ) = 1 for 0 .. 50_000, @ports; sub nextFreePort { no warnings 'portable'; my $open_port; my $t = int( length( $vec ) / 8 ); my $n = 782; ++$n while $n <= $t and vec( $vec, $n, 64 ) == 1844674407370955161 +5; $n *= 64; vec( $vec, $_, 1 ) or $open_port = $_ and last for $n .. $n + 64; vec( $vec, $open_port, 1 ) = 1; return $open_port; } my $next_port = nextFreePort(); print $next_port; __END__ c:\test> 51546

Worst case of only 65535 being available, it does 242+63 tests+incs, rather than 15500.

If I were writing this in assembler, I'd test lo/hi 32-bit; lo/hi 16-bit; lo/hi 8-bit before hitting the bits individually thereby reducing the 63 tests/incs to 10.

It require 8k of string which is quite possibly smaller than your hash. That coudl be reduced further by not storing bits for 0 .. 50_000.

It's a POC. I haven't tested the edge cases.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2016-10-22 09:41 GMT
Find Nodes?
    Voting Booth?
    How many different varieties (color, size, etc) of socks do you have in your sock drawer?

    Results (294 votes). Check out past polls.