什么是最快的排序算法为0-65535的整数？ [英] What is the fastest sort algorithm for 0-65535 integers?

问题描述

我要排序编号的整数，它可以30.000.000和350.000.000之间的值。会有介于0和65.535的整数，平均计数为20.000。 RAM的使用是不相关的，只有速度是很重要的。

后来我也需要把他们分成小组，与鸿沟总是被设置，只要其中两个值之间的差距> 65.535，这正是我所需要的算法。

如果这有什么差别，该算法将在一个Perl脚本中使用。

编辑：在思考它，阅读我已经认识到一些问题的答案后：我真的不关心数据本身。正如我真的只是想找到与小间隙组的开始和结束值，排序只需要创建桶和可丢弃数据。

EDIT2：经过一些测试，并尝试提供的答案，最快的方法，我发现是这样的：

 我@sort =排序{$ A＆LT; =＆GT; $ B} @item_offsets;
我@buckets;
我的$启动=移@sort;
推@buckets，[$开始，$开始]。
我$项目（@sort）{
    如果（$项＆lt; $水桶[$＃桶] [1] + $间隙）{
        $水桶[$＃桶] [1] = $项目;
    }
    其他 {
        推@buckets，[$项目，$项目]
    }
}
说$＃桶;
 

解决方案

我刚刚运行的算法，每个组连续的65536值之前，使桶的数组。水桶将包含分钟，并对其内容最大值，但将不存储内容本身。算法运行后，做单传过来的桶。如果有与分两个连续的非空水桶（bucket2）-max（bucket1）＆LT; 65536，将它们结合起来。组合不会发生，直到算法完成运行。丢弃任何空水桶。这个算法是线性时间

注意桶排序。

I have to sort a number of integers, which can have values between 30.000.000 and 350.000.000. There will be between 0 and 65.535 integers, with the average count being 20.000. RAM usage is irrelevant and speed only is important.

Later on i will also have to split them into groups, with the divide always being set whenever the gap between two of these values is >65.535, which is what i need the algorithm for.

If it makes any difference, the algorithm will be used in a Perl script.

Edit: After thinking it over and reading the answers i've come to realize something: I don't actually care about the data itself. As i really only want to find the start and end values of groups with small gaps, the sorting only needs to create buckets and can discard the data.

Edit2: After some testing and trying out the answers provided, the fastest way i found was this:

my @sort = sort {$a <=> $b} @item_offsets;
my @buckets;
my $start = shift @sort;
push @buckets, [$start,$start];
for my $item ( @sort ) {
    if ( $item < $buckets[$#buckets][1]+$gap ) {
        $buckets[$#buckets][1] = $item;
    }
    else {
        push @buckets, [$item,$item];
    }
}
say $#buckets;

解决方案

I'd just make an array of buckets before running the algorithm, one for each group of 65536 consecutive values. The buckets will contain a min and max value of their contents, but won't store the contents themselves. After running the algorithm, do a single pass over the buckets. If there are two consecutive non-empty buckets with min(bucket2)-max(bucket1) < 65536, combine them. Combining will not happen until the algorithm finishes running. Discard any empty buckets. This algorithm is linear time.

Take note of Bucket Sort.

这篇关于什么是最快的排序算法为0-65535的整数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！