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

Question

问题

对于给定的整数 n，我正在生成这种形式的所有可能序列:

• 序列长度为n
• 序列必须包含数字 n , n-1 , n-2 , ... , n-k ≥ 1对于一些 k < n .数字可以重复。

例如，对于 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]

问题

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

1. 存储:对于我的特定应用程序，一次 n被选中，我需要存储所有的序列。我最终需要遍历列表并删除不满足特定条件的序列。然而，即使是小的 n (即 n > 8 )，需要大量内存(GB 数量级)。

2. 生成时间:我的代码需要很长时间才能生成序列，即使对于小的 n 也是如此。 .

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

Answer 1

我当然会将这些值存储为二进制。对于最多 16 个数字，您甚至可以使用半字节(4 位 - 使用一些位移)来存储每个值。因此，对于 n=8，您“仅”需要 545835 * 4 字节 = ± 2MB——对于 n=10 ± 500MB。

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

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

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