Pythonソート辞書は値によって不安定になることがありますか？ （Hackerrankで）

Question

私はPython 3の学習のためにHackerrankでいくつかの練習をしています。

タスクMost Commonには、英小文字のみを含む文字列が与えられ、その文字列の中で最も一般的な文字の上位3文字を見つける必要があります。

私はいくつかの質問に答えました。この問題の

私のソリューションは以下の通りです：私はローカル環境でこのコードをテストする場合

#!/bin/python3 
import sys 

if __name__ == "__main__": 
    s = input().strip() 
    ch_dict = {} 
    for ch in s: 
     if ch in ch_dict : ch_dict[ch] +=1 
     else: ch_dict[ch] = 1 

    result = sorted(ch_dict.items(),key=lambda d:d[1],reverse=True) 
    for i in result: 
     if i[1] != 1: 
      print(" ".join(map(str,i))) 

、それは働きます！

オンラインテストでは、がになる可能性があります。この入力の

：

b 3 
a 2 
c 2 

とも得ることができます：

aabbbccde 

私はこのような正しい答えを得る時々、多くの時間を提出

b 3 
c 2 
a 2 

それ並べ替えが不安定になる可能性がありますか？または、私のコードの問題は何ですか？ ORは何かHackerrank環境で間違っていますか？

出力を保証するにはどうすればよいですか？

Answer 1

Python辞書は、の順不同です。です。あなたはそれらの内容を反復処理する場合には、順序は実装に依存するので、あなたのリストことを考えると、任意の順序で項目が、時々('a', 2)ペアは、最初に来る、あなたが値だけによってあなたの項目をソートするWhy is the order in dictionaries and sets arbitrary?

を見ます時には('c', 2)ペアがあります。

注文を安定させたい場合は、キーをソートすることによって値間のつなぎを壊します。

あなたの挑戦の状態：出現回数の多い順に

ソート出力。
オカレンス数が同じ場合は、文字を昇順でソートします。

ますので、キーにより、その後、最初の値でソートとする必要があり、これら二つの間の方向はを異なります。

あなたは二回、ソートすることにより、または逆スコアでソートすることによって、これを達成することができます：

# Sort forward by key, to produce a stable order between keys 
by_key = sorted(ch_dict.items(), key=lambda d: d[0]) 
# Sort backward by value, ties are left in the original order, so by key 
result = sorted(by_key, key=lambda d: d[1], reverse=True) 

または1つのステップで：負数によってそのソート

sorted(ch_dict.items(), key=lambda d: (-d[1], d[0])) 

、キーを押して、逆にしないでください。

実際には、挑戦はの上位3つの文字のみを要求することに注意してください。チャレンジは巨大なインプットを使用しませんが、もしあれば、ソートの使用は実際には効率的ではありません。 すべてのキーと値のペアをソートする必要はなく、トップ3のみをソートする必要があります。あなたは効率的にあなたの任意の配列の上位Nを与えることができ、heap queueを使用することができます。

ソートが（N辞書の大きさ）O（NlogN）時間がかかり、heapqはO（NlogKを）かかり

import heapq 

result = heapq.nsmallest(3, ch_dict.items(), key=lambda d: (-d[1], d[0])) 

Nは同じ値であるが、Kは最上位項目の数である。ここでは3です。10.000項目の辞書の場合、ソートには約133kステップを要しますが、ヒープキューは16kステップしか必要としません。それはほぼ10倍速くなるでしょう！

Answer 2

問題はここにある：

key=lambda d:d[1] 

キーは両方の値を使用し、代わりに、第2の値を考慮します。

Answer 3

辞書は順序付けられていません。あなたは出力だけを値でソートしていますが、元のdictではキーの順序が保証されていないので、出力の各値の順序が変わる可能性があります。

あなたは両方に注文することにより、この問題を解決することができます

sorted(ch_dict.items(), key=lambda d: (d[1], d[0]), reverse=True) 

Answer 4

dict.itemsは、任意の順序で実施またはキー挿入順序などの詳細についてdependendを（キー、値）のペアを返すことができます。 sortedこれらのペアに対して、dict.itemsが返す順序で反復処理を行います。

決定的な出力が必要な場合は、値が同じになった場合にキー（辞書、キー）をキーで並べ替えるには、key=lambda d: (d[1], d[0])を使用します。

（ケースでは、Python 2、key=lambda key, value: (value, key)を使用しているがよりよい見える。）

Answer 5

sorted() is actually stableそれはあなたが提供されるキー機能により抽出されたものと同じキーで項目の順序を保持することに - この場合はキービーイング値。しかし、dictは順序付けされていないので、同じ値を持つ項目の保存された順序は未定義です。あなたが昇順のキーと値をソートしたいと思われるよう、

result = sorted(ch_dict.items(), key=lambda d: (-d[1], d[0])) 

注値を否定することで置き換え取り除か逆転引数を、：

ソリューションは(value, key)タプルでソートすることです降順で。

Answer 6

Hackerrank階層では、あなたはCollectionsセクションにあります。その解決策は、おそらくです：

#!/bin/python3 
import sys,collections 
if __name__ == "__main__": 
    s = 'abcdebbca' # input().strip() 
    res=collections.Counter(s).items(s) 
    sortres= sorted (res, key=(lambda x : (-x[1],x[0]))) 
    for k,v in sortres[:3] : print k,v 

も@Martijnピータースによって説明のような行sortres= sorted (res, key=(lambda x : (-x[1],x[0])))が必要です。

EDIT

問題は、dictからのみlists、setsとsorted安定性を使用して、他の答えが生じるので：

import sys 

if __name__ == "__main__": 
    s = raw_input().strip() 
    set_k, list_kv = set() , list() 
    for x in sorted(s): 
     if x not in set_k: 
      if set_k : list_kv.append((-count,val)) 
      set_k.add(x) 
      count , val = 0 , x 
     count+=1 
    for k,v in sorted(list_kv)[:3] : print v,-k