algorithm - 一定時間でスパーステーブルから行/列を削除する方法は?

Question

巨大なディメンションを持つ非常にまばらに満たされたテーブルがあります。

つまり、テーブルのインデックスは非常に大きくなる可能性がありますが、テーブル内の要素の数は非常に少なくなります。

そのためのデータ構造を考えています。

rows x cols行/列内のすべての要素を見つけるにはメモリと時間がかかりすぎるため、テーブルを除外しました。

代わりに、 と の 2 つのマップを使用することを考えrowsましcolsた。

見てみましょうrows。キーは行インデックスであり、キーの値kは、行にあるすべての要素の列番号のリストですk。

例 (1 はそこに要素が存在することを意味します):

0 1 0
1 0 1

このrowsマップになります：

0: [1]
1: [0, 2]

colsキーが列番号で、キーの値が columnkにあるすべての要素の行番号のリストである同様のマップを保持しますk。

kテーブル の行を削除したい場合は、次のようにします。del rows[k]

colsただし、これはマップから頂点を削除しません。一部の要素が削除されたすべての列を反復処理し、colsマップから各要素を削除する必要があります。

O(1)これを行う方法はありますか？

Answer 1

これにアプローチする非常に非正統的な方法は、行列をk =2のk d-treeとして実装することです。行または列と交差するすべてのセルにアクセスして、行または列を削除します。行列が正方形で、ゼロ以外のエントリがある場合、調べる必要があるセルの平均数は です。(私は Stackoverflow のいくつかの回答でその趣旨の証明を書きました - 必要に応じて調べることができます。)nsqrt(n)

非常によく似た方法で、四分木を使用できます。私がこれらの用語を理解している方法では、違いは、ノードが決定するのに対し、ノードが決定するのに対し、セル境界は事前に定義されており、x 範囲と y 範囲を常に半分にカットすることです (すべての非葉の 4 つの同一のサブセルに対して)。k d ツリー内の境界(すべての非リーフ内の 2 つの同一でないサブセル用)。

どちらのバージョンでも、このソリューションのパフォーマンスはスパース性に複雑に依存していると思います。まず第一に、行/列あたりのゼロ以外のエントリの平均数が 1 よりもはるかに少ないように、データが本当に非常にまばらである場合、このソリューションは提案したソリューションよりもはるかにメモリ効率が高くなりますが、おそらく少ないでしょう。時間効率が良い。ゼロ以外のエントリの数cがエントリの総数の一定の割合であり、行列がである場合、このソリューションはより効率的である可能性があります。このソリューションでは、1 つの列を削除するには、平均して行リストm * kを変更する必要があります。c*mこのような行リストごとに、列がある場所を見つけて、その後にあるすべてのエントリを 1 つ前に移動する必要があります。c*k/2 = O(k)これは、合計で、各行の平均エントリです。c^2*m*k/2 = O(m*k)オペレーション。n = c*m*kであるため、操作の平均合計数は になりますが、ここで提案されたソリューションのc*n/2 = O(n)場合になります。O(sqrt(n))同様に、行列がほぼ正方形であると仮定し、m*m各行/列f(m)に平均でゼロ以外のエントリがある (したがってn = f(m)*m) 場合、操作の数はO(f(m)^2)ソリューションとO(sqrt(m*f(m)))このソリューションの数になります。つまり、このソリューションは次の場合に優れていf(m) = ω(m^(1/3))ます。( は小文字の omegaであることに注意してください。基本的には、またはのように、f(m)よりも漸近的に速く成長することを意味します。)m^(1/3)sqrt(m)c*m

(私は、マップの各エントリがソリューションの配列であると想定していrowsました。リンクされたリストは、リスト内の正しい列を見つけるのに直線的な時間がかかるため、同じ複雑さをもたらします。各行と配列ではなく、自己均衡ツリーによって表される列 --行列が正方形からそれほど遠くないと仮定すると、O(log(k))各行および合計の操作を回避できます. それでも、このツリービジネスよりも優れているわけではありません.O(m * log(k)) = O(sqrt(n)*log(n))ただし、最高のパフォーマンスが本当に必要な場合は、実際にどのように機能するかを確認するために実装する価値があるかもしれません.)

マトリックスの密度が実際に定数cである場合、密なマトリックス表現もO(sqrt(n))操作を実行するため、漸近的な動作は同じになるはずです。定数係数は に依存するcため、どちらが速いかを確認するには、両方を実装する必要があります。

四分木解のパフォーマンスを向上させるには、ゼロ以外の値が小さな領域に集中しないようにする必要があります。分布は特に均一である必要はありません。極端に集中している必要はありません。

