たくさんの数字があります。各セットには10個の番号が含まれており、他のセットと5つ以上の番号（順序なし）が一致するすべてのセットを削除する必要があります。
例えば：
set 1: {12,14,222,998,1,89,43,22,7654,23}
set 2: {44,23,64,76,987,3,2345,443,431,88}
set 3: {998,22,7654,345,112,32,89,9842,31,23}
セット1とセット3の上の10個の数字の3つのセットを考えると、それらには5つの一致する数字があるため、重複と見なされます。したがって、この場合、セット3を削除します（セット1と同様と見なされるため）。
比較するセットが10000以上あり、これを非常に効率的に実行したいと思います。私はこれを裏返してきましたが、この比較を実行するための効率的な方法を考えることができません（これを1回のパスで実行するのは素晴らしいことです）。
何か案は？ありがとう！
マイク
このままでは、操作の結果が明確に定義されていないため、要件を再考する必要があります。たとえば、次のセットを使用します。
set 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
set 2: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
set 3: {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
最初に 1 と 2 を「重複」と見なしてセット 1 を削除すると、2 と 3 も「重複」となり、残りのセットは 1 つだけになります。しかし、代わりに最初にセット 2 を排除すると、1 と 3 は一致せず、2 セットが残ります。
これを完全な 10,000 セットに簡単に拡張できるため、比較して最初に除外するセットに応じて、1 つのセットのみが残るか、5,000 セットが残る可能性があります。それはあなたが望んでいることではないと思います。
数学的に言えば、あなたの問題は、等価クラスを見つけようとしているということですが、それらを定義するために使用する関係「類似性」は等価関係ではありません。具体的には、推移的ではありません。簡単に言えば、セット A がセット B に「類似」しており、セット B がセット C に「類似」している場合、定義は A が C にも「類似」していることを保証しないため、類似のセットを意味のある方法で削除することはできません。
効率的な実装について心配する前に、まずこの問題に対処するための要件を明確にする必要があります。推移的な類似性を定義する方法を見つけるか、すべてのセットを保持して比較 (または単一のセットごとに類似したセットのリスト) のみを使用します。
シグネチャー ツリーのもう 1 つの完璧な仕事です。繰り返しますが、それらを実装するライブラリがそこにないことに驚いています。書いたら教えてね。
上記の検索結果の最初の論文の要約から:
セットデータをビットマップ (署名) として表現し、それらを類似検索やその他の関連クエリタイプに適した階層インデックスに編成する方法を提案します。以前の手法とは対照的に、シグネチャ ツリーは動的であり、固定された定数に依存しません。合成データセットと実際のデータセットを使用した実験では、さまざまなデータ特性に対して堅牢であり、データベース サイズに対してスケーラブルであり、さまざまなクエリに対して効率的であることが示されています。
表示される可能性のある数字の範囲についてはあまり言いませんが、私には2つのアイデアがあります。
リストに表示される番号をそれを含むリストにマップし、それらのリストを交差させて、共通の番号が複数あるリストを見つける転置リスト。
番号を分割するか、「近い」番号の範囲にグループ化してから、それらの範囲に番号が表示されるリストを絞り込みます（絞り込みます）。管理可能な数のリストがある一致リストの範囲を減らし、リストを正確に比較できます。これは「近接」アプローチだと思います。
素敵で美しい方法はないと思います。x,y他のほとんどの回答では、ほとんどのペアを比較する必要がありますO(N^2)。あなたはそれをより速く行うことができます。
アルゴリズム: すべての 5 タプルの配列を保持します。新しい分割ごとに、可能なすべての 5 タプルに分割し、その配列に追加します。最後に、重複をソートしてチェックします。
C(10, 5) = 10*9*8*7*6/120 = 9*4*7長さ 10 のセットの長さ 5 の約 250 のサブセットがあります。したがって10^3、データよりも 1 倍大きいテーブルを保持していますが、操作のみを実行しO(250*N)ます。それは実際には機能するはずであり、理論的にも最善であると思います。
時間効率は高いがスペース効率は非常に低い方法でこれを行う方法があります。
私の数学が正しければ、10 個のセットからの 5 個の数字のすべての組み合わせは 10!(10-5)!5! になります。= 252 の組み合わせ× 10000 セット = 252 万の組み合わせ。5 つの整数のセットは 20 バイトを消費するため、すべてのセットのすべての組み合わせをHashSet. 5メガバイトしか使用しません（さらにオーバーヘッドがあり、少なくとも2〜3倍は吹き飛ばされます）。
これは高価に思えるかもしれませんが、代わりに、既存の 10000 に対して新しい 10 セットを個別にチェックする場合、252 セットの 5 を計算し、それらのいずれかがセットに含まれているかどうかを確認することである場合、それはより良いものでなければなりません。
基本的：
public class SetOf5 {
private final static HashSet<Integer> numbers;
private final int hashCode;
public SetOf5(int... numbers) {
if (numbers.length != 5) {
throw new IllegalArgumentException();
}
Set<Integer> set = new HashSet<Integer>();
hashCode = 19;
for (int i : numbers) {
set.add(i);
hashCode = 31 * i + hashCode;
}
this.numbers = Collections.unmodifiableSet(set);
}
// other constructors for passing in, say, an array of 5 or a Collectio of 5
// this is precalculated because it will be called a lot
public int hashCode() {
return numbers.hashCode();
}
public boolean equals(Object ob) {
if (!(ob instanceof SetOf5)) return false;
SetOf5 setOf5 = (SetOf5)ob;
return numbers.containsAll(setOf5.numbers);
}
}
あとは、次の 2 つのことを行うだけです。
HashSet<SetOf5>既存の 5 のすべてのタプルに対して を作成します。とアルゴリズムは次のようになります。10 個の数字の各セットについて、考えられるすべての 5 個のセットを作成し、それぞれがセット内にあるかどうかを確認します。そうである場合は、10 個のセットを拒否します。そうでない場合は、5 個のセットを「セットのセット」に追加します。それ以外の場合は続行します。
少なくとも 10 から 5 の数字の場合は、10000 セットを力ずくで比較するよりもはるかに安価であることがわかると思います。
セットのすべてのペアを比較する必要があるため、アルゴリズムは O(N^2) で、N はセットのサイズです。
比較ごとに、約 O(X+Y) を実行できます。ここで、X と Y は 2 つのセットのサイズであり、この場合はそれぞれ 10 であるため、一定です。ただし、これには事前にすべてのセットをソートする必要があるため、O(N*xlgx) に追加されます。この場合も xlgx は一定です。
セットがソートされているため、2 つのセットの線形比較アルゴリズムは非常に単純です。両方のセットを同時に反復できます。詳細については、c++ std::set_intersection を参照してください。
アルゴリズム全体は O(N^2) になり、10000 セットではかなり遅くなります。
2 つのデータ セットの間のピアソン係数を見つける必要があります。この方法により、プログラムは巨大なデータ セットに簡単に拡張できます。
データセットを取得し、各要素に署名を付けて並べ替えます。署名には、並べ替えによって、重複する可能性のある要素がグループ化されるというプロパティがあります。data_set[j] を data_set[j+1 ...] のアイテムと比較するとき、[j+1 ...] の最初の署名が重複チェックに失敗すると、i を進めます。この「隣接基準」により、これ以上調べる必要がないことが保証されます。これを超える要素は重複できません。
これにより、O(N^2) の比較が大幅に削減されます。どのくらいアルゴリズム アナリストに決定させるかを決定しますが、以下のコードは、単純な O(N^2) の 100m ではなく、約 400k の比較を行います。
署名は、要素をバケット化することから始まります。数値の範囲を N 個の等しいサイズのバケットに分割します: 1..k、k+1..2k、2k+1..3k、...特定のバケット。これにより、フォーム (0,0,0,1,3,0,0,...4,2) の初期署名が生成されます。
署名には、次のプロパティがあります。
sum(min(sig_a[i], sig_b[i]) for i in range(10)) >= 5
その場合、署名に関連付けられた要素に少なくとも 5 つの重複がある可能性があります。さらに、上記が成り立たない場合、要素に 5 つの重複を含めることはできません。これを「署名一致基準」と呼びましょう。
ただし、上記の署名による並べ替えには、上記の adjacency プロパティがありません。ただし、署名を 2 要素形式に変更すると、次のようになります。
(sum(sig[:-1]), sig[-1])
その場合、「署名一致基準」が保持されます。しかし、隣接基準は成り立つでしょうか？はい。その署名の合計は 10 です。列挙すると、次の可能な署名があります。
(0,10) (1, 9) (2, 8) (3, 7) (4, 6) (5, 5) (6, 4) (7, 3) (8, 2) (9, 1) (10,0)
(0,10) を (1,9) .. (10,0) と比較すると、署名テストが失敗すると、二度と真にならないことに注意してください。隣接基準が成り立ちます。さらに、その隣接基準は、「5」だけでなく、すべての正の値に適用されます。
それはいいことですが、署名を 2 つの大きなバケットに分割しても、必ずしも O(N^2) 検索が減るとは限りません。署名は過度に一般的です。sig[:-1] の署名を作成することで、この問題を解決します。
(sum(sig[:-1]), sig[-1]), (sum(sig[:-2]), sig[-2]), ...
等々。この署名はまだ隣接性を満たしていると思いますが、間違っている可能性があります。
私がしなかったいくつかの最適化があります: 署名は最初の値ではなく、各タプルの最後の値のみを必要としますが、並べ替えの手順を修正する必要があります。また、シグネチャの比較は、それ以上のスキャンが成功しないことが明らかになったときに早期に失敗して最適化される可能性があります。
# python 3.0
import random
# M number of elements, N size of each element
M = 10000
N = 10
# Bounds on the size of an element of each set
Vmin,Vmax = 0, (1 << 12)
# DupCount is number of identical numbers required for a duplicate
DupCount = 5
# R random number generator, same sequence each time through
R = random.Random()
R.seed(42)
# Create a data set of roughly the correct size
data_set = [list(s) for s in (set(R.randint(Vmin, Vmax) for n in range(N)) for m in range(M)) if len(s) == N]
# Adorn the data_set signatures and sort
def signature(element, width, n):
"Return a signature for the element"
def pearl(l, s):
def accrete(l, s, last, out):
if last == 0:
return out
r = l[last]
return accrete(l, s-r, last-1, out+[(s-r,r)])
return accrete(l, s, len(l)-1, [])
l = (n+1) * [0]
for i in element:
l[i // width] += 1
return pearl(l, len(element))
# O(n lg(n)) - with only 10k elements, lg(n) is a little over 13
adorned_data_set = sorted([signature(element, (Vmax-Vmin+1)//12, 12), element] for element in data_set)
# Count the number of possible intersections
def compare_signatures(sig_a, sig_b, n=DupCount):
"Return true if the signatures are compatible"
for ((head_a, tail_a), (head_b, tail_b)) in zip(sig_a, sig_b):
n -= min(tail_a, tail_b)
if n <= 0:
return True
return False
k = n = 0
for i, (sig_a, element_a) in enumerate(adorned_data_set):
if not element_a:
continue
for j in range(i+1, len(adorned_data_set)):
sig_b, element_b = adorned_data_set[j]
if not element_b:
continue
k += 1
if compare_signatures(sig_a, sig_b):
# here element_a and element_b would be compared for equality
# and the duplicate removed by adorned_data_set[j][1] = []
n += 1
else:
break
print("maximum of %d out of %d comparisons required" % (n,k))
NumberSet順序付けられていないセットを実装する (そしてints を列挙して数値を取得できる)クラスがあると仮定します。次に、次のデータ構造とアルゴリズムが必要です。
Map<int, Set<NumberSet>> numberSetsMap<Pair<NumberSet, NumberSet>, int> matchCountPair<X,Y>同じ X と Y を持つ各インスタンスに対して同じハッシュコードと等価性を返すキー オブジェクトです (それらがスワップされているかどうかに関係なく)追加/比較する各セットに対して、次の手順を実行します (疑似コード!!!):
for (int number: setToAdd) {
Set<NumberSet> numbers = numberSets.get(number);
if (numbers == null) {
numbers = new HashSet<NumberSet>();
numberSets.put(number, numbers);
} else {
for (NumberSet numberSet: numbers) {
Pair<NumberSet, NumberSet> pairKey = new Pair<NumberSet, NumberSet>(numberSet, setToAdd);
matchCount.put(pairKey, matchCount.get(pairKey)+1); // make sure to handle null as 0 here in real code ;)
}
}
numbers.add(number);
}
いつでもペアを調べることができ、カウントが 5 以上のそれぞれが重複を示します。
注: A が B の複製であり、B が C の複製であると見なされる場合、C は A の複製である必要はないため、セットを削除するのは悪い考えかもしれません。したがって、B を削除すると、 C を削除しないと、セットを追加する順序が重要になります。
HashSetクラスを使用したいようです。これによりO(1)、ルックアップ時間が得られ、ループが正しく行われた場合に非常に効率的な比較が可能になります。（ここではアルゴリズムについて説明していませんが、役立つ場合に備えてデータ構造を提案しているだけです。）