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
[download]

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.

With the data structures you have and if this is a one time operation then a linear search is probably the best you can do. If you have the option of changing the way the port information is stored there are many ways to improve performance even for a one time search.

If you need to search multiple times for the same @range and for only small changes in @ports then taking the hit to transform the port map into a better structure, or at least caching the next untested port will help speed things up. In any case wrapping the information up in an object is likely to make it much easier to manage correctly.

If you want to provide typical use cases you may get a more focused answer.

@hash{@range} = (1) x @range;  #guess I don't need to replicate now.
delete @hash{@ports};
@open = sort {$a <=> $b} keys %hash; 
#seems to work
[download]

krusty:

Two questions:

1. Do you really need to use an array?
2. Do you really need the lowest-numbered available port?

If the answer is no for both, you might consider using a hash to hold your free ports. So when you want to use a free port, just grab the first available one without sorting, and remove it from the "available" hash. When you're done with it, just return it to the hash.

If you must use an array, but don't need the lowest-numbered port, then just pop a port from your list, and when you're done with it, push it back on.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

#!/usr/bin/perl
use strict;
use warnings;
use Set::IntSpan;

my $range = Set::IntSpan->new( '50000-65535' );
my $used  = Set::IntSpan->new( '50000-51545,51549,51555-51999' );

my $unused = $range->diff( $used );

my @newports;
while (my $port = $unused->next) {
    print $port, "\n";
    push @newports, $port;
    last if @newports == 10;
}

print "Unused before newports: ", $unused->run_list, "\n";
for (@newports) {
    $unused->remove($_);
    $used->insert($_);
}
print "Unused after newports: ", $unused->run_list, "\n";
print "Used after newports: ", $used->run_list, "\n";

__END__
C:\Old_Data\perlp>perl t5.pl
51546
51547
51548
51550
51551
51552
51553
51554
52000
52001
Unused before newports: 51546-51548,51550-51554,52000-65535
Unused after newports: 52002-65535
Used after newports: 50000-52001
[download]

Sets are stored internally in a run-length coded form. This provides for both compact storage and efficient computation. In particular, set operations can be performed directly on the encoded representation...

my $range = Set::IntSpan::Fast->new('50000-65535');
my $ports = Set::IntSpan::Fast->new('50000-51545,51549,51555-51999');

my $unused = $ports->copy;
$unused->invert;

my $unused_in_range = $range->intersection($unused);

my $first_unused = ($unused_in_range->iterate_runs->())[0];
[download]