2

コサイン類似度を使用して、2 つのセット間で最も類似したベクトルをできるだけ早く見つけるコードに取り組んでいます。
コードは生の配列を (速度と単純さのために) 使用していますが、配列をさらに割り当てると、計算をまったく変更していなくても、プログラムが遅くなることに気付き始めました。問題を失うことなく、プログラムを次の100行ほどに絞り込むことができました。

#include <iostream>

const int vec_len = 192;

struct fvec
{
    int64_t nvec;
    short int **vecs;
#ifdef PARTIALS
    int **partials;
#endif
    fvec(int size)
    {
        nvec = size;
        vecs = new short int *[nvec];
#ifdef PARTIALS
        partials = new int *[nvec];
#endif
        for (int64_t i = 0; i < nvec; i++)
        {
            vecs[i] = new short int[vec_len];
#ifdef PARTIALS
            partials[i] = new int[vec_len];
#endif
            for (int j = 0; j < vec_len; j++) vecs[i][j] = std::rand() * 10000 / RAND_MAX;
        }
    }
    ~fvec()
    {
        for (int64_t i = 0; i < nvec; i++)
        {
            delete[] vecs[i];
#ifdef PARTIALS
            delete[] partials[i];
#endif
        }
        delete[] vecs;
#ifdef PARTIALS
        delete[] partials;
#endif
    }
};

struct cvec
{
    int nvec;
    short int **vecs;
#ifdef PARTIALS
    int **partials;
#endif
    cvec(int size)
    {
        nvec = size;
        vecs = new short int *[nvec];
#ifdef PARTIALS
        partials = new int *[nvec];
#endif
        for (int nv = 0; nv < nvec; nv++)
        {
            vecs[nv] = new short int[vec_len];
#ifdef PARTIALS
            partials[nv] = new int[vec_len];
#endif
            for (int i = 0; i < vec_len; i++) vecs[nv][i] = std::rand() * 10000 / RAND_MAX;
        }
    }
    ~cvec()
    {
        for (int i = 0; i < nvec; i++)
        {
            delete[] vecs[i];
#ifdef PARTIALS
            delete[] partials[i];
#endif
        }
        delete[] vecs;
#ifdef PARTIALS
        delete[] partials;
#endif
    }
};

float sim(short int *a, short int *b)
{
    int ret = 0;
    for (int i = 0; i < vec_len; i++) ret += a[i] * b[i];
    return ret;
}

void iterative_nn(const cvec &c, const fvec &f, int *results)
{
    for (int64_t i = 0; i < f.nvec; i++)
    {
        results[i] = 0;
        for (int j = 0; j < c.nvec; j++)
        {
            float tmpsim = sim(f.vecs[i], c.vecs[j]);
            if (tmpsim > results[i]) results[i] = tmpsim;
        }
        if (i % 100 == 0) std::cout << "\r" << i << std::flush;
    }
}

int main(int argc, char **argv)
{
    int res[5000];
    iterative_nn(cvec{100000}, fvec{5000}, res);
    std::cout << "\n";
    return 0;
}

ご覧のとおり、2 つの配列セットを保持する 2 つのクラスがあります。2 組の配列に (デモンストレーション用に) ランダムな値を入力し、すべての配列を反復処理してそれらの類似性を計算する関数を呼び出します。
コマンド ラインで -DPARTIALS を指定して各クラスに配列の別のセットを追加すると、プログラムの速度がコンピューターの約半分に低下します。明らかに、そのディレクティブによって影響を受ける行は、追加の配列の割り当てと割り当て解除だけです!
さらに、どちらの場合も 1 秒もかからない割り当てと割り当て解除に余分な時間が費やされることはありません。余分な時間は、ディレクティブの影響を受けない反復検索に費やされます (またはそう思っていました)。したがって、私の質問: プログラムを半分に遅くする余分な配列を単に割り当てることについてはどうですか?

上記のコードは、-std=c++11 でコンパイルする必要があります。-O3 を使用すると、約 25 秒または 1 分で実行されます。

4

1 に答える 1