LoginSignup
6
2

More than 5 years have passed since last update.

@SaitoAtsushi(齊藤 敦志)

数列の操作

Posted at

導入

先日、各種プログラミング言語を用いて基本的な数列操作を比較するという記事を読みました。

》様々な言語でMap, Filter, Reduceを実現してみた(1)

元記事の趣旨からは逸れるのですが、やはり C++ を使うのならばもっと効率的にできないかということは考えてしまいます。

同じ計算結果を導けるように、そして充分に効率的にというだけであれば以下のように書けます。

#include <iostream>

int main(void) {
  long long result=0;
  for(long long i=0; i<10000000LL; ++i) if((i*2)%3==0) result+=i*2;
  std::cout << result << std::endl;

  return 0;
}

数学的な知識 (等差級数) を用いた変形をしない範囲ではこれが最速の形だと思います。 しかし、この状態では各操作を部品として切り出すことが難しいです。 数列を操作するのに適した抽象化をしたいところです。

元記事のように順番に関数を呼び出す形式で、しかし巨大な途中結果を保存しないで済むような方法としては遅延シーケンス (言語によって色々な呼び名があって少しづつ違う部分もあるのでここではとりあえずこの用語を採用します) のようなものがあると便利です。 C++ の標準ライブラリにはそういったものは含まれませんが、コンテナやイテレータの規約を満たすように定義すれば値が実際にメモリ上に並んでいなくても見かけ上はコンテナやイテレータとして振る舞わせることが可能です。 練習のため自分で書いてみることにしました。

もっとも、より洗練されたものが Boost にはあるようです。 実用するのであればそういった実績ある実装を用いるのが良いと思います。

整数列の生成

順番に並んだ整数を生成するコンテナを考えてみます。

countup.hpp
#ifndef HEADER_b8b6a52456f08626e557bee1cd683c1a
#define HEADER_b8b6a52456f08626e557bee1cd683c1a

#include <type_traits>
#include <iterator>
#include <limits>

template<class T>
class countup_iterator {
private:
  T num;
  using type =
    countup_iterator<typename std::enable_if<std::is_integral<T>::value, T>::type>;
public:
  using value_type        = T;
  using difference_type   = T;
  using pointer           = T*;
  using reference         = T&;
  using iterator_category = std::forward_iterator_tag;

  countup_iterator(const T num) : num(num) {}
  type& operator++(void) { ++num; return *this; }
  type operator++(int) { type t = *this; ++num; return t; }
  T operator*(void) { return num; }
  T& operator->(void) { return &num; }
  bool operator==(const type& x) { return num==x.num; }
  bool operator!=(const type& x) { return num!=x.num; }
};

template<class T>
class countup {
private:
  T start;
  T stop;
public:
  using value_type = T;
  using reference = T&;
  using iterator = countup_iterator<T>;
  using const_iterator = countup_iterator<T>;
  using difference_type = value_type;
  using size_type = typename std::make_unsigned<value_type>::type;

  countup(const T start, const T stop) : start(start), stop(stop) {}
  const_iterator begin(void) const { return iterator(start); }
  const_iterator cbegin(void) const { return begin(start); }
  const_iterator end(void) const { return iterator(stop); }
  const_iterator cend(void) const { return end(stop); }
  bool operator==(const countup& cnt) {
    return start==cnt.start && stop==cnt.stop;
  }
  bool operator!=(const countup& cnt) { return !(*this==cnt); }
  void swap(countup& cnt) {
    std::swap(start, cnt.start);
    std::swap(stop, cnt.stop);
  }
  size_type size(void) {
    return std::distance(std::begin(*this), std::end(*this));
  }
  size_type max_size(void) {
    return std::numeric_limits<size_type>::max();
  }
  bool empty(void) {
    return begin()==end();
  }
};

template<class T>
typename std::enable_if<std::is_integral<T>::value, countup<T>>::type
make_countup(const T start, const T stop) {
  return countup<T>(start, stop);
}

#endif

使い方は以下のようになります。

countup_sample.cpp
#include <iostream>
#include "countup.hpp"

int main(void) {
  auto a = make_countup(10, 20); // 10 以上、 20 より小さい整数をもつコンテナ (のようなもの)
  for(auto e: a) std::cout << e << std::endl;

  return 0;
}

