C++ 相当于 std::vector 上的 numpy.unique，具有 return_index 和 return_inverse

Question

numpy有一个unique算法的实现，返回：

1. numpy 数组的已排序唯一元素（即没有重复项）

此外，numpy.unique()还可以返回：

2. 给出唯一值的输入数组的索引
3. 重建输入数组的唯一数组的索引

C++ 标准库还实现了一种unique算法（此处），以某种方式消除连续的重复项。与std::vector<>::erase和结合std::sort()，可以返回向量的排序后的唯一元素（ 的输出 1 numpy.unique()）。

我的问题是： 或其他地方是否有任何算法stl也可以返回 的输出 2 和 3 numpy.unique()。如果没有，有没有办法有效实施？

Answer 1

这是一个仅使用一两个临时向量的版本。对于 n 个输入值，总体复杂度为 O(n log(n))。

#include <algorithm>
// using std::stable_sort, std::unique, std::unique_copy
#include <iterator>
// using std::back_inserter
#include <vector>
// using std::vector


/** Helper to implement argsort-like behavior */
template<class T>
struct SortPair
{
  T value;
  std::size_t index;

  SortPair(const T& value, std::size_t index)
    : value(value), index(index)
  {}
  SortPair(T&& value, std::size_t index)
    : value(std::move(value)), index(index)
  {}
  bool operator<(const SortPair& o) const
  { return value < o.value; }

  bool operator<(const T& o) const
  { return value < o; }

  friend bool operator<(const T& left, const SortPair& right)
  { return left < right.value; }

  bool operator==(const SortPair& o) const
  { return value == o.value; }

  friend void swap(SortPair& left, SortPair& right)
  {
      using std::swap;
      swap(left.value, right.value);
      swap(left.index, right.index);
  }
};
/**
 * Implements numpy.unique
 *
 * \tparam T scalar value type
 * \tparam Iterator input iterator for type T
 * \param first, last range of values
 * \param index if not null, returns the first indices of each unique value in
 *    the input range
 * \param inverse if not null, returns a mapping to reconstruct the input range
 *    from the output array. first[i] == returnvalue[inverse[i]]
 * \param count if not null, returns the number of times each value appears
 * \return sorted unique values from the input range
 */
template<class T, class Iterator>
std::vector<T> unique(Iterator first, Iterator last,
                      std::vector<std::size_t>* index=nullptr,
                      std::vector<std::size_t>* inverse=nullptr,
                      std::vector<std::size_t>* count=nullptr)
{
  std::vector<T> uvals;
  if(! (index || inverse || count)) { // simple case
    uvals.assign(first, last);
    using t_iter = typename std::vector<T>::iterator;
    const t_iter begin = uvals.begin(), end = uvals.end();
    std::sort(begin, end);
    uvals.erase(std::unique(begin, end), end);
    return uvals;
  }
  if(first == last) { // early out. Helps with inverse computation
    for(std::vector<std::size_t>* arg: {index, inverse, count})
      if(arg)
        arg->clear();
    return uvals;
  }
  using sort_pair = SortPair<T>;
  using sort_pair_iter = typename std::vector<sort_pair>::iterator;
  std::vector<sort_pair> sorted;
  for(std::size_t i = 0; first != last; ++i, ++first)
    sorted.emplace_back(*first, i);
  const sort_pair_iter sorted_begin = sorted.begin(), sorted_end = sorted.end();
  // stable_sort to keep first unique index
  std::stable_sort(sorted_begin, sorted_end);
  /*
   * Compute the unique values. If we still need the sorted original values,
   * this must be a copy. Otherwise we just reuse the sorted vector.
   * Note that the equality operator in SortPair only uses the value, not index
   */
  std::vector<sort_pair> upairs_copy;
  const std::vector<sort_pair>* upairs;
  if(inverse || count) {
    std::unique_copy(sorted_begin, sorted_end, std::back_inserter(upairs_copy));
    upairs = &upairs_copy;
  }
  else {
    sorted.erase(std::unique(sorted_begin, sorted_end), sorted_end);
    upairs = &sorted;
  }
  uvals.reserve(upairs->size());
  for(const sort_pair& i: *upairs)
    uvals.push_back(i.value);
  if(index) {
    index->clear();
    index->reserve(upairs->size());
    for(const sort_pair& i: *upairs)
      index->push_back(i.index);
  }
  if(count) {
    count->clear();
    count->reserve(uvals.size());
  }
  if(inverse) {
    inverse->assign(sorted.size(), 0);
    // Since inverse->resize assigns index 0, we can skip the 0-th outer loop
    sort_pair_iter sorted_i =
      std::upper_bound(sorted_begin, sorted_end, uvals.front());
    if(count)
      count->push_back(std::distance(sorted_begin, sorted_i));
    for(std::size_t i = 1; i < uvals.size(); ++i) {
      const T& uval = uvals[i];
      const sort_pair_iter range_start = sorted_i;
      // we know there is at least one value
      do
        (*inverse)[sorted_i->index] = i;
      while(++sorted_i != sorted_end && sorted_i->value == uval);
      if(count)
        count->push_back(std::distance(range_start, sorted_i));
    }
  }
  if(count && ! inverse) {
    sort_pair_iter range_start = sorted_begin;
    for(const T& uval: uvals) {
      sort_pair_iter range_end =
        std::find_if(std::next(range_start), sorted_end,
                     [&uval](const sort_pair& i) -> bool {
                       return i.value != uval;
                     });
      count->push_back(std::distance(range_start, range_end));
      range_start = range_end;
    }
    /*
     * We could use equal_range or a custom version based on an
     * exponential search to reduce the number of comparisons.
     * The reason we don't use equal_range is because it has worse
     * performance in the worst case (uvals.size() == sorted.size()).
     * We could make a heuristic and dispatch between both implementations
     */
  }
  return uvals;
}

