이 알고리즘을 최적화 할 수 있습니까?

일부 개체 목록을 가지고 있으며 다음 함수에서 반환 한 특정 번호에 대해 특정 순서로 반복하고 싶습니다. 다음은 해시 번호의 모듈을 기반으로 각 숫자를 목록 크기로 제거하고 시퀀스를 생성합니다.이 알고리즘을 최적화 할 수 있습니까?

def genSeq(hash,n): 
    l = range(n) 
    seq = [] 
    while l: 
     ind = hash % len(l) 
     seq.append(l[ind]) 
     del l[ind] 
    return seq

예 : 나는 쉽게 이해 파이썬에서 너 한테을 제시하고 [3, 1, 4, 2, 0]

genSeq (53,5)을 반환합니다. 나는 C++로 코딩해야한다. O (n^2)에서이 형식의 복잡성은 vector와 list 둘 다에 있습니다. (우리는 제거 또는 액세스 비용을 지불합니다). 이게 더 나아질 수 있을까요?

2011-12-29 balki

'l'에 적절한 데이터 구조를 사용하면 이론적으로'log n' 성능이 가능합니다. 그러면'n log n'이 될 것입니다. 그럼에도 불구하고 당신의'n'이 정말로 크지 않으면이 성능 향상이 크지 않을지 의심 스럽습니다. – Howard

그래서, n 개의 숫자를 섞어 버리시겠습니까? – Zonko

어느 데이터 구조가 적합할까요? 로그 n은 어떻게됩니까? – balki

skip list은 (는) O(log n) 액세스 및 제거를 제공합니다. 총 이동 시간은 O(n log n)입니다.

선형 솔루션이 있다고 생각하고 싶지만 나에게 아무런 문제가 없습니다.

2011-12-29 16:50:56

-1

벡터에서 삭제하지 말고 끝으로 바꾸고 채우기 포인터를 줄이십시오. 피셔 - 예이츠 셔플을 생각해보십시오.

2011-12-29 19:10:36 Svante

항목의 순서가 변경되므로 작동하지 않습니다. 당신은 그의 알고리즘을 사용하는 것과 같은 순서를 얻지 못할 것입니다. –

[범위 (len (l))의 해시 % (i + 1)] 은 factoradic의 숫자로 볼 수 있습니다. 순열과 factoradic 번호 사이에 bijection가 있습니다.

factoradic 번호에서 순열로의 매핑은 the top answer의 "색인 시퀀스를 사용하여 목록 허용"절에 설명되어 있습니다. 불행히도 제공된 알고리즘은 2 차입니다. 그러나 알고리즘 O (nlog (n))을 만들 데이터 구조를 가리키는 주석 기가 있습니다.

2011-12-30 06:53:13

답변