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返回isRelatedtrue 的元素。然后在尚未编写的第二个循环中，您可以在遍历（现在减少的） set 之前检查缓存A。一旦这到位，也许您可​​以（在第一个循环中）并不总是B从头开始搜索，以便为以后的元素B提供更好的机会进入缓存。

除此之外，我认为这里没有任何大的节省。

于 2013-02-22T08:27:41.570 回答