如何在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或Fubini數字給出，其增長非常快。

這裏是我使用生成的序列代碼：

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)。還要考慮只寫你需要的序列，因爲如果你想在以後刪除它們，你需要移動所有其他數據。

您還可以使用一些值將一個小標題添加到文件中：n，k，number of sequences，二進制。