诀窍是实现类似 np.argsort 的东西。其他一切自然而然。逆映射有点棘手，但当您首先做纸笔版本时，并不太难。

无序映射

我们还可以使用 unordered_map。对于具有 m 个唯一值的 n 个条目（通过排序）和不对唯一值进行排序，将复杂性降低到 O(n) + O(m log(m)) 。

但是，如果唯一值的数量不远小于 n，则这涉及大量临时分配。这个问题可以通过切换到哈希映射实现来解决，例如robin_hood，它使用平面哈希映射，只要键值对默认最多为 6 size_t 大。

然而，人们不应该低估哈希映射的绝对性能，即使是像 std::unordered_map 这样的平庸哈希映射。这是一个在实践中效果很好的简单版本。

#ifdef USE_ROBIN_HOOD
# include <robin_hood.h>
#else
# include <unordered_map>
#endif

template<class T, class Iterator>
std::vector<T>
unordered_unique(Iterator first, Iterator last,
                 std::vector<std::size_t>* index=nullptr,
                 std::vector<std::size_t>* inverse=nullptr,
                 std::vector<std::size_t>* count=nullptr)
{
#ifdef USE_ROBIN_HOOD
  using index_map = robin_hood::unordered_map<T, std::size_t>;
#else
  using index_map = std::unordered_map<T, std::size_t>;
#endif
  using map_iter = typename index_map::iterator;
  using map_value = typename index_map::value_type;
  for(std::vector<std::size_t>* arg: {index, inverse, count})
    if(arg)
      arg->clear();
  std::vector<T> uvals;
  index_map map;
  std::size_t cur_idx = 0;
  for(Iterator i = first; i != last; ++cur_idx, ++i) {
    const std::pair<map_iter, bool> inserted =
      map.emplace(*i, uvals.size());
    map_value& ival = *inserted.first;
    if(inserted.second) {
      uvals.push_back(ival.first);
      if(index)
        index->push_back(cur_idx);
      if(count)
        count->push_back(1);
    }
    else if(count)
      (*count)[ival.second] += 1;
    if(inverse)
      inverse->push_back(ival.second);
  }
  return uvals;
}

我用 N = 100 万个随机 int 条目以 M 为模进行了测试。M=N（约 600,000 个唯一值），Robin-Hood 版本击败了排序版本。当 M=N/10（~100,000 个唯一值）时，即使是 std 版本也胜过排序版本。