任意のエントリの追加と削除を頻繁に行うことも期待している場合、k d-tree をうまく実行するのは非常に難しいです。赤黒や AVL などのように、ツリー自体のバランスを取る簡単なスキームはないと思います。 1 次元ツリー。四分木はまだ機能する可能性があります。

Answer 2

あなたが持っているものを私が理解しているかどうか見てみましょう:

• 行ごとに、占有されている列のリストを維持します。
• 列ごとに、占有されている行のリストを維持します。
• これらの各構造は、単独で行列を記述するのに十分です。

行が削除されると、関連する列リストを空に設定するだけです。しかし、それを行う前に、このリストを使用して、そのリストの各列の行リストを処理してみませんか?

簡単な例。次のマトリックスがあるとします。

   1 0 0 0 1 1
   0 1 0 0 0 0
   0 1 1 0 0 0
   0 0 0 0 0 1

各行の列リストは次のようになります。

   0 [0, 4, 5]
   1 [1]
   2 [1, 2]
   3 [5]

各列の行リストは次のようになります。

   0 [1]
   1 [1, 2]
   2 [2]
   3 []
   4 [0]
   5 [0, 3]

行 2 を削除する場合は、その行に関連付けられた列リストを処理します。この場合は2 [1, 2]. これらは、行リストに「2」が含まれる列です。他の行リストを調べる必要はありません。

   Delete row 2: 
    -Column list for row 2: [1, 2]
    -Remove row '2' from the row list for columns 1 and 2
    -Set column list for row 2 to []
   done.

更新された列リストは次のとおりです。

   0 [0, 4, 5]
   1 [1]
   2 []   <== updated
   3 [5]

更新された行リストは次のとおりです。

   0 [1]
   1 [1]  <== updated
   2 []   <== updated
   3 []
   4 [0]
   5 [0, 3]

これらの構造は両方とも、次のマトリックスを表します。

   1 0 0 0 1 1
   0 1 0 0 0 0
   0 0 0 0 0 0
   0 0 0 0 0 1

これはあなたが探していた O(1) アルゴリズムではありませんが、非常にまばらな行列に対してはかなり効率的です。

Answer 3

ドナルド クヌースのダンシング リンク テクニックは常にあります。各行と列に沿って双方向にリンクされたリストを使用します。行または列を削除するには、行または列の要素数に比例して時間がかかります。

Answer 4

ええと、私は考え続けてきましたが、それは可能だと思います。

ただし、最初は O(1) である可能性があるため、ソリューションは理想的ではありませんが、O(n) 依存関係は依然として存在しますが、一部のタイプのデータと使用法では、定数時間に近いはずです。したがって、それが役立つかどうかによって異なります (変更の数は、配列の長さや操作の数と比較して劇的に少なくなります)。

削除するたびに、その変更を「変更リスト」に追加する必要があります。たとえば、行番号を削除します。10 であるため、リストに「10 より上、1 を引く」を追加します。

正しい行を数えるときは、「変更のリスト」から減算/加算する必要があります。

また、最後に使用された減算/加算された数と「変更のリスト」の数を含むもう1つの配列が必要なので、その行ですでにカウントされている変更をカウントする必要はありません。

最悪の場合、それはまだ「a*n」であり、a は何らかの定数です。

---

例 ：

rows, cols = 1000;
delete(row,573);
//=> list_of_changes[0] = {573, 'deleted'}
access_row(581)
//=> help_array[581] = {-1, 1}
//=> help_array.structure = {"how much add/subtract on this line", "number of changes used"}
access_row(581)
//=> look at the help_array[581] seeing having used 1 change,
//   the size of list_of_change is 1, so you don't have to count
//   anything, using the -1 value. - constant time

---

もちろん、row[0] を削除してからすべての 0..998 値にアクセスすると、O(n) になり、help_array の n 倍をカウントする必要があります。

Answer 5

マップの主な用途はcols、列からデータを取得するのではなく、列をできるだけ早くカウントすることであるため、tableネストされたマップを使用して を作成し、 と の代わりcolCountにマップを作成します。rowscols

このソリューションは O(1) よりも O(n) に近いですが、構造に無駄なサイクルが存在することはありませんrow x cols。

したがって、あなたの例では、次のtableようになります。

{0: {1:"Value"},
{1: {0:"Value", 2:"Value"}}

そしてcolCount、次のようになります。

#Each column in the example only had one value

{0:1,
 1:1,
 2:1}

次に、行を削除するときにk、行で見つかった各列のカウンターを減らすだけです。ここにいくつかの擬似コードがあります:

for key in table[k].keys()
    colCount[key] = colCount[key] - 1
delete table[k]