あたかもコンテナの中身を表示しているように見えますが、実際にはひとつ値を取り出すたびに生成しているので、いくら大きな数列であってもメモリの占有量は変わりません。

写像

コンテナの全ての要素に関数を適用するには、一般的には std::transform を使うのですが、実際に値を取り出すときまで適用を遅延するようなコンテナを作ってみました。

lazymap.hpp
#ifndef HEADER_78ae8f2350d09c5c1f8ad0fb24c00858
#define HEADER_78ae8f2350d09c5c1f8ad0fb24c00858

#include <functional>
#include <type_traits>
#include <limits>
#include <iterator>

template<class IT, class T=typename std::iterator_traits<IT>::value_type>
class lazymap_iterator {
public:
  using value_type = T;
  using difference_type = typename std::iterator_traits<IT>::difference_type;
  using pointer = T*;
  using reference = T&;
  using iterator_category = typename std::forward_iterator_tag;

private:
  using type = lazymap_iterator<IT, T>;
  IT cur;
  using function_type =
    std::function<T(typename std::iterator_traits<IT>::value_type)>;
  const function_type func;
public:
  lazymap_iterator(IT cur, function_type func) :cur(cur), func(func) {}

  type& operator++(void) { ++cur; return *this; }
  type operator++(int) { type t = *this; ++cur; return t; }
  bool operator!=(const type& x) { return cur!=x.cur; }
  bool operator==(const type& x) { return cur==x.cur; }
  type::value_type operator*(void) { return func(*cur); }
  type::value_type* operator->(void) { return &func(*cur); }
};

template<class T, class U = typename T::value_type>
class lazymap {
public:
  using value_type = U;
  using reference = U&;
  using iterator = lazymap_iterator<typename T::iterator, U>;
  using const_iterator = lazymap_iterator<typename T::iterator, U>;
  using difference_type = typename T::difference_type;
  using size_type = typename T::size_type;
  using function_type = std::function<value_type (typename T::value_type)>;
private:
  using type = lazymap<T>;
  T* src;
  function_type func;
  typename T::iterator start;
  typename T::iterator stop;
public:
  lazymap(T& src, function_type func)
    : src(&src), func(func),  start(std::begin(src)), stop(std::end(src)) {}

  bool operator==(type& lm) {
    return src==lm.src
      && func==lm.func
      && start==lm.start
      && stop==lm.stop;
  }

  void swap(type& lm) {
    std::swap(src, lm.src);
    std::swap(func, lm.func);
    std::swap(start, lm.start);
    std::swap(stop, lm.stop);
  }

  bool operator!=(type& lm) { return !(*this==lm); }
  iterator begin(void) const { return iterator(start, func); }
  iterator cbegin(void) const { return begin(start, func); }
  iterator end(void) const { return iterator(stop,func); }
  iterator cend(void) const { return end(stop,func); }
  size_type size(void) {
    return std::distance(std::begin(*this), std::end(*this));
  }
  size_type max_size(void) {
    return std::numeric_limits<size_type>::max();
  }
};

template<class T, class U>
lazymap<T, typename std::result_of<U(typename T::value_type)>::type>
make_lazymap(T& cnt, U func) {
  return lazymap<T, typename std::result_of<U(typename T::value_type)>::type>(cnt, func);
}

#endif

以下のように使えます。

lazymap_sample.cpp
#include <iostream>
#include <vector>
#include "lazymap.hpp"

int main(void) {
  auto a = std::vector<long long>(10);
  for (long long i=0; i<a.size(); ++i) a[i] = i;

  auto b = make_lazymap(a, [](long long x){return "("+std::to_string(x)+")";});

  for(auto e: b) std::cout << e << std::endl;

  return 0;
}

このとき、オブジェクト b が作られた段階では関数は適用されていません。 イテレータを通じて値を取り出そうとするときに関数は適用されます。

フィルタ

同様に、処理を遅延するフィルタです。

lazyfilter.hpp
#ifndef HEADER_854ed21d7934718c2c14ecfaaf0f55d2
#define HEADER_854ed21d7934718c2c14ecfaaf0f55d2

#include <iterator>
#include <functional>
#include <limits>
#include <type_traits>

