随机生成的排序数组：搜索性能比较

Question

我正在制作一个程序来测试和比较多键顺序搜索和插值二进制搜索的统计数据。我正在征求意见：

什么是对随机生成的整数数组进行排序，或者甚至像排序数组一样生成它的最佳方法（如果这有意义的话）在给定的上下文中？

我正在研究一些排序技术，但是，如果您记住重点是搜索（而不是排序）性能，所有高级排序似乎都相当复杂，仅在一种实用程序方法中使用。考虑到数组必须 大于 10⁶（用于测试目的），Modified/Bubble，选择或插入排序不是选项。

附加约束是所有数组成员必须唯一。

现在，我最初的想法 是将区间 [INT_MIN,INT_MAX] 拆分为 n 间隔（n 是数组长度）然后添加一个随机整数，从 0 到 2³²/n（向下舍入），到每个间隔开始。

问题是这样:

我推测，随着 n 上升到更接近 2³²，就像我的一样, 插值搜索开始提供越来越好的结果，因为它的插值变得更加准确。

然而：

如果我仅依赖 伪随机数生成器 （如 rand();），它们的分散特性决定了与 生成器相同的趋势-然后排序 数组，即 - 随着大小接近 int 限制，插值在精确定位最可能的位置方面变得更好。 Uniformity/dispersion 特征随着 n 上升到 INT_MAX 而丢失，因此，由于规定的限制，插值似乎总是获胜.

您可以随意讨论、批评和澄清这个问题，但我非常想得到答案，因为无论哪种方式，测试似乎都对插值有利，我想公平地分析它们。简而言之：我想确信我最初的想法不会进一步向 Interpolation 倾斜天平，我想使用它，因为它是 O(n).

Answer 1

所以您想生成一个 "array"，它有 N 个唯一的随机数，并且它们必须按排序顺序排列？这听起来像是 std::set 的完美用法。将元素插入 set 时，它们会自动为我们排序，并且集合只能包含唯一元素，因此它负责检查随机数是否已经生成。

std::set random_numbers;
std::random_device rd;
std::mt19937 mt(rd());
while (random_numbers.size() < number_of_random_numbers_needed)
{
    random_numbers.insert(mt());
}

然后，如果您不想将集合保留为集合，则可以将其转换为 std::vector 或 std::array 之类的其他内容。

Answer 2

好的，我决定将责任转移到内置的 PRNG 并执行以下操作：

将nrand()结果添加到二进制树并通过按顺序（从最左边的叶子开始）遍历来填充数组。

Answer 3

如何根据统计属性生成排序数组？

这可能需要一些挖掘，但您应该能够通过添加一个随机差来按顺序生成整数，该随机差的平均值是整个样本的标准差。

这会在范围边界引起一些问题，但考虑到样本的大小，您可能会忽略它。

Answer 4

这是一种生成有序随机序列的方法。这使用 Knuth 的算法 S 并取自 Programming Pearls.

一书

这需要一个函数 returns [0,1) 范围内的随机双精度数。我以 my_rand() 为例。我还对其进行了修改，为目标获取一个输出迭代器。

namespace
{
    std::random_device rd;
    std::mt19937 eng{ rd() };
    std::uniform_real_distribution<> dist; // [0,1)
    double my_rand() { return dist(eng); }
}

// Programming Pearls column 11.2
// Knuth's algorithm S (3.4.2)
// output M integers (in order) in range 1..N
template <typename OutIt>
void knuth_s(int M, int N, OutIt dest)
{
    double select = M, remaining = N;
    for (int i = 1; i <= N; ++i) {
        if (my_rand() < select / remaining) {
            *dest++ = i;
            --select;
        }
        --remaining;
    }
}

int main()
{
    std::vector<int> data;

    knuth_s(20, 200, back_inserter(data)); // 20 values in [1,200]
}

Demo in ideone.com

随机生成的排序数组：搜索性能比较

Randomly generated sorted arrays: search performances comparison

c++

sorting

random

algorithm

linear-interpolation