高效算法：对元素进行成对比较

Question

高效算法：对元素进行成对比较

14

给定一个包含一些键值对的数组：

[
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

我想要找到这些对中的交集。交集意味着只保留那些可以被其他元素覆盖或是唯一的元素。例如，{'a': 1, 'b': 1, 'c': 1} 和 {'a': 1, 'b': 1, 'c': 2} 全部涵盖了 {'a': 1, 'b': 1}，而 {'a': 2, 'b': 2} 是唯一的。因此，在

[
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

在找到交集后，应该保留。

[
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

我尝试遍历所有对并与彼此比较以找到覆盖对，但时间复杂度等于O(n^2)。 有可能在线性时间内找到所有覆盖或独特的对吗？

这是我的代码示例（O(n^2)）:

public Set<Map<String, Integer>> find(Set<Map<String, Integer>> allPairs) {
  var results = new HashSet<Map<String, Integer>>();
  for (Map<String, Integer> stringToValue: allPairs) {
    results.add(stringToValue);
    var mapsToAdd = new HashSet<Map<String, Integer>>();
    var mapsToDelete = new HashSet<Map<String, Integer>>();
    for (Map<String, Integer> result : results) {
      var comparison = new MapComparison(stringToValue, result);
      if (comparison.isIntersected()) {
        mapsToAdd.add(comparison.max());
        mapsToDelete.add(comparison.min());
      }
    }
    results.removeAll(mapsToDelete);
    results.addAll(mapsToAdd);
  }
  return results;
}

其中MapComparison是：

public class MapComparison {

    private final Map<String, Integer> left;
    private final Map<String, Integer> right;
    private final ComparisonDecision decision;

    public MapComparison(Map<String, Integer> left, Map<String, Integer> right) {
        this.left = left;
        this.right = right;
        this.decision = makeDecision();
    }

    private ComparisonDecision makeDecision() {
        var inLeftOnly = new HashSet<>(left.entrySet());
        var inRightOnly = new HashSet<>(right.entrySet());

        inLeftOnly.removeAll(right.entrySet());
        inRightOnly.removeAll(left.entrySet());

        if (inLeftOnly.isEmpty() && inRightOnly.isEmpty()) {
            return EQUALS;
        } else if (inLeftOnly.isEmpty()) {
            return RIGHT_GREATER;
        } else if (inRightOnly.isEmpty()) {
            return LEFT_GREATER;
        } else {
            return NOT_COMPARABLE;
        }
    }

    public boolean isIntersected() {
        return Set.of(LEFT_GREATER, RIGHT_GREATER).contains(decision);
    }

    public boolean isEquals() {
        return Objects.equals(EQUALS, decision);
    }

    public Map<String, Integer> max() {
        if (!isIntersected()) {
            throw new IllegalStateException();
        }
        return LEFT_GREATER.equals(decision) ? left : right;
    }

    public Map<String, Integer> min() {
        if (!isIntersected()) {
            throw new IllegalStateException();
        }
        return LEFT_GREATER.equals(decision) ? right : left;
    }

    public enum ComparisonDecision {
        EQUALS,
        LEFT_GREATER,
        RIGHT_GREATER,
        NOT_COMPARABLE,

        ;
    }
}

- Andrei Levin

6

我不能确定这个任务可以在线性时间内完成，但如果你先对数据进行排序，可能可以在O(n*log(n))的时间复杂度内完成。 - Thomas

2

你正在尝试计算的子列表被称为多目标优化领域中的帕累托前沿。 - Stef

3

我想知道，如果将每个元素视为一个多项式（假设每个键值对都可以唯一哈希），是否可以通过多项式算术找到交点。元素中的每个键值对是第n阶系数。但是需要更清晰地了解问题集——例如{a:1, b:2}是否等同于{b:2, a:1}，以及{a:1, c:1, d:1, b:1}是否包含{a:1, b:1}。我建议您让输入集更全面些。 - user2711811

4

我觉得并查集可能是这个问题的一个近似解（至少是算法中的查找部分），时间复杂度为 O(log*(n))。可以从具有最少元素的集合开始，将它们用作“查找”算法的元素。我认为这会得出与@Thomas答案相同的时间复杂度。我认为无法再更快了，虽然这可能还有待商榷。不过我还是赞同这个问题，因为算法总是有趣的。编辑：根据https://cstheory.stackexchange.com/a/41388/62830的说法，不可能在O(n)内完成此操作。 - SirHawrk

2

我不了解Java，但是Python中Pareto前沿的快速计算的被接受答案可以在4秒内解决包含10,000个数组和每个数组15个键值的问题。这对你来说是否足够高效？ - Stef

显示剩余10条评论

2个回答

0

假设列表中的每个元素都是唯一的（一个元素是具有键值对的对象）。对于每个唯一的键值对，存储包含它的列表元素的集合。按照大小递增的顺序迭代元素。对于每个元素，通过查找包含它们的元素集合并将该集合与当前交集相交来搜索它的键值对。如果交集大小低于2（假定交集至少包含一个元素，即我们正在调查的元素），则提前退出。根据数据，我们可能可以为这些集合使用位集（每个位表示排序列表中映射元素的索引），这可以执行并行比较的交集。还取决于数据，交集可以显着减少搜索空间。

Python代码：

import collections

def f(lst):
  pairs_to_elements = collections.defaultdict(set)

  for i, element in enumerate(lst):
    for k, v in element.items():
      pairs_to_elements[(k, v)].add(i)

  lst_sorted_by_size = sorted(lst, key=lambda x: len(x))

  result = []

  for element in lst_sorted_by_size:
    pairs = list(element.items())
    intersection = pairs_to_elements[pairs[0]]
    is_contained = True

    for i in range(1, len(pairs)):
      intersection = intersection.intersection(pairs_to_elements[pairs[i]])
      if len(intersection) < 2:
        is_contained = False
        break

    if not is_contained:
      result.append(element)

  return result

输出：

lst = [
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

for element in f(lst):
  print(element)

"""
{'a': 2, 'b': 2}
{'a': 1, 'b': 1, 'c': 1}
{'a': 1, 'b': 1, 'c': 2}
{'a': 2, 'b': 1, 'c': 1}
{'a': 2, 'b': 1, 'c': 2}
"""

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kaya3 · Accepted Answer

这是一个算法，具体效果取决于数据的形状。为了简化问题，我们将输入行表示为集合而不是映射，因为本质上您只将那些映射视为一组对/条目的集合。如果集合像 [a1, b1] 等，则该问题等价。目标是制作一个线性时间算法，假设输入行的长度很短。假设 n 是输入行的数量，k 是行的最大长度；我们的假设是 k 远小于 n。

使用计数排序按长度对行进行排序。
为结果初始化一个空的 HashSet，其中集合成员将是行（您需要一个不可变的、可哈希的类来表示行）。
对于每一行：
- 从结果中删除行的幂集中的每个子集（如果存在）。
- 将该行添加到结果中。

由于行按长度排序，因此保证如果行 i 是行 j 的子集，则行 i 将在行 j 之前添加，并因此稍后从结果集中正确删除。一旦算法终止，结果集恰好包含不是任何其他输入行的子集的那些输入行。

计数排序的时间复杂度为O（n + k）。每个幂集的大小最多为2 ^k，幂集的每个成员的长度最大为k，因此每个 HashSet 操作的时间为O（k）。因此，其余算法的时间复杂度为O（2 ^k · kn），这支配了计数排序。

因此，如果我们将k视为常量，则总体时间复杂度为O（n）。如果不是，则当k 2 n时，此算法仍然渐近优于朴素的O（n ² · k）算法。

注意，朴素算法的时间复杂度为O（n ² · k），而不是O（n ²），因为两行之间的每个比较都需要O（k）时间。