16

有一个数组可以包含，比如说，最多1000元素。它可以产生的数字范围是 say 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";
4

7 回答 7

16

您最多有 5k 个元素。

请注意，沙桥处理器具有 32KB L1-Cache，假设为 4 字节整数 - 这意味着它可以包含 8192 个整数。

我会尽量避免创建额外的数据（计数器等除外），并使用相同的数组完成所有操作。这将使缓存未命中的数量非常少，并且可能会胜过任何算法。

因此，就地快速排序而不是迭代数组中的元素可能会比任何其他解决方案更好，既能提高缓存效率，又能保持O(nlogn).

注意 - 虽然这个解决方案可能会更有效（至少在理论上），但规模仍然非常小 - 除非您要多次执行此操作 - 不值得您花时间过度优化它。

一般提示：当谈论小规模问题（最多 5000 个元素符合此标准）时，大 O 表示法通常是不够的。缓存性能通常是这些问题的主要因素。

于 2012-09-02T06:55:13.363 回答
11

这是一维中最接近的配对问题。请注意，解决此问题至少与解决元素唯一性问题一样难，因为如果有任何重复元素，则答案为 0。

元素唯一性问题需要O(n lg n)时间来解决，所以这个问题也必须至少有那么难。由于您提出的迭代排序解决方案是O(n lg n)，因此没有更好的渐近最坏情况算法可用。

然而，正如 wiki 文章中所指出的，有些算法的最坏情况运行时间更差，但预期运行时间是线性的。本文介绍了一种这样的方法，看起来很复杂！

于 2012-09-02T07:17:01.083 回答
5

第二个会更快，原因很简单，在第一个解决方案中，您使用的是您在 Perl 空间中编写的排序，而在第二个解决方案中，您有机会使用 Perl 内置sort的C 函数而且非常快。如此小的投入，第一个获胜几乎是不可能的，即使它有可能做更少的工作。

于 2012-09-02T07:11:26.907 回答
2

第二种算法可能更好。在第一个算法中，您使用的是插入排序，它比其他一些排序算法效率低。

于 2012-09-02T07:03:56.210 回答
1

最近对问题的简单随机筛算法描述了最近对问题的 O(n) 随机算法，并且它还参考了另一篇论文，该论文给出了一维最近对问题的 O(n log log n) 确定性算法如果您有权访问该floor功能，则会出现问题。

于 2012-09-02T15:47:24.460 回答
1

因为我们在谈论 Perl，所以我们不应该对最有效的排序算法感到好奇——在 Perl 中自己实现某些东西肯定比使用内置函数要慢。只是为了好玩，我运行了这个小脚本（为了清晰起见）：

time perl -e'
    @array = map {rand} 1..100000;
    $lastdiff=10**11;
    for(sort {$a <=> $b} @array){
        unless(defined $last){
            $last=$_;
            next
        }
        $difference = abs($last - $_);
        $last = $_;
        $lastdiff = $lastdiff < $difference ? $lastdiff : $difference;
        last if $lastdiff == 0;
    }
    print $lastdiff, "\n"
'

我设置了一个包含 100,000 个随机数的数组。该脚本在 0.42 秒内终止（在我的慢速笔记本电脑上）。考虑到我使用 ~0.12 秒进行启动和数组初始化，主要算法使用大约 0.3 秒。假设O(n)你应该在 < 0.02 秒内完成......哦，等等，这并不多......（有 5000 个元素）

如果您需要更快，请使用 Inline::C 编写算法。

于 2012-09-02T07:13:57.090 回答
0
  1. 将数组的数字复制到黑红树中
  2. 这将允许您测试 log(n) 的特定间隔中是否有数字
  3. 设置 d = inf
  4. 使用变量 i 遍历数组
  5. 如果区间 (id, i+d) 中有一个数，则设置 d 等于 |i-thatNumber|

它会带你〜n * ln找到d

于 2012-09-02T06:43:39.487 回答