logo标签列表

高效算法扩展分组表格数据

pythonoptimizationnumpypandasscientific-computing
3
我正在寻找一个优化的Python工具来执行一个我一遍又一遍做的数组操作任务。如果这个工具已经存在，例如在numpy或pandas中，我宁愿实现它，而不是继续使用我自己的cythonized循环。
我有两个相同长度的数组A和B，存储一些关于分组数据的数据。数组A的第i个条目告诉我第i组的某些属性；数组B的第j个条目告诉我第j组有多少成员；A存储浮点数，B存储整数。因此，为了明确起见，如果A [5] = 100.4＆B [5] = 7，则第5组的质量等于100.4，并且该组有7个成员。
我的目标是创建一个新的浮点数数组C，其长度为B.sum()，这是上述数据集的扩展。因此，C [0：B [0]] = A [0]，C [B [0]：B [1]] = A [1]，依此类推。是否有一种优化的解决方案可以在现有库（如pandas）中执行此操作？
我的现有解决方案是初始化一个空数组C，然后对A的元素运行一个for循环，索引C的公共元素如上所述。我一直在用cython编写和编译for循环，以提高速度。但是，这个特定的操作是我的代码中最大的瓶颈，而且在处理表格数据时似乎是一个非常常见的数组操作，因此我想知道是否已经有一个高度优化的算法来执行它。
4个回答
5

Numpy中有repeat()方法可以实现这种类型的操作。

给定两个数组：

A = np.array([100.4,98.3,88.5])
B = np.array([7,3,10])
np.repeat(A,B)

会给你

array([ 100.4,  100.4,  100.4,  100.4,  100.4,  100.4,  100.4,   98.3,
         98.3,   98.3,   88.5,   88.5,   88.5,   88.5,   88.5,   88.5,
         88.5,   88.5,   88.5,   88.5])
1
这无疑是所有提议中最快的解决方案，对于一个有1e6个元素的数组，比列表推导式快约7倍。哇，我甚至不知道这种速度可能存在。谢谢，鲍勃！ - aph
很高兴听到这个消息。是的，numpy相当惊人。 - Bob Haffner
我非常惊喜。这个numpy解决方案正是我正在寻找的：只有一行代码，非常直观且意义完全自我表达，速度提高了约30倍。 - aph
1
@aph，你在这里和下面描述的测试结果非常有启示性。如果有一个自我回答可以收集你测试的数据，我会点赞的。 - senderle
同意@senderle的观点，看到测试会很好。 - Roman Pekar
2
In [58]: A = [100.4, 50.0]

In [59]: B = [7, 5]

In [60]: [A[i] for i in range(len(B)) for _ in range(B[i])]
Out[60]: [100.4, 100.4, 100.4, 100.4, 100.4, 100.4, 100.4, 50.0, 50.0, 50.0, 50.0, 50.0]
优雅的解决方案，inspectorG4dget，但是一个纯Python列表推导式肯定比Cython化的for循环慢，而我要优化的是性能，而不是代码行数。 - aph
@aph -- "一个纯Python的列表推导式肯定比Cython化的for循环慢。" 我对你评论中的“肯定”感到担忧，这让我觉得你没有进行过测试。但是我的经验是，对于某些应用程序，Python列表推导式可以非常快，接近C语言的速度。如果你还没有测试过这个解决方案，你应该去尝试一下。 - senderle
我刚刚测试了一下。对于单个属性A，你是正确的，列表推导确实接近cython的速度。然而，当我尝试在一个大数据集中实现这个解决方案时，其中我聚合的数据不仅仅是A，我的cython版本仍然比较快。所以，假设我有A1、A2和A3。那么，在B[i]的范围内，以下对inspectorG4dget解决方案的改进比我的cython方法慢得多：[(A1[i]，A2[i]，A3[i]) for i in range(len(B)) for _ in range(B[i])] - aph
1
@aph：如果您将zip（A1，A2，A3）作为预处理步骤呢？在Python3中，zip是一个迭代器，因此不应该需要额外的空间。 - inspectorG4dget
1
很棒的想法@inspectorG4dget - 将A-N数组完全压缩解决了我在纯Python中看到的随着N增加而产生的开销问题。看起来你的列表推导式和zip组合基本上与编译的cython一样快。干得好！ - aph
1

其中一种可能的方法是使用 itertools 函数创建迭代器：

>>> A = np.array([100.4,98.3,88.5])
>>> B = np.array([7,3,10])
>>>
>>> from itertools import chain, izip, repeat
>>> res = chain(*(repeat(*x) for x in izip(A,B)))
>>> list(res)
[100.4, 100.4, 100.4, 100.4, 100.4, 100.4, 100.4,
 98.3, 98.3, 98.3,
 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5]

