0

大きなオブジェクト間のすべてのペアワイズ距離を計算する必要があるアルゴリズムがあります(距離は真のメトリックであるためdist(a,b) == dist(b,a)、他のすべてのメトリック要件の中でも)。約 1000 個のオブジェクトがあるため、約 500,000 の距離を計算する必要があります。いくつかの問題があります:

  1. これらの 1000 個のオブジェクトはすべてシリアル化され、ディスク上の個別のファイルに格納されます。
  2. ディスクからそれらを読み取ることは、比較的些細な距離計算に比べて膨大な操作です。
  3. スワップしてからスラッシングしないと、それらすべてを同時にメモリに入れることはできません。一度に約500個のメモリに収まります。
  4. これは、以前のある時点でメモリを読み取って解放した後、ある時点でオブジェクトをメモリに再度読み取る必要があることを意味します。

ディスクからの読み取りがボトルネックであり、一度に半分以上を読み取ることができないことを考えると、これらのオブジェクトを読み取って解放し、読み取りの総数を最小限に抑えるアルゴリズムを考えられる人はいますか?

私は前半に読み、それらのペアごとの距離をすべて実行し、その記憶をすべて解放して後半を読み、次にそれらのペアごとの距離をすべて実行することを検討しました。この時点では、まだ前半のオブジェクトと後半のオブジェクト間の距離が必要ですが、どうすればよいかわかりません。また、いっぱいになると、現在のオブジェクトをランダムに選択して削除し、次のオブジェクトを読み取るキャッシュを持つことも検討しましたが、より良いオプションが必要だと感じています。LRU のようなものを検討しましたが、必要なオブジェクトが最後の計算で削除されたという動作につながる可能性があります。

全体として、私はちょっと立ち往生しています。何かアドバイス？

4

3 に答える 3

3

前半で点を積みます。ペアごとの距離を計算します。前半をメモリに保持し、後半のポイントを 1 つずつ読み込み、距離を計算します。後半全体を読み込み、ペアごとの距離を計算します。これはポイントあたり約 1.5 の読み取りであり、次のモデルではほぼ最適です。

モデルは、このタスクの構文的に正しいプログラムは、LOAD( i , j ) の形式の一連の命令であり、その意味はポイントiをメモリ位置jにロードすることです。ポイントのすべてのペアに対して、両方のポイントがメモリ内にある直後の命令が存在する場合、プログラムは正しいです。

正しいプログラムでは、すべてのポイントが少なくとも 1 回読み込まれることは明らかです。正確に 1000 のポイントと 500 の場所を想定すると、最初に読み込まれるポイントを支持して、少なくとも 500 のエビクションがあることになります。一般性を失うことなく、メモリ内でポイントが複製されることはないと仮定します。ポイントpが最初に読み込まれるポイントqのために削除された後、 pとqの間の距離を計算するためにpをリロードする必要があります。したがって、少なくとも 500 回のリロード、つまり少なくとも 1500 回のロードがあります。

于 2013-08-26T15:19:12.593 に答える
2

私の最初の考え（したがって、最良のものではないかもしれません）：

各 i について:

  • 250 の i 番目のグループを読み取ります。これらの間の距離を計算します。

  • 250 の残りのグループ j ごとに:

    • j 番目のグループを読み取ります。

    • i 番目と j 番目のグループのポイント間の距離を計算します。

    • グループ j を破棄します。

  • グループ i を破棄します。

したがって、次のグループを読むことになります。

i  j
1  2
   3
   4
2  3
   4
3  4
4

グループ 4 を読むだけでは意味がないことに気付くでしょう。3 番目 (または他のグループ) を読むときに距離を計算することができます。

(1+2+3+3)/4 = 2.25したがって、ポイントあたりの読み取りの平均で終了します。

于 2013-08-26T15:02:46.123 に答える