标签: python-itertools

在 python 中进行 itertools.combinations 计算多进程?

我正在使用这样的算法对小数数组进行一些计算:

fkn = Decimal('0')
for bits in itertools.combinations(decimals_array, elements_count):
    kxn = reduce(operator.mul, bits, Decimal('1'))
    fkn += kxn
Run Code Online (Sandbox Code Playgroud)

我正在使用 Python 3.4 x64。 小数的精度>300(这是必须的)。len(decimals_array) 大多数时候超过 40。 elements_count 大多数时候是 len(decimals_array)/2。

计算需要很长时间。我想让它们成为多进程,所以首先我考虑制作一个所有组合的数组,并将该数组的一部分发送到许多进程 - 但在制作这样的数组期间,我很快就得到了 MemoryError 异常。

现在我正在寻找更好的方法来使该代码多进程。

在多核上运行该算法的好方法是什么?

或者也许有更好(更快)的方法来进行此类计算?

预先感谢您的一些想法。

python combinations decimal multiprocessing python-itertools

5
推荐指数
1
解决办法
2265
查看次数

如何在Python中高效地获取总和为10或以下的所有组合

想象一下,您正尝试n=10在一定数量的区域(例如 )上分配一些固定资源(例如t=5)。我正在尝试有效地找出如何获得总和等于n或低于的所有组合。

例如10,0,0,0,0是好的,等等0,0,5,5,0,而3,3,3,3,3,3显然是错误的。

我到目前为止:

import itertools
t = 5
n = 10
r = [range(n+1)] * t
for x in itertools.product(*r): 
   if sum(x) <= n:          
       print x
Run Code Online (Sandbox Code Playgroud)

然而,这种蛮力方法的速度非常慢;一定会有更好的办法?

计时(1000 次迭代):

Default (itertools.product)           --- time: 40.90 s
falsetru recursion                    --- time:  3.63 s
Aaron Williams Algorithm (impl, Tony) --- time:  0.37 s
Run Code Online (Sandbox Code Playgroud)

python python-itertools

5
推荐指数
1
解决办法
3013
查看次数

如何在 python 中有效地多线程或多处理大型 itertools.combinations ?

目标(较大问题的最简单概述)

我正在迭代地搜索最接近大整数的幂和的列表。


我是多线程新手的一些背景。我的理解是,我当前的瓶颈可能可以通过多线程来缓解。但是,我不确定其他方法是否更适合进一步改进。

代码

from itertools import combinations
from math import log, ceil

num = 26115155829

pwr = {n**p:str(n)+'^'+str(p) for n in range(9999,1,-1) for p in range(2,ceil(log(num,n)))}
pk = tuple(sorted(pwr.keys()))

sum2 = [(abs(num-(a+b)),' + '.join((pwr[a],pwr[b]))) for a,b in combinations(pk,2) if abs(num-(a+b)) < 99999]
sum3 = [(abs(num-(a+b+c)),' + '.join((pwr[a],pwr[b],pwr[c]))) for a,b,c in combinations(pk,3) if abs(num-(a+b+c)) < 99999]
Run Code Online (Sandbox Code Playgroud)

_ 描述 _

num:大整数的示例(通常为 10 到 18 位长)
 pwr:可能的基数^指数幂对的字典理解;4 到 1 位 基数开始递减,以便用较小的基数表示覆盖重复项,功率限制为低于目标大整数
 sumN:到目标距离小于~100000的N次方总和的过滤列表理解


样本输出
>>> print(*sorted(sum2)[:100],sep='\n')

(57, '4774^2 + 2966^3')
(1052, …
Run Code Online (Sandbox Code Playgroud)

python performance multithreading combinations python-itertools

5
推荐指数
1
解决办法
1724
查看次数

与python中的重复组合,其中顺序很重要

来自 python 的文档:https : //docs.python.org/2/library/itertools.html#itertools.combinations

见组合_with_replacement:“#组合_与替换('ABC',2)--> AA AB AC BB BC CC”

我想使用相同的功能,附带生成“BA”、“CA”和“CB”的奖励。

python combinations combinatorics cartesian-product python-itertools

5
推荐指数
1
解决办法
3416
查看次数

将列表字典转换为键和值列表的有效方法

我有如下列表的字典(它可以超过1M个元素,也假设字典按键排序)

import scipy.sparse as sp
d = {0: [0,1], 1: [1,2,3], 
     2: [3,4,5], 3: [4,5,6], 
     4: [5,6,7], 5: [7], 
     6: [7,8,9]}
Run Code Online (Sandbox Code Playgroud)

我想知道什么是最有效的方式(大字典的最快方法)将其转换为行和列索引列表,如:

r_index = [0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 6, 6]
c_index = [0, 1, 1, 2, 3, 3, 4, 5, 4, 5, 6, 5, 6, 7, 7, 7, 8, 9]
Run Code Online (Sandbox Code Playgroud)

以下是我到目前为止的一些解决方案:

  1. 使用迭代

    row_ind = [k for k, v in d.iteritems() for _ in range(len(v))] # or d.items() in …
    Run Code Online (Sandbox Code Playgroud)

python dictionary python-itertools

5
推荐指数
1
解决办法
195
查看次数

如何使用python groupby()

当我尝试使用itertools.groupby对这样的数字列表进行分组时:

from itertools import groupby

a = [1, 2, 1, 3, 2, 1, 2, 3, 4, 5]

for key, value in groupby(a):
    print((len(list(value)), key), end=' ')
Run Code Online (Sandbox Code Playgroud)

输出是

(1, 1) (1, 2) (1, 1) (1, 3) (1, 2) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) 
Run Code Online (Sandbox Code Playgroud)

