파이썬에서 큰 시퀀스 목록을 생성 할 때 저장 공간 크기와 성능을 최적화하는 방법은 무엇입니까?

Question

문제

I 주어진 정수 n에 대해,이 형식의 모든 가능한 시퀀스를 생성하고 :

• 시퀀스 길이를 갖는다 n
• 번호를 포함해야 시퀀스 n, n-1, n-2, ... , 일부 k < n에 대해서는 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 또는 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의 경우, '585835 * 4 바이트 = ± 2MB - n=10 ± 500MB 만 필요합니다.

더 빠르게 처리하고 파일에 쓰려면, memory mapping (앞에 필요한 크기를 계산하고 그 크기의 파일을 만들고 메모리 매핑을 사용하여 열 수 있음)을 사용할 수 있습니다.

이렇게하면 모든 값을 매핑 (예 : 메모리 인 것처럼 파일)에 직접 쓸 수 있으므로 느린 sequences.append(permutation)을 제거 할 수 있습니다. 나중에 필요한 경우 다른 모든 데이터를 이동해야하기 때문에 필요한 시퀀스 만 작성하는 것도 고려하십시오.

작은 헤더를 n, k, number of sequences의 이진수로 파일에 추가 할 수도 있습니다.