Comment optimiser la taille et la performance du stockage lors de la génération d'une grande liste de séquences en python?

Question

problème

Je générant toutes les séquences possibles de cette forme, pour un entier n suivant:

• la séquence a une longueur n
• la séquence doit contenir les numéros n, n-1, n-2, ... , n-k ≥ 1 pour certains k < n. Les chiffres peuvent être répétés.

Par exemple, pour n = 3, les séquences possibles sont:

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 

En d'autres termes, la séquence doit contenir n et le nombre décompter de n sans sauts, mais sans ordre particulier et répétitions autorisées.

Étant donné n, le nombre de ces séquences est donné par les nombres ordered Bell numbers ou Fubini, qui se développent extrêmement rapidement.

Voici le code que j'utilise pour générer les séquences:

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] 

Questions

Le code affiché ci-dessus fonctionne comme prévu. Mes deux principales préoccupations sont les suivantes:

1. Stockage: Pour ma application particulière, une fois n est choisi, je dois stocker toutes les séquences. Je finirai par devoir parcourir la liste et supprimer les séquences qui ne satisfont pas à une condition particulière. Cependant, même pour un petit n (c'est-à-dire n > 8), beaucoup de mémoire est nécessaire (ordre des Go).

2. Temps de génération: Mon code prend beaucoup de temps à générer les séquences, même pour les petites n.

Comment puis-je générer les séquences de manière à optimiser le temps de stockage et de génération?

Answer 1

Je stockerais certainement ces valeurs comme binaires. Pour les numéros jusqu'à 16, vous pouvez même utiliser un quartet (4 bits - en utilisant un peu de décalage) pour stocker chaque valeur. Donc, pour n=8 vous auriez «seulement» besoin de 545835 * 4 octets = ± 2MB - pour n=10 ± 500MB.

Pour accélérer le traitement et l'écriture dans un fichier, vous pouvez utiliser memory mapping (calculez la taille requise à l'avant, créez un fichier de cette taille et ouvrez-le avec le mappage de la mémoire).

De cette manière, chaque valeur peut être écrite directement dans le mappage (c'est-à-dire le fichier, comme s'il s'agissait de mémoire), ce qui éliminerait également le sequences.append(permutation) plus lent. N'envisagez également d'écrire que les séquences dont vous avez besoin, car si vous souhaitez les supprimer plus tard, vous devrez déplacer toutes les autres données.Vous pouvez également ajouter un petit en-tête au fichier avec certaines valeurs: n, k, number of sequences, en binaire.