python 是否更快地从非唯一项目列表中获取唯一组合?

yxyvkwin  于 2022-12-10  发布在  Python
关注(0)|答案(2)|浏览(150)

首先,我能做到,但我对速度不满意。
我的问题是,有没有更好、更快的方法?
我有一个项目列表,如下所示:

[(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.")
laximzn5

laximzn51#

最初提出的问题“是否有更好、更快的方法来完成此操作?”实际上包含两个问题:

  • 有更快的路吗?
  • 有没有更好的办法?

我想将“是否有更快的方法”这一问题的答案缩小为:
是否有一种更快的方法从列表中删除重复项,如下所示:
列表(设置(具有重复项的列表))

据我所知,没有更快的方法...
现在让我们集中讨论问题的第二部分(“有更好的方法吗?”)。通常情况下,回答这类问题非常困难,需要进行大量讨论,但在这里情况并非如此,因为更好的方法是什么,问题(引文)的作者已经清楚地说明了:
我喜欢使用生成器函数,itertools combinations()本身是一个可迭代的函数,而不是一个列表或集合,所以如果我知道如何生成唯一的组合,那就太好了。
所以这里是:

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

5lhxktic

5lhxktic2#

我想这个答案是在OP需要它之后很好地出现的,但是我遇到了同样的问题,我想贡献我的解决方案。我不想在内存中存储任何组合,因为很容易看到这是如何出错的。
首先,this link提供了一个非常清楚的解释,说明了当元素重复时如何计算不同组合的数量,策略是创建带有替换的组合,然后丢弃不允许的组合。
例如,如果集合是(A,A,B,B),并且您想要3个元素的所有组合,则组合(A,A,A)和(B,B,B)不允许。因此,其思想是从原始集合中的唯一元素的列表中创建具有替换的所有可能的组合,这不占用任何查找的存储器,并且易于写入。
然而,当集合中有很多唯一元素时,这种策略是浪费的。将这个问题推向极端,集合(A,B,C)中唯一的3元素长的组合显然是(A,B,C),但这种策略会产生(A,A,A),(A,A,B),......为了缓解这个问题,我们可以注意到,唯一元素在有效组合中只能出现一次:对于唯一的元素,标准的itertools.combinations()就可以了。
因此,如果我们有一个唯一元素和重复元素的混合体,那么最终的组合可以分成两部分,一部分是通过itertools.combinations()从唯一元素生成的,另一部分是通过itertools.combinations_with_replacement()为重复元素生成的。
总而言之,这就是代码。它运行的速度取决于原始集合中重复的数量。最坏的情况是没有重复的情况:

import itertools
from collections import Counter

#Check if an element is repeated more times than allowed.
def comb_check(comb, original_dic):
    trouble = False
    if not comb:
        return(not trouble)
    comb_unique = set(comb)
    ratio = len(comb_unique)/len(comb)
    if ratio < 1:
       comb = Counter(comb)
       ks = (v for v in comb_unique)
       complete = False
       while (not trouble) and (not complete):
           try:
               k = next(ks)
               if comb[k] > 1:
                   if original_dic[k] < comb[k]: trouble = True
           except StopIteration:
               complete = True
    return(not trouble)

def generate_comb(elements,k):
    elements = Counter(elements)
    elements_unique = [k for k,v in elements.items() if v == 1]
    elements_other = [k for k, v in elements.items() if k not in elements_unique]
    max_repetition = sum([elements[k] for k in elements_other ])
    for n in range(0, min(k+1,len(elements_unique)+1)):
        if (n + max_repetition)>= k:
            for i in itertools.combinations(elements_unique, n):
                for j in itertools.combinations_with_replacement(elements_other, k-n):
                    if comb_check(j, elements):
                        (yield  j)

#All unique elements is the worst case when it comes to time
lst = [a for a in range(80)]
for k in generate_comb(lst, 6):
    pass
#It took my machine ~ 264 sec to run this

#Slightly better
lst = [a for a in range(40)] + [a for a in range(40)]
for k in generate_comb(lst, 6):
    pass
#It took my machine ~ 32 sec to run this

相关问题