itertools产品加速

发布于 2024-10-12 01:19:29 字数 351 浏览 13 评论 0原文

我使用 itertools.product 生成长度为 13 的 4 个元素的所有可能变体。4 和 13 可以是任意的，但事实上，我得到了 4^13 个结果，这是很多。我需要 Numpy 数组形式的结果，目前执行以下操作：

  c = it.product([1,-1,np.complex(0,1), np.complex(0,-1)], repeat=length)
  sendbuf = np.array(list(c))

在中间插入一些简单的分析代码，看起来第一行几乎是瞬时的，而转换为列表和 Numpy 数组大约需要 3 小时。有没有办法让它更快？这可能是我忽略的非常明显的事情。

谢谢！

原文

I use itertools.product to generate all possible variations of 4 elements of length 13. The 4 and 13 can be arbitrary, but as it is, I get 4^13 results, which is a lot. I need the result as a Numpy array and currently do the following:

  c = it.product([1,-1,np.complex(0,1), np.complex(0,-1)], repeat=length)
  sendbuf = np.array(list(c))

With some simple profiling code shoved in between, it looks like the first line is pretty much instantaneous, whereas the conversion to a list and then Numpy array takes about 3 hours.
Is there a way to make this quicker? It's probably something really obvious that I am overlooking.

Thanks!

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

琴流音 2024-10-19 01:19:29

NumPy 等价于 itertools.product() 是 numpy.indices()，但它只能得到 0,...,k 形式的范围的乘积-1：

numpy.rollaxis(numpy.indices((2, 3, 3)), 0, 4)
array([[[[0, 0, 0],
         [0, 0, 1],
         [0, 0, 2]],

        [[0, 1, 0],
         [0, 1, 1],
         [0, 1, 2]],

        [[0, 2, 0],
         [0, 2, 1],
         [0, 2, 2]]],


       [[[1, 0, 0],
         [1, 0, 1],
         [1, 0, 2]],

        [[1, 1, 0],
         [1, 1, 1],
         [1, 1, 2]],

        [[1, 2, 0],
         [1, 2, 1],
         [1, 2, 2]]]])

对于您的特殊情况，您可以使用

a = numpy.indices((4,)*13)
b = 1j ** numpy.rollaxis(a, 0, 14)

（这不会在 32 位系统上运行，因为数组太大。从我可以测试的大小推断，它应该在不到一分钟的时间内运行。）

EIDT ：顺便提一下：对 numpy.rollaxis() 的调用或多或少是装饰性的，以获得与 itertools.product() 相同的输出。如果您不关心索引的顺序，则可以忽略它（但只要您没有任何后续操作将数组转换为连续数组，它就很便宜。）

EDIT2：要获得确切的类似物，

numpy.array(list(itertools.product(some_list, repeat=some_length)))

您可以使用

numpy.array(some_list)[numpy.rollaxis(
    numpy.indices((len(some_list),) * some_length), 0, some_length + 1)
    .reshape(-1, some_length)]

This getting Completely unread -- justtell me是否应该进一步解释它:)

The NumPy equivalent of itertools.product() is numpy.indices(), but it will only get you the product of ranges of the form 0,...,k-1:

numpy.rollaxis(numpy.indices((2, 3, 3)), 0, 4)
array([[[[0, 0, 0],
         [0, 0, 1],
         [0, 0, 2]],

        [[0, 1, 0],
         [0, 1, 1],
         [0, 1, 2]],

        [[0, 2, 0],
         [0, 2, 1],
         [0, 2, 2]]],


       [[[1, 0, 0],
         [1, 0, 1],
         [1, 0, 2]],

        [[1, 1, 0],
         [1, 1, 1],
         [1, 1, 2]],

        [[1, 2, 0],
         [1, 2, 1],
         [1, 2, 2]]]])

For your special case, you can use

a = numpy.indices((4,)*13)
b = 1j ** numpy.rollaxis(a, 0, 14)

(This won't run on a 32 bit system, because the array is to large. Extrapolating from the size I can test, it should run in less than a minute though.)

EIDT: Just to mention it: the call to numpy.rollaxis() is more or less cosmetical, to get the same output as itertools.product(). If you don't care about the order of the indices, you can just omit it (but it is cheap anyway as long as you don't have any follow-up operations that would transform your array into a contiguous array.)

EDIT2: To get the exact analogue of

numpy.array(list(itertools.product(some_list, repeat=some_length)))

you can use

numpy.array(some_list)[numpy.rollaxis(
    numpy.indices((len(some_list),) * some_length), 0, some_length + 1)
    .reshape(-1, some_length)]

This got completely unreadable -- just tell me whether I should explain it any further :)

回复收藏 0 原文

寄居者 2024-10-19 01:19:29

第一行似乎是瞬时的，因为没有发生实际操作。生成器对象刚刚被构造，并且仅当您在操作发生时迭代它时。正如您所说，您会得到 4^13 = 67108864 数字，所有这些数字都会在您的 list 调用期间计算并提供。我看到 np.array 仅需要列表或元组，因此您可以尝试从迭代器中创建一个元组并将其传递给 np.array 以查看是否存在任何性能差异，并且它不会影响程序的整体性能。这只能通过尝试您的用例来确定，尽管有一些要点< /a> 表示元组稍微快一些。

