6

私は現在、画像処理アルゴリズムを書いていますが、ある時点で、変換されたピクセルに関する統計情報を収集して、さらなる開発で従うべき方向についての洞察を得る必要がありました。収集する必要のある情報の種類は、次の形式でした。

key: RGB value
value: int

私がしたことは、変換された画像を開いて反復処理し、必要な値を保存しstd::unordered_mapて、次の署名を付けることでした。

typedef std::unordered_map<boost::gil::rgb8_pixel_t, unsigned int> pixel_map_t;

ループ内:

for(int y = 0; y < vi.height(); y++) {
    SrcView::x_iterator dst_it = src.row_begin(y);
    for(int x = 0; x < vi.width(); x++, hits++) {
        diff_map.insert(std::make_pair(dst_it[x], /* some uint32 */));
    }

また、カスタム ハッシュ関数も作成します (これは完璧なハッシュ関数でした: 256^2 x R + 256 x G + B- したがって、バケットとハッシュテーブルのレイアウトに関係なく (妥当な範囲で) 衝突は最小限に抑えられるはずです)。

私が気づいたのは、挿入が悲惨なほど遅いということでした! - 11 回目以降、挿入速度が約 100 倍に低下しました。大量の衝突がありました！画像内の複製された色の数は非常に少ないにもかかわらず。

その後、コード内で発生する可能性のある障害を排除したいと考え、unordered_mapint などのプリミティブ キー型で STL ハッシュ関数を使用してベンチマークを開始しました。

ベンチマークのコードは次のとおりです。

std::size_t hits = 0, colls = 0;
for(int y = 0; y < vi.height(); y++) {
    SrcView::x_iterator dst_it = src.row_begin(y);

    for(int x = 0; x < vi.width(); x++, hits++) {
        if(diff_map.find(x*y) != diff_map.cend())
            colls++;
        diff_map.insert(std::make_pair(x*y, 10));
    } 
    std::cout << y << "/" << vi.height() << " -> buckets: " 
              << diff_map.bucket_count() << "(" 
              << std::floor(diff_map.load_factor() * 100) 
              << "% load factor) [ " << colls << " collisions / " <<  hits << " hits ]"  << std::endl;
}

... そして、これが外側のループの最初の 20 回の反復の結果です (int 型のキーには STL のハッシュ関数のみを使用):

0/480 -> buckets: 8(12% load factor) [ 639 collisions / 640 hits ]
1/480 -> buckets: 4096(15% load factor) [ 640 collisions / 1280 hits ]
2/480 -> buckets: 4096(23% load factor) [ 960 collisions / 1920 hits ]
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions / 2560 hits ]
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions / 3200 hits ]
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions / 3840 hits ]
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions / 4480 hits ]
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions / 5120 hits ]
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions / 5760 hits ]
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions / 6400 hits ]
10/480 -> buckets: 4096(77% load factor) [ 3872 collisions / 7040 hits ]
11/480 -> buckets: 4096(85% load factor) [ 4161 collisions / 7680 hits ]
12/480 -> buckets: 4096(90% load factor) [ 4612 collisions / 8320 hits ]
13/480 -> buckets: 4096(99% load factor) [ 4901 collisions / 8960 hits ]
14/480 -> buckets: 32768(13% load factor) [ 5315 collisions / 9600 hits ]
15/480 -> buckets: 32768(13% load factor) [ 5719 collisions / 10240 hits ]
16/480 -> buckets: 32768(14% load factor) [ 6148 collisions / 10880 hits ]
17/480 -> buckets: 32768(15% load factor) [ 6420 collisions / 11520 hits ]
18/480 -> buckets: 32768(16% load factor) [ 6870 collisions / 12160 hits ]
19/480 -> buckets: 32768(17% load factor) [ 7135 collisions / 12800 hits ]
20/480 -> buckets: 32768(17% load factor) [ 7584 collisions / 13440 hits ]
21/480 -> buckets: 32768(18% load factor) [ 7993 collisions / 14080 hits ]

この場合、衝突の数が多すぎませんか? STL ライブラリは一般的に高品質ですが、単純な int ベースのキー サウンドには 639/640 と 640/1280 が少なくとも奇妙に聞こえます。それとも、私は何か間違ったことをしていますか？

そして、これは私のハッシュ関数でした（理論的には、衝突はまったくないはずですが、数値は非常に近かったです）：

