質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.34%

【C++】【vectorクラス】高速なベクトル足し算

解決済

回答 5

投稿

  • 評価
  • クリップ 4
  • VIEW 9,846

RyuSA

score 127

C++のstd::vectorクラスにおいての足し算実装

初歩的なものですが、C++を用いてベクトル同士の足し算を実装中です。
今現在、以下のような単純なもの浮かばないのですが
より高速なアルゴリズムをご存知の方はいませんか?

// ベクトルA,Bのサイズは同じ(サイズをNとする)
vector<int> Addition(vector<int> A, vector<int> B, int N){
    vector<int> temp(N);
    for(int i = 0 ; i < N ; i++){
        temp[i] = A[i] + B[i];
    }
    return temp
}

/* 
例:
A = [1,2,3,4], B = [5,6,7,8]
print Addition(A,B)
> [6,8,10,12]
*/
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

+5

高速化のための tips は皆さんの助言どおり。
ですがより速い"アルゴリズム"はなさそうです。
ハードウェアの助けを借りて力技でゴリ押すならマルチスレッド(SIMDもアリ)、
もっと欲張るならOpenCLとかCUDAとか。

[追記] ...ってことで、マルチスレッドとCUDAでやってみたわけよ。

#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
#include <cassert>
#include <thread>
#include <cuda_runtime.h>
#include <device_launch_parameters.h>

template<typename Function>
float time_call(Function&& f) {
  using namespace std::chrono;
  auto start = high_resolution_clock::now();
  f();
  auto stop =  high_resolution_clock::now();
  return duration_cast<microseconds>(stop - start).count() / 1000.0f;
}

void Addition_single(std::vector<int>& C, const std::vector<int>& A, const std::vector<int>& B, int N) {
  for ( int i = 0; i < N; ++i ) {
    C[i] = A[i] + B[i];
  }
}

void Addition_multi(std::vector<int>& C, const std::vector<int>& A, const std::vector<int>& B, int N) {
  const int nthr = 4;
  std::thread threads[nthr];
  for ( int t = 0; t < nthr; ++t ) {
    threads[t] = std::thread(
      [&](int begin, int end, int stride) {
        for ( int i = begin; i < end; i += stride ) {
          C[i] = A[i] + B[i];
        }
      },
      t, N, nthr);
  }
  for ( auto& thr : threads ) thr.join();
}

__global__ void kernel(int* pC, const int* pA, const int* pB, int size) {
  int i = blockDim.x * blockIdx.x + threadIdx.x;
  if ( i < size ) { 
    pC[i] = pA[i] + pB[i];
  }
}

void Addition_cuda(std::vector<int>& C, const std::vector<int>& A, const std::vector<int>& B, int N) {
  int* pA;
  int* pB;
  int* pC;
  cudaMalloc(&pA, N*sizeof(int));
  cudaMalloc(&pB, N*sizeof(int));
  cudaMalloc(&pC, N*sizeof(int));
  cudaMemcpy(pA, A.data(), N*sizeof(int), cudaMemcpyHostToDevice);
  cudaMemcpy(pB, B.data(), N*sizeof(int), cudaMemcpyHostToDevice);
  kernel<<<(N+255)/256,256>>>(pC, pA, pB, N);
  cudaMemcpy(C.data(), pC, N*sizeof(int), cudaMemcpyDeviceToHost);
}

int main() {
  int N = 2000000;
  std::vector<int> A(N);
  std::vector<int> B(N);
  for ( int i = 0; i < N; ++i ) {
    A[i] = i; B[i] = -i;
  }
  std::vector<int> C(N);

  float single = time_call([&]() { Addition_single(C, A, B, N); });
  for ( int i = 0; i < N; ++i ) assert( T[i] == 0 );
  std::cout << "single = " << single << "[ms]\n";

  float multi  = time_call([&]() { Addition_multi(C, A, B, N); });
  for ( int i = 0; i < N; ++i ) assert( T[i] == 0 );
  std::cout << "multi  = " << multi  << "[ms]\n" ;

  float cuda   = time_call([&]() { Addition_cuda(C, A, B, N); });
  for ( int i = 0; i < N; ++i ) assert( T[i] == 0 );
  std::cout << "cuda   = " << cuda  << "[ms]\n" ;
}

結果: ぜーんぜん速くならんです。
thread/CUDAのオーバヘッドが速くなった分を食ってしまう。
時間計算量 O(N) なのを頑張って速くしようと考えん方がむしろ幸せなんじゃないでしょか。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+4

vectorを使ってるので要素数を渡す必要は無いですね。size()で得ることが出来ます。
それと、引数は参照にすべきです。そうしないとvectorのコピーが発生するのでオーバーヘッドがかかります。
また、std::transformを使えばもう少し簡単に(forが不要)かけます。
高速かどうかは計ってないのでわかりません。

#include <algorithm>

