c++ - 如何通过键有效地合并 k 个排序的成对键/值 vector ？

Question

我要合并k按键对成对的键/值 vector 进行排序。通常，大小 n vector 的数量非常大(例如 n >= 4,000,000,000 )。

考虑以下 k = 2 的示例:

// Input
keys_1 = [1, 2, 3, 4], values_1 = [11, 12, 13, 14]
keys_2 = [3, 4, 5, 6], values_2 = [23, 24, 25, 26]

// Output
merged_keys = [1, 2, 3, 3, 4, 4, 5, 6], merged_values = [11, 12, 13, 23, 14, 24, 25, 26]

自 __gnu_parallel::multiway_merge是一个高效的k -way 合并算法，我尝试利用最先进的 zip 迭代器 ( https://github.com/dpellegr/ZipIterator ) 来“组合”键值对 vector 。

#include <iostream>
#include <vector>
#include <parallel/algorithm>

#include "ZipIterator.hpp"

int main(int argc, char* argv[]) {
  std::vector<int> keys_1   = {1, 2, 3, 4};
  std::vector<int> values_1 = {11, 12, 13, 14};
  std::vector<int> keys_2   = {3, 4, 5, 6};
  std::vector<int> values_2 = {23, 24, 25, 26};

  std::vector<int> merged_keys(8);
  std::vector<int> merged_values(8);

  auto kv_it_1 = Zip(keys_1, values_1);
  auto kv_it_2 = Zip(keys_2, values_2);
  auto mkv_it = Zip(merged_keys, merged_values);

  auto it_pairs = {std::make_pair(kv_it_1.begin(), kv_it_1.end()),
                   std::make_pair(kv_it_2.begin(), kv_it_2.end())};

  __gnu_parallel::multiway_merge(it_pairs.begin(), it_pairs.end(), mkv_it.begin(), 8, std::less<>());
  
  for (size_t i = 0; i < 8; ++i) {
    std::cout << merged_keys[i] << ":" << merged_values[i] << (i == 7 ? "\n" : ", ");
  }

  return 0;
}

但是，我遇到了各种编译错误(使用 -O3 构建):

error: cannot bind non-const lvalue reference of type' std::__iterator_traits<ZipIter<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator > > >, void>::value_type&' {aka 'std::tuple<int, int>&'} to an rvalue of type' std::tuple<int, int>'

error: cannot convert ‘ZipIter<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator > > >::reference*’ {aka ‘ZipRef<int, int>’} to ‘_ValueType’ {aka ‘std::tuple<int, int>*’}

是否可以修改ZipIterator让它发挥作用？

或者是否有更有效的合并方式 k按键对成对的键/值 vector 进行排序？

考虑的替代方案

1. 定义一个KeyValuePair struct与 int key和 int value成员以及operator<和 operator<=运营商。将键/值 vector 的元素移动到 std::vector<KeyValuePair> 中秒。调用__gnu_parallel::multiway_merge在 std::vector<KeyValuePair> 上秒。将合并的元素移回键/值 vector 中。 [结论:执行缓慢，内存开销高，即使使用 -O3 ]
2. 使用std::merge(std::execution::par_unseq, kv_it_1.begin(), kv_it_1.end(), kv_it_2.begin(), kv_it_2.end(), mkv_it.begin());而不是 __gnu_parallel::multiway_merge . [结论:仅支持两个键/值 vector ]

Answer 1

Is it possible to modify the ZipIterator to make it work?

是的，但它需要修补 __gnu_parallel::multiway_merge .错误来源是this line :

      /** @brief Dereference operator.
      *  @return Referenced element. */
      typename std::iterator_traits<_RAIter>::value_type&
      operator*() const
      { return *_M_current; }

这是_GuardedIterator的成员函数- multiway_merge中使用的辅助结构执行。它包装 _RAIter在你的例子中是 ZipIter .根据定义，当迭代器被取消引用时( *_M_current )，返回表达式的类型应该是 reference类型。但是，此代码期望它是 value_type& .在大多数情况下，这些是相同的类型。事实上，当您取消引用一个项目时，您希望获得对这个项目的引用。但是，使用 zip 迭代器是不可能的，因为它的元素是虚拟的，它们是动态创建的。这就是为什么 reference ZipIter 的类型根本不是引用类型，它实际上是一个 value type called ZipRef :

  using reference = ZipRef<std::remove_reference_t<typename std::iterator_traits<IT>::reference>...>;

与(非常讨厌)vector<bool> 一起使用的相同做法.

所以，ZipIterator是没有问题的，或者你如何使用算法，这对算法本身来说是一个重要的要求。下一个问题是，我们可以摆脱它吗？

答案是肯定的。您可以更改 _GuardedIterator::operator*()返回 reference而不是 value_type& .那么你会出现编译错误in this line :

      // Default value for potentially non-default-constructible types.
      _ValueType* __arbitrary_element = 0;

      for (_SeqNumber __t = 0; __t < __k; ++__t)
        {
          if(!__arbitrary_element
             && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
            __arbitrary_element = &(*__seqs_begin[__t].first);
        }

这里元素的地址取自一些__arbitrary_element .我们可以存储此元素的拷贝，因为我们知道 ZipRef复制成本低，并且可以默认构造:

      // Local copy of the element
      _ValueType __arbitrary_element_val;
      _ValueType* __arbitrary_element = 0;

      for (_SeqNumber __t = 0; __t < __k; ++__t)
        {
          if(!__arbitrary_element
             && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0) {
            __arbitrary_element_val = *__seqs_begin[__t].first;
            __arbitrary_element = &__arbitrary_element_val;
          }
        }

同样的错误会出现在文件multiseq_selection.h的多处，例如here和 here .使用类似的技术修复所有这些问题。

然后你会看到多个像这样的错误:

./parallel/multiway_merge.h:879:29: error: passing ‘const ZipIter<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >’ as ‘this’ argument discards qualifiers [-fpermissive]

它们是关于 const 不正确的。它们是因为您声明了 it_pairs作为auto ，在这个特定的场景中推导出类型为 std::inializer_list .这是一种非常奇特的类型。例如，它只提供对其成员的常量 访问，即使它本身没有声明为常量。这就是这些错误的来源。更改 auto例如std::vector这些错误都消失了。

此时应该编译 find。只是不要忘记用 -fopenmp 编译否则您将收到“对 `omp_get_thread_num' 的 undefined reference ”错误。

这是我看到的输出:

$ ./a.out
1:11, 2:12, 3:13, 3:23, 4:14, 4:24, 5:25, 6:26