2017-01-05 6 views
3

私は以下の問題に取り組んでいます。私の質問は、私の現在の実装は、Pythonで並べ替えを使用している - 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) 

答えて

3

リンクで提示最高のアルゴリズムの時間複雑度はO(N + MログM)であるmは、入力文字列内の一意の文字数です。 メートルN複雑さはO(N)とみなすことができる時間に比べて小さい場合には、常に以下メートル(固定定数である)アルファベットの文字の総数ので、上述したように 。ヒープの代わりに周波数を並べ替えるのにソートアルゴリズムを使用すると、時間の複雑さに違いはありません。O(m log m)

すべてのループでindexiに初期化するため、実装には時間複雑度がO(nm)あることに注意してください。ここでは縮退ケースでのパフォーマンスの問題が固定され、短い比較を持っているCounter代わりのdefaultdictを使用して代替実装です:

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を使用していますnが与えられた反復可能な長さである場合のヒープソートへ。上記の結果からわかるように、実際の違いはありません。もちろん、結果はデー​​タのサイズと一意の文字の数に依存します。

+0

niemmiのアドバイスをいただきありがとうございました。実装を検討し、リンクから参照実装と比較してください。私はループの 'for(v、k)in enumerate(sorted_freq) 'では、同じ回数のループを繰り返すので、自分のコード時間の複雑さは' O(n + m log m) (あなたの答えでは、 'n'は文字列の長さを意味し、' m'は文字列中の一意の文字数を意味します)。私があなたのコメントを間違って読んだら、私を修正してください。 –

+0

ところで、あなたの考えを愛して、「カウンター」。 –

+1

@LinMa:はい、一意の文字の量である外側ループ「m回」をループします。しかし、最初の 'while'ループが何回実行されるかを考えてください。私があなたに与えた例では、最初の外側ループの 'index'は' 0'に初期化され、 'result' [0]は' 0'なので '0'回実行されます。 2回目の 'index'は' 1'であり、 'result' [1]は' 0'であるのでループは '0'回実行されます。 3番目のラウンドでは、 'index'が' 2'に初期化され、 'result'の最初の空きインデックスが' 20000'であるので、より興味深いものになります。第4ラウンド 'index'は' 3'に初期化され、最初の空きインデックスは '20001'に初期化されます。 – niemmi

関連する問題