在 python 中生成大量序列时如何优化存储大小和性能？

Question

问题

对于给定的整数 n:

，我正在生成这种形式的所有可能序列

序列的长度为 n
对于某些 k < n，序列必须包含数字 n、n-1、n-2、...、n-k ≥ 1。数字可以重复。

例如，对于n = 3，可能的序列是：

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
2, 2, 3
2, 3, 2
3, 2, 2
2, 3, 3
3, 2, 3
3, 3, 2
3, 3, 3

换句话说，序列必须包含 n 和从 n 开始倒数的数字，没有任何跳跃，但没有特定的顺序并且允许重复。

给定n，这样的序列的数量由ordered Bell numbers或富比尼数给出，增长极快。

这是我用来生成序列的代码：

from sympy.utilities.iterables import multiset_permutations

def generate_sequences(n):
    sequences = []
    for unpermuted_seq in unpermuted_sequences(n,n):
        for permutation in multiset_permutations(unpermuted_seq):
            sequences.append(permutation)
    return sequences

def unpermuted_sequences(number,remaining_slots):
# Generates list of possible unpermuted sequences 
    if remaining_slots == 0:
        yield []
        return
    for repetitions in range(1, remaining_slots + 1):
        for sequence in unpermuted_sequences(number - 1, remaining_slots - repetitions):
            yield sequence + repetitions*[number]

问题

上面发布的代码按预期工作。我的两个主要问题如下：

存储： 对于我的特定应用程序，一旦选择了 n，我需要存储所有序列。我最终需要遍历列表并删除不满足特定条件的序列。然而，即使是小的 n（即 n > 8），也需要大量内存（GB 的数量级）。
生成时间： 我的代码需要很长时间来生成序列，即使是小的 n.

如何以优化存储和生成时间的方式生成序列？

Answer 1

我当然会将这些值存储为二进制。对于最多 16 个数字，您甚至可以使用半字节（4 位 - 使用一些位移）来存储每个值。所以对于 n=8 你会 'only' 需要 545835 * 4 字节 = ± 2MB -- 对于 n=10 ± 500MB.

为了更快地处理和写入文件，您可以使用memory mapping（预先计算所需的大小，创建该大小的文件，然后使用内存映射打开它）。

这样每个值都可以直接写入映射（即文件，就好像它是内存），这也将消除较慢的 sequences.append(permutation)。还要考虑只写你需要的序列，因为如果你想稍后删除它们，你将需要移动所有其他数据。

您还可以在文件中添加一个小的 header，其中包含一些值：n、k、number of sequences，二进制形式。

在 python 中生成大量序列时如何优化存储大小和性能？

How to optimise storage size and performance when generating a large list of sequences in python?

python

algorithm

optimization

performance

storage

问题

问题