0

次のような 2 つのセットがあるとします。

A = { 1, 4, 7, 10, 11, 12 }
B = { a, b, x, y, z }

そして、A の要素が B の別の要素に関連しているかどうかを判断する関数があります。

bool isRelated(a, b)

関連する要素がない A と B から要素を削除したい。どうすればそれを達成できますか？1つの簡単な方法は次のとおりです。

forEach a in A:
    related = 0
    forEach b in B:
        if isRelated(a, b):
            related++
            break
    if related == 0 
        A.remove(a)

// then I need to do something similar for B

私には非常に非効率に見えます。より良い方法はありますか？もっと良い方法があるはずですか？

4

2 に答える 2

0

これは時間の複雑さにおいて非常に似ていますが、linqの怠惰のために、おそらくそれのいくつかを節約することができます。

これはC＃の例です：

var newA = A.Where(a=> B.Any(b=> IsRelated(a,b)).Select(a); //checks the desired condition
var newB = B.Where(b=> A.Any(a=> IsRelated(a,b)).Select(b);
A = newA;
B = newB'
于 2013-02-22T08:27:41.140 に答える
0

一般的に、これ以上の方法はありません。SQLデータベースは、結合句の特定の条件を認識すると最適化されます。この条件では、インデックス（既存のインデックス、またはオンザフライで構築されたデータ構造）を使用して、セット全体をスキャンせずにすべての一致を見つけることができます。考えられるすべての関係がインデックスと関係があるわけではありません。

Bのすべての要素がtrueをisRelated返す最初のループにレコードを保持できます。次に、まだ書き込まれていない2番目のループで、（現在は削減されている）セットをループする前にキャッシュをチェックできますA。これが整ったら、おそらく（最初のループで）常に最初Bから検索するとは限らないので、後でBキャッシュに入れる可能性が高くなります。

それ以外は、ここで提供される大きな節約はないと思います。

于 2013-02-22T08:27:41.570 に答える