performance - 与えられた各領域の最小値を見つけるための効率的な方法

Question

与えられた場合、 最初に2つの実数値関数を次のように定義します。

m(X)また、各マトリックスの値をX次のように定義します。

ここで、が与えられると、の多くの領域がありG、として示されます。ここで、の領域は、のいくつかの列といくつかの行からランダムに選択Gされたその部分行列によって形成されます。そして、私たちの問題は、可能な限り少ない操作を計算することです。ハッシュテーブルを作成したり、結果をより速く取得するために並べ替えたりするような方法はありますか？ありがとう！GG

========================

たとえば、の場合G={{1,2,3},{4,5,6},{7,8,9}}、

G_1 could be {{1,2},{7,8}}
G_2 could be {{1,3},{4,6},{7,9}}
G_3 could be {{5,6},{8,9}}

=======================

現在、それぞれG_iについて、を計算するためにmxn比較が必要ですm(G_i)。したがって、m(G_1),...,m(G_r)rxmxnの比較が必要です。しかし、私はそれに気付くことができG_i、G_jおそらく重複しているので、より効果的な他のアプローチがあるでしょう。どんなご注意もよろしくお願いします！

Answer 1

最小/最大タイプのデータが必要な回数に応じて、マトリックス値の間、つまり値の間の隙間に最小/最大情報を保持するマトリックスを考えることができます..したがって、あなたの例では G={{1 ,2,3},{4,5,6},{7,8,9}} サイズが ((mxn),(mxn),(mxn)) で、集合 C の値を持つ関係行列 R を定義します。 = {-1 = 未満、0 = 等しい、1 = より大きい}。

R には (n,1)、(n,2) ～ (n,9) の 9 つの関係ペアがあり、各値は C のメンバーであることに注意してください (n,n は定義されており、0 に等しくなります)。したがって、R[4,,) = (1,1,1,0,-1,-1,-1,-1,-1)。ここで、サブセット G_1 のいずれかを検討してください ..., サブセットのメンバーの位置関係を知ることで、R へのオフセットが得られます。これは、各 R(N,,) へのインデックスに解決され、比較なしで目的の関係情報を直接返します。

もちろん、R を構築するためのスペースと計算のオーバーヘッドが、必要になるたびに必要なものを計算するだけのコストを超えるかどうかを判断する必要があります。R 行列が主対角線に沿って反映されることや、"equals" を宣言して未満 (C は 2 つの値しか持たないことを意味する) と呼ぶことができるなど、特定の最適化が利用可能です。元の行列 G に応じて、行または列が並べ替えられていることがわかっている場合は、他の最適化を行うことができます。

また、一部のコンピューター (メインフレーム、スーパーコンピューターなど) はデータを RAM に列優先順で格納するため、データセットを格納して、転置された行と列を埋めて、列から列へのタイプの操作 (ベクトル計算) を実際に実行できるようにします。列を優先します。アーキテクチャを確認してください。