有一个数组可以包含,比方说,多达1000
个元素。它可以生成的数字范围是1 to 10^10
。现在我必须找到数组中两个数字之间的minimal absolute difference
。我想到了两种算法:
对于第一个函数,我定义了一个binarysearch
函数,它在排序数组中查找要插入的数字的位置。现在我只使用给定数组的第一个数字开始排序数组,并从第二个元素开始迭代给定数组。对于每个数字,我在排序数组中找到它的位置。如果在那个位置的数字是这个数,那么差是0,它是最低可能的,所以我退出循环。否则,我在排序后的数组中插入该数字,然后检查该数字与该数组中上一个和下一个数字之间的差异。然后我存储这个结果和上一个结果的最小值,并以这种方式继续。
第二:我使用quicksort对数组进行排序。(范围太大,所以我认为基数排序没有那么有效)。然后我对它进行迭代,如果两个连续的数字相等,则以0作为答案,否则存储该数字与前一个数字和前一个结果之间的最小差异。
哪一个更有效?
有更好的算法吗?
stackoverflow在这方面有很多帖子,但是没有多大帮助。这是我的Perl代码:
sub position {
my @list = @{$_[0]};
my $target = $_[1];
my ($low,$high) = (0, (scalar @list)-1);
while ($low <= $high) {
$mid = int(($high + $low)/2);
if ( $list[$mid] == $target ) {
return $mid;
}
elsif ( $target < $list[$mid] ) {
$high = $mid - 1;
}
else {
$low = $mid + 1;
}
}
$low;
}
sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }
sub min { $_[0] > $_[1] ? $_[1] : $_[0]; }
$ans = 10_000_000_000;
@numbers = (234, 56, 1, 34...123); #given array
($max,$min) = @num[0, 0];
@sorted = ($numbers[0]);
for ( @num[1 .. $#num] ) {
$pos = position(\@sorted, $_);
if ( $sorted[$pos] == $_ ) {
$ans = 0;
last;
}
splice @sorted, $pos, 0, $_;
if ( $#sorted == $pos ) {
$ans = min($_-$sorted[-2], $ans);
}
elsif ( 0 == $pos ) {
$ans = min($sorted[1]-$_, $ans);
}
else {
$ans = min(min(abs($sorted[$pos-1]-$_), abs($sorted[$pos+1]-$_)), $ans);
}
$max = max($_, $max);
$min = min($_, $min);
}
print "$ans\n";
最佳答案
你有多达5公里的元素。
注意,sandy bridge处理器有32kbL1-Cache,假设为4字节整数-这意味着它可以包含8192个整数。
我尽量避免创建额外的数据(计数器等除外),并使用同一个数组执行所有操作。这将使得cache-misses的数目非常小,并且可能会超过任何算法。
因此,就地快速排序和迭代数组中的元素可能比任何其他解决方案都更好,既有缓存效率,又保持了O(nlogn)
的正方形渐近复杂性。
注意-虽然这个解决方案可能会更有效(至少在理论上),但规模仍然很小-除非你要做很多次这种操作-只是不值得你花时间去优化它。
一般提示:当谈到小规模的问题(并且多达5000个元素符合这个标准)时,big-o符号通常是不够的。缓存性能通常是这些问题的主要因素。