質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.48%

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,034
退会済みユーザー

退会済みユーザー

プログラミング初学者です
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()の理解が浅いのでもしそれが関係しているなら解説いただけるとありがたいです
よろしくお願いします

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+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),)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/01 16:47

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

    キャンセル

  • 2017/11/01 16:49

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

    キャンセル

  • 2017/11/01 16:53

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.48%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る