首页 文章

从非唯一的项目列表中获取独特的组合，更快？

提问于
浏览 次
1

首先，我能够做到，但我对速度不满意 .

我的问题是，有更好，更快的方法吗？

我有一个看起来像这样的项目列表：

[(1,2), (1,2), (4,3), (7,8)]

我需要获得所有独特的组合 . 例如，2个项目的独特组合将是：

[(1,2), (1,2)], [(1,2), (4,3)], [(1,2), (7,8)], [(4,3), (7,8)]

在使用itertools.combinations之后，由于重复，我获得了更多 . 例如，我得到每个包含（1,2）两次的列表 . 如果我创建了一组这些组合，我会获得独特的组合 . 当原始列表有80个元组并且我想要其中包含6个项目的组合时，会出现问题 . 获得该设置需要超过30秒 . 如果我能得到这个数字，我会非常高兴 .

我知道组合的数量很大，这就是为什么创建集合非常耗时的原因 . 但我仍然希望有一个库以某种方式优化了这个过程，加快了它的速度 .

值得注意的是，从我发现的所有组合中，我只测试了前10000个左右 . 因为在某些情况下，所有组合都可能因为太多而无法处理，所以我真的不想在它们上花太多时间，因为还有其他测试要做 .

这是我现在拥有的样本：

from itertools import combinations

ls = [list of random NON-unique sets (x,y)]
# ls = [(1,2), (1,2), (4,3), (7,8)]  # example
# in the second code snipped it is shown how I generate ls for testing

all_combos = combinations(ls, 6)
all_combos_set = set(all_combos)

for combo in all_combos_set:
  do_some_test_on(combo)

如果你想测试它..这是我用来测试不同方法的速度：

def main3():
    tries = 4
    elements_in_combo = 6
    rng = 90
    data = [0]*rng
    for tr in range(tries):
        for n in range(1, rng):
            quantity = 0
            name = (0,0)
            ls = []
            for i in range(n):
                if quantity == 0:
                    quantity = int(abs(gauss(0, 4)))
                    if quantity != 0:
                        quantity -= 1
                    name = (randint(1000,7000), randint(1000,7000))
                    ls.append(name)
                else:
                    quantity -= 1
                    ls.append(name)

            start_time = time.time()
            all_combos = combinations(ls, elements_in_combo)
            all_combos = set(all_combos)

            duration = time.time() - start_time
            data[n] += duration
            print(n, "random files take", duration, "seconds.")

            if duration > 30:
                break

    for i in range(rng):
        print("average duration for", i, "is", (data[i]/tries), "seconds.")
python python-3.x combinations

1 回答

  • 2

    最初提出的问题是“有更好，更快的方法吗？”实际上有两个问题：

    • 有更快的方法吗？

    • 还有更好的方法吗？

    我想缩小“有更快的方法吗？”这个问题的答案 . 至：

    有没有更快的方法从列表中删除重复项，如下所示：

    lstWithUniqueElements = list（set（lstWithDuplicates））

    ？

    据我所知，没有更快的方法......

    现在让我们更多地关注问题的第二部分（“有更好的方法吗？”） . 通常很难并且需要很多讨论才能回答这类问题，但在这里情况并非如此，因为问题的作者（引用）已经明确说明了更好的方法：

    我喜欢使用发电机功能 . itertools组合（）本身是一个可迭代的而不是列表或集合，所以如果我弄清楚如何产生那些非常棒的独特组合 .

    所以这是：

    def uniqueCombinations(lstList, comboSize): 
    from itertools import combinations
    lstList.sort()
    allCombos = combinations(lstList, comboSize)
    setUniqueCombos = set()
    for comboCandidate in allCombos:
        if comboCandidate in setUniqueCombos:
            continue
        yield comboCandidate
        setUniqueCombos.add(comboCandidate)

    而已 ...

    还有一件事可能值得一提 . 问题的作者选择获取唯一组合的方法，以防它们生成的列表不仅具有唯一性，而且具有相同值的多个元素在某些特殊情况下不起作用，如下所示：

    set(combinations(['a','a','b','a'], 2)) gives: {('a', 'b'), ('b', 'a'), ('a', 'a')}
uniqueCombinations(['a','a','b','a'],2) gives: {('a', 'b'), ('a', 'a')}

    在这两者之间有一个纯Python函数可用于stackoverflow，它比上面提供的更快更慢 . 怎么能更快更慢？有关详细信息，请参阅HERE .

    回复于

相关问题