Rob Dixon wrote:
> "R. Joseph Newton" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]
> > Hi,
> >
> > I'm wondering if there is an issue with the random function in terms of scaling.
> [snip data]
> >
> > Needless to say, that is a lot of . Is there any alternativcollisionse random
> > function that provides greater variation?
>
> Hi Joseph.
>
> Careful inspection shows that each of your random numbers is exactly divisible
> by 3.0517578125. Dividing your range of 100000 by this figure (magically, for
> those who know their powers of two) gives 32768, showing that 'rand' is in fact
> producing a 15-bit pseudo-random number scaled according to the range that
> you supply.
>
> As Todd says, there is a Math::TrulyRandom module, but I believe it runs only
> on Unix (I believe you're on WinNT?). A quick search shows that there are
> several random number routines, notably Data::Random, which may provide
> what you need.
>
> Cheers,
>
> Rob
Thanks Rob and Todd,
As it turns out, the module for my purposes was Math::Random. As you pointed out,
TrulyRandom is not well suited to Win32 installations. Data::Random is a little too
specialized to strings and enums for my general ranodm-generation purposes.
Math::Random::random_uniform_integer($n, $low, $high) works perfectly for the kind of
testing on numeric sorts that I am doing. The random_uniform($n, $low, $high) works
well, too, but I like the neater look with just integers:
Merge-sort note: The merge-sort isn't terribly fast, but it is reliable. It
maintains O(n log(n)) time regardless of the order of elements it is sorting. I use
it because it has no degenerate or pathological cases. For pre-sorted arrays, though,
it can seem a bit wasteful. If I load @array in order:
for (1..100000) { push @array, ($_ + 3); }
the algorithm will still conduct the same number of operations:
sort took 11 seconds for 100000 items
Performed 1668928 transfers in sorting.
4
5
6
7
8
9
...
sort took 12 seconds for 100000 items
Performed 1668928 transfers in sorting.
15
26
46
46
74
88
96
106
108
115
117
121
144
176
177
179
185
191
203
208
231
235
238
241
247
253
258
259
261
273
[end first 30]
Joseph
['da code]
#!/usr/bin/perl -w
use strict;
use warnings;
use Math::Random;
sub start_sort();
sub merge_sort($$$);
sub merge($$$$);
our $subs;
start_sort();
sub start_sort() {
my ($time1, $time2);
my @array;
my $items = 100000;
# @array = random_uniform_integer($items, 1, 1000000);
for (1..100000) { push @array, ($_ + 3); }
my $length = @array;
$time1 = time();
merge_sort([EMAIL PROTECTED], 0, $length);
# my @new_array = sort {$a <=> $b} @array;
$time2 = time();
my $elapsed_time = $time2 - $time1;
print "sort took $elapsed_time seconds for $items items\n";
our $subs;
print "Performed $subs transfers in sorting.\n";
print "$array[$_]\n" for (0..29);
# print "$new_array[$_]\n" for (0..29);
# print "$_ : $array[$_]\n" for ([EMAIL PROTECTED] - 1);
}
sub merge_sort($$$) {
my ($array_ref, $start_index, $length) = @_;
my $end_index = $start_index + $length;
my $mid_index = int($length/2) + $start_index;
return if $length < 2;
merge_sort ($array_ref, $start_index, $mid_index - $start_index);
merge_sort ($array_ref, $mid_index, $end_index - $mid_index);
merge ($array_ref, $start_index, $mid_index, $end_index);
}
sub merge($$$$) {
my ($array_ref, $start_index, $mid_index, $end_index) = @_;
my $i = $start_index;
my $j = $mid_index;
my @buffer = ();
my $rounds = 0;
our $subs;
while ($i < $mid_index and $j < $end_index) {
if ($$array_ref[$i] <= $$array_ref[$j]) {
push @buffer, $$array_ref[$i++];
$subs++;
} else {
push @buffer, $$array_ref[$j++];
$subs++;
}
}
while ($i < $mid_index) {
push @buffer, $$array_ref[$i++];
$subs++;
}
while ($j < $end_index) {
push @buffer, $$array_ref[$j++];
$subs++;
}
my $buff_length = @buffer;
# print "Buffer has $buff_length items\n"; #debug--why the top item?
for ([EMAIL PROTECTED] - 1) {
$$array_ref[$_ + $start_index] = $buffer[$_];
}
}
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