要尝试使用元组，而不是列表，只需执行以下操作

sendbuf = np.array(tuple(c))

The first line seems instantaneous because no actual operation is taking place. A generator object is just constructed and only when you iterate through it as the operating taking place. As you said, you get 4^13 = 67108864 numbers, all these are computed and made available during your list call. I see that np.array takes only list or a tuple, so you could try creating a tuple out of your iterator and pass it to np.array to see if there is any performance difference and it does not affect the overall performance of your program. This can be determined only by trying for your usecase though there are some points which say tuple is slightly faster.

To try with a tuple, instead of list just do

sendbuf = np.array(tuple(c))

回复收藏 0 原文

流年已逝 2024-10-19 01:19:29

您可以通过跳过到列表的转换来加快速度：

numpy.fromiter(c, count=…)  # Using count also speeds things up, but it's optional

使用此函数，首先分配 NumPy 数组，然后逐个元素进行初始化，而无需执行列表构造的额外步骤。

PS：fromiter() 不处理 product() 返回的元组，因此目前这可能不是一个解决方案。如果 fromiter() 确实处理了 dtype=object，那么这应该可以工作。

PPS：正如 Joe Kington 指出的，这可以通过将元组放入结构化数组中来实现。然而，这似乎并不总是能提高速度。

You could speed things up by skipping the conversion to a list:

numpy.fromiter(c, count=…)  # Using count also speeds things up, but it's optional

With this function, the NumPy array is first allocated and then initialized element by element, without having to go through the additional step of a list construction.

PS: fromiter() does not handle the tuples returned by product(), so this might not be a solution, for now. If fromiter() did handle dtype=object, this should work, though.

PPS: As Joe Kington pointed out, this can be made to work by putting the tuples in a structured array. However, this does not appear to always give a speed up.

回复收藏 0 原文

自此以后，行同陌路 2024-10-19 01:19:29

让 numpy.meshgrid 完成所有工作：

length = 13
x = [1, -1, 1j, -1j]
mesh = numpy.meshgrid(*([x] * length))
result = numpy.vstack([y.flat for y in mesh]).T

在我的笔记本上大约需要 2 分钟

Let numpy.meshgrid do all the job:

length = 13
x = [1, -1, 1j, -1j]
mesh = numpy.meshgrid(*([x] * length))
result = numpy.vstack([y.flat for y in mesh]).T

on my notebook it takes ~2 minutes

回复收藏 0 原文

猫性小仙女 2024-10-19 01:19:29

您可能想尝试一种完全不同的方法：首先创建一个所需大小的空数组：

result = np.empty((4**length, length), dtype=complex)

然后使用 NumPy 的切片功能自己填充数组：

# Set up of the last "digit":
result[::4, length-1] = 1
result[1::4, length-1] = -1
result[2::4, length-1] = 1j
result[3::4, length-1] = -1j

您可以对其他“数字”（即 result[ 的元素）执行类似的操作:, 2]、结果[:, 1] 和结果[:, 0]）。整个事情当然可以放入一个迭代每个数字的循环中。

转置整个操作 (np.empty((length, 4**length)…)) 值得尝试，因为它可能会带来速度增益（通过更好地使用内存缓存）。

You might want to try a completely different approach: first create an empty array of the desired size:

result = np.empty((4**length, length), dtype=complex)

then use NumPy's slicing abilities to fill out the array yourself:

# Set up of the last "digit":
result[::4, length-1] = 1
result[1::4, length-1] = -1
result[2::4, length-1] = 1j
result[3::4, length-1] = -1j

You can do similar things for the other "digits" (i.e. the elements of result[:, 2], result[:, 1], and result[:, 0]). The whole thing could certainly be put in a loop that iterates over each digit.

Transposing the whole operation (np.empty((length, 4**length)…)) is worth trying, as it might bring a speed gain (through a better use of the memory cache).

回复收藏 0 原文

野心澎湃 2024-10-19 01:19:29

可能没有优化，但对 python 类型转换的依赖要少得多：

ints = [1,2,3,4]
repeat = 3

def prod(ints, repeat):
    w = repeat
    l = len(ints)
    h = l**repeat
    ints = np.array(ints)
    A = np.empty((h,w), dtype=int)
    rng = np.arange(h)
    for i in range(w):
        x = l**i
        idx = np.mod(rng,l*x)/x
        A[:,i] = ints[idx]
    return A

Probably not optimized but much less reliant on python type conversions:

ints = [1,2,3,4]
repeat = 3

def prod(ints, repeat):
    w = repeat
    l = len(ints)
    h = l**repeat
    ints = np.array(ints)
    A = np.empty((h,w), dtype=int)
    rng = np.arange(h)
    for i in range(w):
        x = l**i
        idx = np.mod(rng,l*x)/x
        A[:,i] = ints[idx]
    return A

回复收藏 0 原文

~没有更多了~