template<class T>
class lazyfilter_iterator {
public:
  using value_type = typename T::value_type;
  using difference_type = typename T::difference_type;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = typename std::forward_iterator_tag;
private:
  using type = lazyfilter_iterator<T>;
  typename T::src_type::const_iterator cur;
  const T& fc;
public:
  lazyfilter_iterator(typename T::src_type::const_iterator c, const T& fc)
    : cur(c), fc(fc) {
    for(; cur != fc.stop && !fc.pred(*cur); ++cur);
  }
  type& operator++(void) {
    ++cur;
    for(; cur != fc.stop && !fc.pred(*cur); ++cur);
    return *this;
  }
  type operator++(int) {
    type t = *this;
    ++(*this);
    return t;
  }
  bool operator!=(const type& x) { return cur!=x.cur; }
  bool operator==(const type& x) { return cur==x.cur; }
  type::value_type operator*(void) { return *cur; }
  type::value_type* operator->(void) { return &cur; }
};

template<class T>
class lazyfilter {
  template<class U> friend class lazyfilter_iterator;
private:
  using type = lazyfilter<T>;
  using src_type = T;
public:
  using value_type = typename T::value_type;
  using reference = typename T::value_type&;
  using iterator = lazyfilter_iterator<type>;
  using const_iterator = iterator;
  using difference_type = typename T::difference_type;
  using size_type = typename T::size_type;
  using predicate_type = std::function<bool (value_type)>;
private:
  const T* src;
  const typename T::const_iterator start;
  const typename T::const_iterator stop;
  const predicate_type pred;
public:
  lazyfilter(const T& s, predicate_type pred)
    : src(&s),
      pred(pred),
      start(std::begin(s)),
      stop(std::end(s)) {
  }
  bool operator==(type& ft) {
    return src==ft.src
      && pred==ft.pred
      && start==ft.start
      && stop==ft.stop;
  }
  void swap(type& ft) {
    std::swap(src, ft.src);
    std::swap(pred, ft.pred);
    std::swap(start, ft.start);
    std::swap(stop, ft.stop);
  }
  bool operator!=(type& lm) { return !(*this==lm); }
  iterator begin(void) const { return const_iterator(start, *this); }
  iterator end(void) const { return const_iterator(stop, *this); }
  iterator cbegin(void) const { return const_iterator(start, *this); }
  iterator cend(void) const { return const_iterator(stop, *this); }
  size_type size(void) {
    return std::distance(std::begin(*this), std::end(*this));
  }
  size_type max_size(void) {
    return std::numeric_limits<size_type>::max();
  }
};

template<class T> lazyfilter<T>
make_lazyfilter(const T& s, std::function<bool(typename T::value_type)> pred) {
  return lazyfilter<T>(s, pred);
}

#endif

終端をうまく処理できてなくて雑なのですが勘弁してください。

以下のように使えます。

lazyfilter_sample.cpp
#include <iostream>
#include <array>
#include "lazyfilter.hpp"

int main(void) {
  std::array<int, 10> a={1, 8, 7, 33, 21, 3, 8, 9, 21, 4};

  // 奇数だけ抽出する
  auto f = make_lazyfilter(a, [](long long x){return x%2==1;});
  for(auto e: f) {std::cout<<e<<std::endl;}

  return 0;
}

組み合わせる

さて、ここで部品は出そろいました。 これらを用いて元記事にあったような操作をやってみます。

#include <iostream>
#include <numeric>
#include <vector>

#include "countup.hpp"
#include "lazymap.hpp"
#include "lazyfilter.hpp"

int main(void) {
  // 1. Generating sequence
  auto a = make_countup(0LL, 10000000LL);

  // 2. Mapping the sequence into another
  auto mapped = make_lazymap(a, [](long long x)->long long{return x*2;});

  // 3. Filtering the sequence
  auto filtered = make_lazyfilter(mapped, [](long long x){return x%3==0;});

  // 4. Reducing the sequence
  long long result = std::accumulate(std::begin(filtered), std::end(filtered), 0LL, [](long long a, long long b){return a+b;});

  // As a result
  std::cout << result << std::endl;
  return 0;
}

数列の処理を各工程にわけてやっているように見えても実際には中間的な計算を保存していません。 そのかわり前工程のコンテナを指すポインタを保持しているので元コンテナが先に消えるとおかしなことになります。 寿命の管理には気を付けてください。

ちなみに処理速度はとりたてて速くなりませんでしたので、これくらいの規模なら std::vector でやってしまった方が楽かもしれませんね。

6
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
2