とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

ユニークな要素の数を得る。ダブった分の要素の数を得る

重複した数/してない数 - Faith and Brave - C++で遊ぼう
ぱっと見でなんか効率が気になったので自分で書いてみた。

#if !defined(SSCRISK_ALGORITHM_COUNT_UNIQUE_HPP)
#define SSCRISK_ALGORITHM_COUNT_UNIQUE_HPP
#if defined(_MSC_VER) && _MSC_VER >= 1020
#pragma once
#endif

// count_unique.hpp

#include<iterator>
#include<cassert>
#if !defined(NDEBUG)
#include<algorithm>
#endif
#include<functional>

namespace sscrisk{
 
 template<class ForwardIterator, class BinaryPredicate>
 inline typename std::iterator_traits<ForwardIterator>::difference_type
 count_unique(ForwardIterator first, ForwardIterator last,
              BinaryPredicate pred)
 {
  assert(std::is_sorted(first, last));
  if(first == last)return 0;
  typename std::iterator_traits<ForwardIterator>::difference_type unique = 1;
  for(ForwardIterator i = first, j = ++first; j != last; ++j)
   if(!pred(*i, *j))
   {
    ++unique;
    i = j;
   }
  return unique;
 }
 
 template<class ForwardIterator>
 inline typename std::iterator_traits<ForwardIterator>::difference_type
 count_unique(ForwardIterator first, ForwardIterator last)
 {
  return count_unique(first, last, std::equal_to<typename std::iterator_traits<ForwardIterator>::value_type>());
 }

 
 template<class ForwardIterator, class BinaryPredicate>
 inline typename std::iterator_traits<ForwardIterator>::difference_type
 count_overlap(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
 {
  assert(std::is_sorted(first, last));
  if(first == last)return 0;
  typename std::iterator_traits<ForwardIterator>::difference_type overlap = 0;
  for(ForwardIterator i = first, j = ++first; j != last; ++j)
   if(pred(*i, *j))
    ++overlap;
   else
    i = j;
  return overlap;
 }
 
 template<class ForwardIterator>
 inline typename std::iterator_traits<ForwardIterator>::difference_type
 count_overlap(ForwardIterator first, ForwardIterator last)
 {
  return count_overlap(first, last, std::equal_to<typename std::iterator_traits<ForwardIterator>::value_type>());
 }
 
}

#endif

g++ 4.6 で最適化(-O1以上)をかけると元ネタより速くなることを確認。
こんな感じで使う。

#include<vector>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cassert>
#include<sscrisk/algorithm/count_unique.hpp>

int main()
{
 using namespace std; using namespace sscrisk;
 
 vector<int> v;
 for(unsigned n = 0; n != 1000000; ++n)v.push_back(rand());
 sort(v.begin(), v.end());
 cout << count_unique(v.begin(), v.end()) << endl;
 cout << count_overlap(v.begin(), v.end()) << endl;
 assert((count_unique(v.begin(), v.end()) + count_overlap(v.begin(), v.end())) == v.size());
}

実行結果(例):

32768
967232

の std::equal_to とかって C++0x 的にどうなんだろ?時代遅れ?別の良い方法がある?

追記:別解

追記2:別解2

コメントいただきました。

デフォルトの名無しさん 2011/02/17 10:14 リンク先の faith_and_brave さんとこにもコメントしたのですが、
std::adjacent_find() が部分的に使えそうな場面だと思いました。

コードはこれ。
C++ code - 64 lines - codepad