using namespace std;

vector<int> Addition(vector<int>& v1, vector<int>& v2)
{
  vector<int> v3 = vector<int>(v1.size());
  transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), plus<int>());
  return v3;
}


上記は2つのvectorのサイズがv1のほうがサイズが大きい場合は例外が出ると思います。サイズが違ってたら空っぽのvectorを返すとか、小さいサイズを変換の元にするなどが必要かと思います。その辺は自分なりに工夫してください。
(boost.rangeを使えばtransformはもう少し簡潔に記述できます。)

戻り値を新たに返すのではなく、例えば引数のv1に返すという手もあります。そうすれば戻り値を返す時のコピーを防げます。

#include <algorithm>

using namespace std;

void Addition(vector<int>& v1, const vector<int>& v2)
{
  transform(v1.begin(), v1.end(), v2.begin(), v1.begin(), plus<int>());
}


ただ、これなら1行で書けるので関数にする必要もなくなるという考えもあります。

更に追記です。

vectorはデバッグビルドだとかなり速度が遅くなります(VC++ではそうです)。なので、リリースビルドすれば高速に動作する可能性があります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

こんにちは。

高速化ポイントとしては2つ思いつきますが、その両方とも最適化により自動的に高速化されてしまうだろうと思います。

  1. for文
    最適化されない場合、indexではなくてiteratorを使った方が、微妙に速くなるCPUもあると思います。

  2. return文
    文法通りに解釈するとこの返し方の場合、std::vector<int>のコピーが発生するので遅いのですが、最近のPC用コンパイラでは、RVO(Return Value Optimization)と言う最適化が働いてコピーされなくなると思います。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/02/09 17:26 編集

    PineMatsuさんが書かれている引数側の問題を見落としてました。
    確かに要素数は態々渡す必要はない筈です。またstd::vector<>の引数は参照かポインタにしないとこちらでコピーが発生します。それは痛いです。

    キャンセル

  • 2017/02/09 17:34

    C++11だったら範囲forを使う手もありますが速度的にイテレータとくらべてどうなんでしょうね?処理系に依存するのかな?

    キャンセル

  • 2017/02/09 18:04

    範囲ベースforも中身はイテレータです。ただ、毎回end()関数を呼ぶことになっているので、そこも最適化したい場合はイテレータの方が良いだろうと思います。

    キャンセル

  • 2017/02/09 18:06

    なるほど。終了条件をforの外に出してしまうということですね。ありがとうございます。

    キャンセル

+2

高速化の要点をまとめます。

  • vectorオブジェクトは参照渡しで
    PineMatsuさんが指摘するとおり、値渡しだと各要素のコピーが発生し、パフォーマンス低下の要因となります。もしvectorのサイズが100万だった場合100万件分のコピーが発生します。

  • vectorオブジェクトはreturnで返さない
    Chironianさんが書かれているように、場合によってはRVOの仕組みによりコピーが省かれることもありますが、常にRVOが働くとは限らないので、参照渡しの引数で結果を返した方がパフォーマンス的には有利です。

  • 「X = A + B」ではなく、「A += B」とする
    オブジェクトの作成と破棄には相応のコストがかかります。前者ではオブジェクトを1個余分に作る必要があるため、パフォーマンスに影響が出ます。場合によってはメモリへの負荷も気になります。

  • vectorの各要素のアクセスは、インデックスではなくイテレーターを使う
    組み込み配列のインデックス指定だと、今時のコンパイラーならかなりの最適化が期待できますが、vectorのインデックス指定だと最適化があまり効かず、毎回アドレス計算を行ってしまい、高速化の足かせになってしまいます。
    その点、イテレーターは中身はポインタなのでアドレス計算のコストが省けます。

  • いっそのこと生ポインタを使う
    とにかく最大限に高速化したいという場合は、最終的にはこれになります。
    vectorの要素はメモリ内で連続して配置されていることが保証されているので、イテレーターの代わりに生ポインタによる連続アクセスが可能です。生ポインタによるアクセスは最適化が効きやすいので高速化が期待できます。
    ただし、バッファオーバーランなどの問題を引き起こしやすいので、慎重にコードを書かないといけません。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

vectorの要素が100万くらいで、要素の型がintなら実際にわずかな時間しかかからないし、普通のプログラムであれば、全体に対してもほんの僅かなのでは?オイラの環境では、10^7要素で0.1秒です。究極の方法使って最大0.1秒節約。全体が10秒であれば、1%の節約。

profilerを使ってどこで時間がかかっているか調べましょう。要素の型がもっと複雑であれば、その型に応じた最適化があるかも です。

g++ -O3 使って実行時間が変わるか、openMPをloop部分に使って、

<p>#pragma omp parallel for
for (int i = 0; i < size; ++i)
</p>
g++ -fopenmp で試す。 というあたりからがいいのでは?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る