代替

(3, 1) (3, 2) (2, 3) (1, 4) (1, 5)
Run Code Online (Sandbox Code Playgroud)

为什么它不能正确分组相同的数字?

python python-itertools

5
推荐指数
1
解决办法
4969
查看次数

python 多个列表的组合

有没有任何Pythonic方法来生成多个列表之间的组合?(类似于笛卡尔积但更复杂)

例子:

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9]
# ...
# there are more than 3 lists
Run Code Online (Sandbox Code Playgroud)

预期输出:

1. [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
2. [(1, 4, 8), (2, 5, 7), (3, 6, 9)]
3. [(1, 4, 9), (2, 5, 7), (3, 6, 8)]
4. [(1, 5, 7), (2, 4, 8), (3, 6, 9)]
5. ...
Run Code Online (Sandbox Code Playgroud)

更新:

谢谢你这么快的回复~!!

为了澄清这个问题:

结果是列表a、b、c的笛卡尔积的所有非重复组合。

可以通过另一种丑陋的方法来完成:

1)生成笛卡尔积的完整列表

from itertools import product, combinations, …
Run Code Online (Sandbox Code Playgroud)

python algorithm combinations python-itertools

5
推荐指数
1
解决办法
4724
查看次数

在 Python 中使用 itertools/more-itertools 对多列列表的项目进行分组和组合

这段代码:

from itertools import groupby, count 
L = [38, 98, 110, 111, 112, 120, 121, 898] 
groups = groupby(L, key=lambda item, c=count():item-next(c))
tmp = [list(g) for k, g in groups]
Run Code Online (Sandbox Code Playgroud)

采用[38, 98, 110, 111, 112, 120, 121, 898],按连续数字对其进行分组,并将它们与最终输出合并:

['38', '98', '110,112', '120,121', '898']
Run Code Online (Sandbox Code Playgroud)

如何对具有多列的列表进行同样的操作,就像下面的列表一样,您可以按名称及其第二列值的连续性对它们进行分组,然后合并。

换句话说,这个数据:

L= [
['Italy','1','3']
['Italy','2','1'],
['Spain','4','2'],
['Spain','5','8'],
['Italy','3','10'],
['Spain','6','4'],
['France','5','3'],
['Spain','20','2']]
Run Code Online (Sandbox Code Playgroud)

应给出以下输出:

[['Italy','1-2-3','3-1-10'],
['France','5','3'],
['Spain','4-5-6','2-8-4'],
['Spain','20','2']]
Run Code Online (Sandbox Code Playgroud)

more-itertools应该更适合这项任务吗?

在 Python 中使用 itertools/more-itertools 对多列列表的项目进行分组和组合

python python-itertools

5
推荐指数
1
解决办法
1654
查看次数

加速 itertools 与 cython 的组合

我有以下代码可以使用 itertools 生成指定范围内的所有可能组合,但我无法通过使用 cython 代码来提高速度。原始代码是这样的:

from itertools import *

def x(e,f,g):
    a=[]        
    for c in combinations(range(e, f),g):
        d = list((c))
        a.append(d) 
Run Code Online (Sandbox Code Playgroud)

声明 cython 的类型后:

from itertools import *

cpdef x(int e,int f,int g):        
    cpdef tuple c
    cpdef list a
    cpdef list d

    a=[]        
    for c in combinations(range(e, f),g):    
        d = list((c))
        a.append(d)
Run Code Online (Sandbox Code Playgroud)

我将后者保存为test_cy.pyx并使用编译cythonize -a -i test_cy.pyx

编译后,我使用以下代码创建了一个新脚本并运行它:

import test_cy

test_cy.x(1,45,6) 
Run Code Online (Sandbox Code Playgroud)

我没有得到任何显着的速度提升,仍然花费了与原始脚本相同的时间,大约 10.8 秒。

我是否做错了什么,或者 itertools 已经如此优化以至于无法对其速度进行任何更大的改进?

python cython python-itertools

5
推荐指数
1
解决办法
1777
查看次数

Python中重复排列的数量?

Python中有没有计算重复排列数的函数?我知道使用 itertools 我可以生成它们,但我只想要一种更快的方法来进行计算并避免计算阶乘,我对生成所有可能的排列不感兴趣。

例:计算4个A、3个B、5个C可能组成的字符串。

分辨率= 12!/(4!3!5!)

或者在代码中:

from math import factorial
from functools import reduce
rep=[4,3,5]
result= factorial(sum(rep))//reduce(lambda x,y: x*y, map(factorial, rep))
Run Code Online (Sandbox Code Playgroud)

python python-itertools

5
推荐指数
0
解决办法
533
查看次数