template<> 
struct std::hash<boost::gil::rgb8_pixel_t> :
    public std::unary_function<const boost::gil::rgb8_pixel_t&, size_t>
{
    size_t operator()(const boost::gil::rgb8_pixel_t& key) const
    {
        size_t ret =  (static_cast<size_t>(key[0]) << 16) |
                      (static_cast<size_t>(key[1]) << 8) |
                      (static_cast<size_t>(key[2]));
        //return 256 * 256 * key[0] + 256 * key[1] + key[2];
        return ret;
    }
};

こ、これはもうおかしくない…

私はこのハッシュ関数を書きました：

template<> 
struct std::hash<int> :
    public std::unary_function<const int&, size_t>
{
    size_t operator()(const int& key) const
    {
        return 5;
    }
};

理論的には、衝突率は 100% になるはずですよね? しかし、結果は次のとおりです。

0/480 -> buckets: 8(12% load factor) [ 639 collisions / 640 hits ]
1/480 -> buckets: 4096(15% load factor) [ 640 collisions / 1280 hits ]
2/480 -> buckets: 4096(23% load factor) [ 960 collisions / 1920 hits ]
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions / 2560 hits ]
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions / 3200 hits ]
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions / 3840 hits ]
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions / 4480 hits ]
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions / 5120 hits ]
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions / 5760 hits ]
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions / 6400 hits ]

なんで？

環境: MSVS2010

4

5 に答える 5

8

colls衝突を測定していません。衝突を測定したい場合bは、範囲内の各バケットについて[0, bucket_count())を取得しbucket_size(b)ます。これにより、各バケットにアイテムがいくつあるかがわかります。バケットに 2 つ以上のアイテムがある場合、バケットにbucket_size(b) - 1衝突がありますb。

于 2011-05-22T00:46:19.220 に答える
4

ハッシュ スペースのサイズは 24 ビットです。衝突を 0 にするには、完全な場合はデータのサイズのハッシュ テーブルが必要であり、そうでない場合は 25 ～ 50% 大きくなります。私の推測では、ハッシュ テーブルをこれよりもはるかに小さくしたため、コンテナーがデータを再マッピングし、衝突が発生しています。

于 2011-05-22T00:19:38.540 に答える
1

あなたが正しく行っていることを理解していれば、画像内の多くのピクセルが同じ色を持ち、同じ色に対して diff_map.insert を繰り返し呼び出しているため、これらの衝突が発生している可能性があります(したがって、ハッシュ値の品質は無関係です) . 色のヒストグラムを計算するためにこれを行っている場合、おそらく「diff_map.insert(std::make_pair(dst_it[x], /* some uint32 */));」を実行したくないでしょう。のようなことをする

auto it = diff_map.find(dst_it[x]); if(それ == diff_map.end()) それ = 1; そうでなければ（それ->秒）++;

于 2011-05-22T00:18:13.263 に答える
0

カスタムハッシュ関数も作成します（これは完全なハッシュ関数でした：256 ^ 2 x R + 256 x G + B-したがって、バケットとハッシュテーブルのレイアウトに関係なく、衝突は最小限に抑えられます（妥当な範囲で）。

このハッシュ関数は良くありません。優れたハッシュ関数（バケットの数がわからない場合）は、ほぼ同一の入力に対して大幅に異なるハッシュ値を生成する必要があります。あなたの場合、これを達成するための非常に簡単な方法は、256個のランダムな32ビット値の3つのテーブルを使用することint32_t rand[3][256]ですrand[0][R] ^ rand[1][G] ^ rand[2][B]。これにより、値がバケット全体にランダムに分散され、同様の値をクラスター化する傾向がなくなります。これは、不明なバケットの理想的なハッシュ関数プロパティです。

ライブラリが提供するハッシュ関数に亀裂を入れることもできます。ハッシュ生成のランダムテーブルプロパティを改善することはできませんが、メモリルックアップが少ないために高速になるか、数学演算が多かれ少なかれ複雑になるため低速になる可能性があります。 -気になる場合はベンチマーク。

于 2011-05-22T04:32:39.413 に答える
0

値が等しくない場合でも、値が十分に近い場合があります。時系列や分散していない数値に適したハッシュ関数を見つけるのに苦労しました。unordered_map がバケットの数でハッシュ値に対して「%」(モジュロ) を実行すると、ほとんどの値が少数のバケットのみに収まる可能性があり (ハッシュ値が十分に分散されていない場合)、O(n) 検索につながります。 .

ハッシュ値が十分に分散していない場合は、std::map (RB ツリー) を使用して O(log n) を取得します。

于 2011-05-22T05:23:48.587 に答える