更新。
>>> A1 = ['A', 3, [1,2]]
>>> A2 = [len, lambda x: x * 3, sum]
>>> B = [2, 3, 4]
>>>
>>> c = chain(*(repeat((a1, a2(a1)), b) for a1, a2, b in izip(A1, A2, B)))
>>> list(c)
[('A', 1), ('A', 1),
 (3, 9), (3, 9), (3, 9),
 ([1, 2], 3), ([1, 2], 3), ([1, 2], 3), ([1, 2], 3)]

这个解决方案的好处是你不需要实际存储所有这些元素，你可以直接从迭代器中获取。
你也可以使用 imap 而不是生成器：
>>> from itertools import chain, izip, repeat, imap
>>> A1 = ['A', 3, [1,2]]
>>> A2 = ['C', 4, 12]
>>> B = [2, 3, 4]
>>> for x in chain(*imap(repeat, izip(A1, A2), B)):
...     print x
... 
('A', 'C')
('A', 'C')
(3, 4)
(3, 4)
(3, 4)
([1, 2], 12)
([1, 2], 12)
([1, 2], 12)
([1, 2], 12)
和上面的问题一样：假设我希望该算法可扩展到多个组属性，例如 A1、A2、...、AN。您将如何使用itertools运行此循环以包括多个A数组的扩展？ - aph
@aph 好的，你可以使用任意多个A，我更新了答案。我只是为了展示实际数据而使用了list(c)，在你的应用程序中，你可以直接从迭代器中获取元素。 - Roman Pekar
1
对于 len(A)=1e6，我发现 itertools 的解决方案比列表理解要慢三倍左右。相比之下，itertools 的语法也难以阅读。如果有性能优势，我可以接受丑陋的语法，但对于这个问题似乎没有。 - aph
好知道，现在我也很感兴趣 :) 必须进行一些测试。 - Roman Pekar
0

好的，再次感谢大家的参与。这对我的工作来说是一个异常有用和有启发性的线程。我从假期回来，现在将发布我的测试结果，根据 senderle 的要求，请在任何提出的解决方案未最优编码时加入讨论。

首先，这是我的虚假数据，为了清晰起见而牺牲了冗长（欢迎为使多行格式更清晰提供建议）：

Ngrps=int(1.e6)
grp_prop1=np.random.random(Ngrps)
grp_prop2=np.random.random(Ngrps)
grp_prop3=np.random.random(Ngrps)
grp_prop4=np.random.random(Ngrps)
grp_prop5=np.random.random(Ngrps)
grp_prop6=np.random.random(Ngrps)
grp_occupation=np.random.random_integers(0,5,size=Ngrps)

现在让我们从我发现的最快算法开始，即Bob Haffner建议的numpy解决方案，在我的笔记本电脑上只需0.15秒。

mmbr_prop1=np.repeat(grp_prop1, grp_occupation)
mmbr_prop2=np.repeat(grp_prop2, grp_occupation)
mmbr_prop3=np.repeat(grp_prop3, grp_occupation)
mmbr_prop4=np.repeat(grp_prop4, grp_occupation)
mmbr_prop5=np.repeat(grp_prop5, grp_occupation)
mmbr_prop6=np.repeat(grp_prop6, grp_occupation)

下一个最快的是压缩列表推导式，由inspectorG4dget建议，用时1.21秒。
zipped_grps = zip(grp_prop1, grp_prop2, grp_prop3, grp_prop4, grp_prop5, grp_prop6)
zipped_mmbr_props = [zipped_grps[i] for i in range(len(grp_occupation)) for _ in range(grp_occupation[i])]

仅仅将组合压缩起来的行为就能提速超过2倍。当我不对组数据进行压缩时，列表推导解决方案需要2.71秒：

z=[(grp_prop1[i], grp_prop2[i], grp_prop3[i], grp_prop4[i], grp_prop5[i], grp_prop6[i]) for i in range(len(grp_occupation)) for _ in range(grp_occupation[i])]

Roman Pekar提出的itertools解决方案需要2.4秒：
zipped_grps = izip(grp_prop1, grp_prop2, grp_prop3, grp_prop4, grp_prop5, grp_prop6, grp_occupation)
c = chain(*(repeat((p1, p2, p3, p4, p5, p6), n) for p1, p2, p3, p4, p5, p6, n in zipped_grps))

最后，我原先编写的for循环需要4.8秒：

Ntot_mbrs = grp_occupation.sum()
data=np.zeros(Ntot_mbrs*6).reshape(6, Ntot_mbrs)
first_index=0
for i in range(len(grp_occupation)):
    data[0][first_index:first_index+grp_occupation[i]] = grp_prop1[i]
    data[1][first_index:first_index+grp_occupation[i]] = grp_prop2[i]
    data[2][first_index:first_index+grp_occupation[i]] = grp_prop3[i]
    data[3][first_index:first_index+grp_occupation[i]] = grp_prop4[i]
    data[4][first_index:first_index+grp_occupation[i]] = grp_prop5[i]
    data[5][first_index:first_index+grp_occupation[i]] = grp_prop6[i]
    first_index += grp_occupation[i]

因此，由于这个帖子中提出的建议，我将我的代码加速了30倍以上。非常感谢大家！
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接