Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

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]
[Your Mother]: Nice!!!
[Your Mother]: That was for LanX, not you. For you: TERRIBLE!!!!
[Your Mother]: Moral: Be more like LanX.
[shmem]: what nicety is next?
[shmem]: pardon me, I chimed in too late
[Your Mother]: shmem is also quite well. The rest of you, horrible!!!!

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (7)
As of 2018-03-19 20:34 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (246 votes). Check out past polls.