このようなデータ構造は存在しますか？

Question

私は、単純なリストと同じ速さでソートすることができ、以下の方法で要素を削除することができるデータ構造を探しています。

[{2,[1]}, 
{6,[2,1]}, 
{-4,[3,2,1]}, 
{-2,[4,3,2,1]}, 
{-4,[5,4,3,2,1]}, 
{4,[2]}, 
{-6,[3,2]}, 
{-4,[4,3,2]}, 
{-6,[5,4,3,2]}, 
{-10,[3]}, 
{18,[4,3]}, 
{-10,[5,4,3]}, 
{2,[4]}, 
{0,[5,4]}, 
{-2,[5]}] 

すなわちタプルを（これはErlangの構文である）を含むリスト：我々はこのようなリストを持っているとしましょう。各タプルは、を計算するために使用されるリストのメンバーを含むのと、のリストを含みます。私がリストでやってみたいことは次のとおりです。まず、ソートそれは、その後、は、リストの先頭、およびリストついにクリーンを取ります。 クリーン私は、頭の中にある要素を含むテールからすべての要素を削除することを意味します。つまり、頭と交差するテールのすべての要素は空ではありません。たとえば、ソート後の頭部は{18,[4,3]}です。次のステップは、4又は3を含むリストのすべての要素を削除して、すなわち、結果のリストはこの1つでなければならない：

[{6,[2,1]}, 
{4,[2]}, 
{2,[1]}, 
{-2,[5]}] 

プロセスは、新しいヘッドを取り、リスト全体が消費されるまで、再び洗浄することにより続きます。クリーンプロセスがオーダーを保持している場合、各反復のリストを使用する必要はありません。

ここでのボトルネックは、クリーンプロセスです。私は今よりも早く掃除をするための構造が必要です。

誰でも注文を失うことなく効率的にこれを行うことができる構造を知っていますか、少なくとも高速ソートを許可していますか？

Answer 1

はい、あなたはこれより速く得ることができますグラフアルゴリズムのためのgoogleする方が簡単だということかもしれません。あなたの問題は、リストとして2番目のタプルメンバーを表現していることです。それらを検索するのは面倒で非常に不必要です。それらはすべて5..1の連続した部分文字列です。単純にそれらをインデックスの組として表現することができます！

実際には、これらのインデックスタプルでリストを作成する必要はありません。右のそれぞれの組によって所定の位置に2次元配列でそれらを入れて、あなたはtriangular arrayを取得します：

h\l| 1 2 3 4 5 
---+---------------------- 
1 | 2 
2 | 6 2 
3 | -4 -6 -10 
4 | -2 -4 18 2 
5 | -4 -10 -10 0 -2 

代わりに二次元配列にデータを格納する、あなたが保存したい場合があります三角形の形状を考慮したインデックスマジックの単純な配列（プログラミング言語では長方形の2次元配列のみが可能な場合）が、複雑さには影響しません。

これは、リストをすばやくフィルタリングするために必要なすべての構造です。代わりに、最初の並べ替えと頭を得るための

、我々は単に最大値とそのインデックスを見つけるために、全体の構造を通って一度反復：

max_val = 18 
max = (4, 3) // the two indices 

フィルタは非常に簡単です。リスト（not (any (substring `contains`) selection)）またはタプル（isEmpty (intersect substring selection)）を使用しない場合は、それはちょうどsel.high < substring.low || sel.low > substring.highです。そして、私たちも全体の三角配列を反復処理する必要はありません、我々は、単純な反復はhigerと下の三角形ができます。今すぐ

[{ 2, (1,1)}, 
{ 6, (2,1)}, 
{ 4, (2,2)}, 
{-2, (5,5)}] 

：

result = [] 
for (i from 1 until max[1]) 
    for (j from i until max[1]) 
     result.push({array[j][i], (j,i)}) 
for (i from max[0] until 5) 
    for (j from i until 5) 
     result.push({array[j+1][i+1], (j+1,i+1)}) 

そして、あなたはあなたが必要とする要素を持っていますあなたはそれを並べ替えるだけで、あなたの結果が得られます。

---

実際、全体の複雑さは三角形配列では良くなりません。あなたはまだO(n)を得て、リストを作成して最大値を見つけることができません。すべての部分文字列インデックスタプルに対してテストすることによってO(n)にフィルタリングするか、またはO(|result|)でスマートな選択でフィルタリングするかは、これ以上重要ではありませんが、具体的には高速クリーニングステップについて質問しています。これは、データが大きい場合や、複数のクリーニングを行う必要がある場合には、現実的には有益な場合があります。
全体の複雑さに影響を与えるのは、入力全体ではなく、結果のみをソートすることです。

Answer 2

元のデータ構造が有向グラフの隣接関係リストとみなされるのだろうか？例えば;

{2,[1]}, 
{6,[2,1]} 

は、これらのノードとエッジがあることを意味します。

node 2 => node 1 
node 6 => node 2 
node 6 => node 1 

あなたの質問は次のように書き換えられます。

ノード4とノード3にリンクするノードが見つかった場合、ノード4とノード3を削除すると、グラフはどうなりますか？

1つのアプローチは、隣接行列を構築することです。すべてのエッジが1ビットであるN×Nビットマトリックス。あなたの問題は今になります。

は、4行のすべてのビットと4列のすべてのビットをゼロに設定します。

つまり、この削除されたノードの内外には何もリンクされません。

最適化として、長さNのビット配列を保持します。ノードが削除されていない場合、ビットが設定されます。ノード1、2、4、および5は「ライブ」と3と6ですが「削除」されているのであれば、配列は、削除するために今すぐ

[1,1,0,1,1,0] 

のように見える「4」、あなただけのビットをクリア。あなたが削除終わっ

[1,1,0,0,1,0] 

、隣接行列を経るが、0セットで行または列にエンコードされています任意のエッジを無視します。

完全な例。あなたはあなただけのマスクを変更する、ノード2を削除するには隣接行列

1 2 3 4 
1 0 0 0 0 # no entry for 1 
2 1 0 1 0 # 2, [1,3] 
3 1 0 0 0 # 3, [1] 
4 0 1 1 0 # 4, [2,3] 

とマスク

[1 1 1 1] 

だ

[ {2, [1,3]}, 
    {3, [1]}, 
    {4, [2,3]} ] 

を考えてみましょう。

今

[1 0 1 1] 

、擬似コードのような、構造を把握するために：

rows = [] 
for r in 1..4: 
    if mask[r] == false: 
    # this row was deleted 
    continue; 

    targets = [] 
    for c in 1..4: 
    if mask[c] == true && matrix[r,c]: 
     # this node wasn't deleted and was there before 
     targets.add(c) 

    if (!targets.empty): 
    rows.add({ r, targets}) 

隣接行列が大規模な取得することができます - それは結局、N×N個のビットだ - これは小さな、密行列の唯一のよりよい意志ではなく、大きい、疎なもの。これは素晴らしいではない場合

、あなたはそれが自分で発明するよりも:)