OrderedDict()と辞書型と要素の順番について

Question

プログラミング初学者です
https://www.hackerrank.com/challenges/most-commons/problem

この問題を解いていて

from collections import OrderedDict

user = sorted(input())
counter = OrderedDict()

for i in user:
	if i in counter:
		counter[i] += 1
	else:
		counter[i] = 1

n = 0
for k, v in sorted(counter.items(), key=lambda x:x[1], reverse=True):
	n += 1
	if n > 3:
		break
	else:
		print(k, v)

まずこのように解きました
forループの部分をCounter()に代えようと考え

from collections import Counter

user = sorted(input())
counter = Counter(user)

n = 0
for k, v in sorted(counter.items(), key=lambda x:x[1], reverse=True):
	n += 1
	if n > 3:
		break
	else:
		print(k, v)

とこのように変えたのですが、outputの順番が同じ回数のもの同士で変わってしまいます
何故順番が安定しないのか、また何故最初のコードは順番が固定されるのか
もし後者のコードの順序を固定させるにはどのような方法が考えられるのか
教えていただきたいです
正直OrderdDict()の理解が浅いのでもしそれが関係しているなら解説いただけるとありがたいです
よろしくお願いします

Answer 1

リンク先の問題を見る限り...

Output Format
Print the three most common characters along with their occurrence count each on a separate line.
Sort output in descending order of occurrence count.
If the occurrence count is the same, sort the characters in ascending order.

ここでのascendingとは、アルファベット順のことではないでしょうか？
そう解釈してよいのなら、辞書に要素を追加した順を意識する必要はないはずです。
Counter.most_commonで出現回数順に並び変え、その後にアルファベット順にソートすればよいかと。

from collections import Counter

counter = Counter(input())

for k, v in sorted(counter.most_common(), key=lambda x: x[0])[:3]:
    print(k, v)

動作テストはしていないので、何かバグがあるかもしれませんが。
追記：バグ、ありました。ちょっと修正します。

---

修正しました。結局Counter.most_commonは使ってないです。

from collections import Counter

counter = Counter(input())
for k, v in sorted(counter.items(), key=lambda x: (-x[1], x[0]))[:3]:
    print(k, v)

---

さらに改造しました。こっちの方がわかりやすい気もしますね。

from collections import Counter
from operator import itemgetter

counter_list = list(Counter(input()).items())
counter_list.sort(key=itemgetter(0))
counter_list.sort(key=itemgetter(1), reverse=True)

for k, v in counter_list[:3]:
    print(k, v)

順番が安定しない理由

Counterは要素の挿入順序を記憶しないからです。
引用元：Python標準ライブラリ - 8.3.2. Counter オブジェクト

class collections.Counter([iterable-or-mapping])
Counter はハッシュ可能なオブジェクトをカウントする dict のサブクラスです。これは、要素を辞書のキーとして保存し、そのカウントを辞書の値として保存する、順序付けされていないコレクションです。

一方、OrderedDictは要素の挿入順序を記憶します。
引用元：Python標準ライブラリ- 8.3.6. OrderedDict オブジェクト

class collections.OrderedDict([items])
通常の dict メソッドをサポートする、辞書のサブクラスのインスタンスを返します。 OrderedDict は、キーが最初に追加された順序を記憶します。新しい項目が既存の項目を上書きしても、元の挿入位置は変わらないままです。

このように、これらの用途は異なります。
なお、OrderedCounterたるクラスが実装例として紹介されています。

順序付き辞書と Counter クラスを組み合わせると、要素が最初に現れた順を記憶するカウンタができます:

class OrderedCounter(Counter, OrderedDict):
    'Counter that remembers the order elements are first encountered'

def __repr__(self):
    return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

def __reduce__(self):
    return self.__class__, (OrderedDict(self),)

Comments

[退会済みユーザー]

後からアルファベット順にソートしたら出現回数まで入れ替わってしまいませんか

[LouiS0616]

ですよね。実行するまで気付かなかった私がまぬけでした。
既に修正済みでるので、更新してご覧ください。

[退会済みユーザー]

回答ありがとうございます、これから読んで理解してベストアンサーにすると思います