힙을 사용하면 문자열 재정렬 성능이 향상됩니다.

Question

아래의 문제를 해결하고 코드를 게시했습니다. 내 질문에, 현재 구현 파이썬에서 정렬을 사용하고 있습니다 - sorted(sorted_freq, reverse=True). 나는 최대 힙 (http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distance-away/)을 사용하는 다른 구현을 언급했다. 나는 그들이 동일한 시간 복잡도가 O(n*log n)이라고 생각한다. (잘못 계산 한 경우, 언제든지 수정하자.) 그래서 정렬 이외의 힙 사용의 성능 측면에서 어떤 이점이 있는지 궁금하네요?

내 코드는 Python 2.7로 작성되었습니다.

문제점 : 문자열 양수 D 주어

. 주어진 문자열에서 일부 문자가 반복 될 수 있습니다. 동일한 문자열이 d이 서로 떨어져 있도록 주어진 문자열의 문자를 재정렬하십시오. 가능한 많은 재배치가있을 수 있으며 출력은 가능한 재배치 중 하나 여야합니다. 그러한 합의가 가능하지 않다면, 또한보고되어야한다. 예상 시간 복잡도는 O (n)입니다. 여기서 n은 입력 문자열의 길이입니다.

예 :

Input: "abb", d = 2 
Output: "bab" 

Input: "aacbbc", d = 3 
Output: "abcabc" 

Input: "geeksforgeeks", d = 3 
Output: egkegkesfesor 

Input: "aaa", d = 2 
Output: Cannot be rearranged 

소스 코드 :

from collections import defaultdict 
def rearrange(source, distance): 
    freq = defaultdict(int) 
    for c in source: 
     freq[c] += 1 
    sorted_freq = [] 
    for k,v in freq.items(): 
     sorted_freq.append((v,k)) 
    sorted_freq = sorted(sorted_freq, reverse=True) 
    result = [0] * len(source) 
    for i, (v,k) in enumerate(sorted_freq): 
     index = i 
     while index < len(result) and result[index] != 0: 
      index += 1 
     if index == len(result): 
      return None 
     count = v 
     while count > 0: 
      result[index] = k 
      index += distance 
      count -= 1 
      if index >= len(source) and count > 0: 
       return None 
    return result 

if __name__ == "__main__": 
    print rearrange('abb', 2) 
    print rearrange('aacbbc', 3) 
    print rearrange('geeksforgeeks', 3) 
    print rearrange('aaa', 2) 

Answer 1

링크에 제시된 최상의 알고리즘의 시간 복잡도 O (N + m 로그 m) 어디 m은 입력 문자열의 고유 한 문자 수입니다. 이 언급 한 바와 같이 m이 작 으면, 미터 항상 이하 (일정한 상수 임) 알파벳 문자의 총 수 있기 때문에, 시간 복잡도를 고려 될 수 N 비교 O (N) . O (m log m) 정렬 알고리즘을 사용하여 힙 대신 주파수를 정렬하면 시간 복잡도에 차이가 없습니다.

모든 루프에서 index을 i으로 초기화하므로 구현시 시간 복잡성이 O (nm)입니다.

이

from collections import Counter 

def rearrange2(s, dist): 
    start = 0 
    result = [None] * len(s) 
    for char, count in Counter(s).most_common(): 
     while result[start]: 
      start += 1 
     end = start + dist * (count - 1) + 1 
     if end > len(s): 
      return None 
     for i in xrange(start, end, dist): 
      result[i] = char 

    return ''.join(result) 


def rearrange3(s, dist): 
    start = 0 
    result = [None] * len(s) 
    for char, count in sorted(Counter(s).items(), key=lambda x: x[1], reverse=True): 
     while result[start]: 
      start += 1 
     end = start + dist * (count - 1) + 1 
     if end > len(s): 
      return None 
     for i in xrange(start, end, dist): 
      result[i] = char 

    return ''.join(result) 

if __name__ == '__main__': 
    import timeit 
    print timeit.timeit("rearrange(src,2)", setup="from __main__ import rearrange; src='a'*10000 + 'b'*10000 + 'cdefghijk'", number=100) 
    print timeit.timeit("rearrange2(src,2)", setup="from __main__ import rearrange2; src='a'*10000 + 'b'*10000 + 'cdefghijk'", number=100) 
    print timeit.timeit("rearrange3(src,2)", setup="from __main__ import rearrange3; src='a'*10000 + 'b'*10000 + 'cdefghijk'", number=100) 

출력 :

이

3.23630073078 
0.756645293244 
0.753287190129 

업데이트 :most_common 사용이 heapq.nlargestunder the hood이 동일 여기에서 문제 해결 및 퇴화 경우 성능의 짧은 비교가 대신 defaultdict의 Counter를 사용하여 대안 구현의 heapsort의 경우 n은 주어진 반복 가능한 길이입니다. 위의 결과에서 알 수 있듯이 실제 차이점은 없습니다. 물론 결과는 데이터의 크기와 고유 한 문자 수에 따라 다릅니다.