Syntactic Confectionery Delight PerlMonks

### 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>899314.pl
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.

Create A New User
Node Status?
node history
Node Type: note [id://899317]
help
Chatterbox?
 [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?
As of 2018-03-19 20:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (246 votes). Check out past polls.

Notices?