c++ - 简单的。比较两个 800k 每个元素数组的快速方法

Question

使用 mt19937_64 生成器我生成了 800 000 个整数，范围从 0 到 30 000 000。每个数字都必须是唯一的，所以我应该将它与每个已经生成的整数进行比较:

unsigned array[800 000]; 
for (int i = 0; i < 800 000; i++)
  {
    generate_again:      
    buffer = uid(rng); // generate in buffer

    for (int j = 0; j < i; j++) // *comparing to every already generated integer
      {
        if (buffer == array[j])
          goto generate_again; // if the same integer exist, go togenerate_again flag
      }
      array[i] = pepper; // is integer is unique - it goes to array.
  }

这个比较大约需要 16 分钟。我怎样才能做得更快？谢谢。

Answer 1

您可以先按顺序生成唯一数字，然后将它们打乱以获得最终结果(如果您需要的话)。

使用 std::bitset 如果值已经生成，这将是一种有效的存储方式。或者，如果您在编译时实际上不知道值的数量，则可以使用 std::vector<bool> 这是一个使用位操作的特化也将为您节省一些空间。

#include <iostream>

#include <vector>
#include <algorithm>
#include <random>
#include <bitset>


int main()
{
    static constexpr int max_value = 30'000'000;
    static constexpr int n_values = 800'000;

    std::bitset<max_value + 1> have_num;

    int cur_n_values = 0;

    std::mt19937_64 mt{std::random_device{}()};
    std::uniform_int_distribution<int> distribution{0, max_value};


    while (cur_n_values != n_values) {
        auto newVal = distribution(mt);

        if (!have_num[newVal]) {
            have_num[newVal] = true;
            ++cur_n_values;
        }
    }

    std::vector<int> nums;
    nums.reserve(n_values);

    for (int i = 0; i < have_num.size(); ++i) {
        if (have_num[i]) {
            nums.push_back(i);
        }
    }

    std::shuffle(nums.begin(), nums.end(), mt);

    for (auto i : nums) {
        std::cout << i << " ";
    }
}

LIVE