8

一連のレコードをデータベースにバッチ処理する必要がある状況に遭遇しました。stdアルゴリズムでこれをどのように達成できるのか疑問に思っています。

10002レコードが与えられた場合、処理のために100レコードのビンに分割し、残りは2のビンにします。

うまくいけば、次のコードは私が達成しようとしていることをよりよく説明するでしょう。私はイテレータ、ラムダ、あらゆる種類の最新のC++の楽しみを含むソリューションに完全にオープンです。

#include <cassert>
#include <vector>
#include <algorithm>

template< typename T >
std::vector< std::vector< T > > chunk( std::vector<T> const& container, size_t chunk_size )
{
  return std::vector< std::vector< T > >();
}

int main()
{
  int i = 0;
  const size_t test_size = 11;
  std::vector<int> container(test_size);
  std::generate_n( std::begin(container), test_size, [&i](){ return ++i; } );

  auto chunks = chunk( container, 3 );

  assert( chunks.size() == 4 && "should be four chunks" );
  assert( chunks[0].size() == 3 && "first several chunks should have the ideal chunk size" );
  assert( chunks.back().size() == 2 && "last chunk should have the remaining 2 elements" );

  return 0;
}
4

3 に答える 3

7

この種の範囲の分割が一般的である並列化のコンテキストでは、範囲の概念、つまり、さまざまなルーチンとスレッドの間で渡される最小単位のペア（from、to）を作成すると便利であることがわかりました。処理する。

必要なメモリスペースがはるかに少ないため、各部分のサブベクトル全体のコピーを作成するよりも優れています。また、各範囲をそのままスレッドに渡すことができるため、単一のエンドイテレータのみを維持するよりも実用的です。最初または最後の部分など、特別な場合はありません。

これを念頭に置いて、以下は私がうまく機能することがわかったルーチンの簡略化されたバージョンであり、それはすべて最新のC++11です。

#include <cassert>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdint>

template <typename It>
std::vector<std::pair<It,It>>
  chunk(It range_from, It range_to, const std::ptrdiff_t num)
{
  /* Aliases, to make the rest of the code more readable. */
  using std::vector;
  using std::pair;
  using std::make_pair;
  using std::distance;
  using diff_t = std::ptrdiff_t;

  /* Total item number and portion size. */
  const diff_t total
  { distance(range_from,range_to) };
  const diff_t portion
  { total / num };

  vector<pair<It,It>> chunks(num);

  It portion_end
  { range_from };

  /* Use the 'generate' algorithm to create portions. */    
  std::generate(begin(chunks),end(chunks),[&portion_end,portion]()
        {
          It portion_start
          { portion_end };

          portion_end += portion;
          return make_pair(portion_start,portion_end);
        });

  /* The last portion's end must always be 'range_to'. */    
  chunks.back().second = range_to;

  return chunks;
}

int main()
{
  using std::distance;

  int i = 0;
  const size_t test_size = 11;
  std::vector<int> container(test_size);
  std::generate_n( std::begin(container), test_size, [&i](){ return ++i; } );

  /* This is how it's used: */    
  auto chunks = chunk(begin(container),end(container),3);

  assert( chunks.size() == 3 && "should be three chunks" );
  assert( distance(chunks[0].first,chunks[0].second) == 3 && "first several chunks should have the ideal chunk size" );
  assert( distance(chunks[2].first,chunks[2].second) == 5 && "last chunk should have 5 elements" );

  return 0;
}

提案したものとは少し異なります。部分のサイズは常に切り捨てられるため、例では3つの部分しか得られず、最後の部分は他の部分よりもわずかに大きくなります（わずかに小さくなりません）。これは簡単に変更できます（通常、部分の数は作業項目の総数よりもはるかに少ないため、それほど重要ではないと思います）。

述べる。.begin()私自身の範囲関連パターンの使用では、イテレータよりも実際に整数（それぞれがからの距離を示す）を格納する方が優れていることがすぐにわかりました。iteratorその理由は、これらの整数と実際のイテレータの間の変換は迅速で無害な操作であり、必要かどうかに関係なく実行できるためですconst_iterator。一方、イテレータを保存するときは、作業するかどうかを一度に決定する必要がありますが、これは面倒な作業iteratorにconst_iteratorなる可能性があります。

于 2013-01-09T02:13:35.417 に答える
5

問題はのバリエーションであるように思われますstd::for_each。ここで、操作したい「それぞれ」はコレクションの間隔です。したがって、各間隔の開始と終了を定義する2つのイテレーターを取り、そのラムダ/関数をアルゴリズムに渡すラムダ（または関数）を作成することをお勧めします。

これが私が思いついたものです...

// (Headers omitted)

template < typename Iterator >
void for_each_interval(
    Iterator begin
  , Iterator end
  , size_t interval_size
  , std::function<void( Iterator, Iterator )> operation )
{
  auto to = begin;

  while ( to != end )
  {
    auto from = to;

    auto counter = interval_size;
    while ( counter > 0 && to != end )
    {
      ++to;
      --counter;
    }

    operation( from, to );
  }
}

（インクリメントにstd::advance使用する内部ループが処理されることを望みますが、残念ながら、それは終わりを超えて盲目的にステップします[これをカプセル化するために独自のテンプレートを作成したい]。それが機能する場合は、約半分のコード！）countertosmart_advance

今それをテストするためのいくつかのコードのために...

// (Headers omitted)

int main( int argc, char* argv[] )
{
  // Some test data
  int foo[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  std::vector<int> my_data( foo, foo + 10 );
  size_t const interval = 3;

  typedef decltype( my_data.begin() ) iter_t;
  for_each_interval<iter_t>( my_data.begin(), my_data.end(), interval,
    []( iter_t from, iter_t to )
    {
      std::cout << "Interval:";
      std::for_each( from, to,
        [&]( int val )
        {
          std::cout << " " << val;
        } );
      std::cout << std::endl;
    } );
}

これにより、次の出力が生成されます。これは、必要なものを表していると思います。

間隔：0 1 2
間隔：3 4 5
間隔：6 7 8
間隔：9
于 2013-01-09T18:58:33.810 に答える
0

実装は少し異なりますが、イテレータに範囲操作を使用しています。また、std::partition関数を使用した実装についても考えていました。

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

template< typename Iterator >
void sized_partition( Iterator from, Iterator to, std::ptrdiff_t partition_size, std::function<void(Iterator partition_begin, Iterator partition_end)> range_operation )
{
  auto partition_end = from;
  while( partition_end != to )
  {
    while( partition_end != to && std::distance( from, partition_end ) < partition_size )
      ++partition_end;

    range_operation( from, partition_end );
    from = partition_end;
  }
}

int main()
{
  int i = 0;
  const size_t test_size = 11;
  std::vector<int> container(test_size);
  typedef std::vector<int>::iterator int_iterator;
  std::generate_n( std::begin(container), test_size, [&i](){ return ++i; } );

  sized_partition<int_iterator>( container.begin(), container.end(), 3, []( int_iterator start_partition, int_iterator end_partition )
  {
    std::cout << "Begin: ";
    std::copy( start_partition, end_partition, std::ostream_iterator<int>(std::cout, ", ") );
    std::cout << " End" << std::endl;
  });

  return 0;
}
于 2013-01-09T18:21:56.960 に答える