YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 04ps-01 Finding the Mode

This is a solution video for Udacity CS215 problem set 4, problem 4.

Find the mode of a list in time Theta(n).

Get Embed Code
3 Languages

Showing Revision 2 created 03/11/2014 by Fran Ontanaya.

  1. 問4はn個の数のリストからΘ(n)の時間内に
    最頻値を求める問題です

  2. やり方はいろいろあります
  3. ここで紹介するのは基本的に5通りの方法です
  4. バリエーションに富んでいます
  5. 最初に辞書を使います
  6. 辞書を反復させることで
  7. 最も頻繁に登場する要素を抜き出します
  8. ここで初期状態に戻します 以前になかった値なら
  9. キー/値を作り値を1とします
  10. 以前にあった値ならその値に1を加えます
  11. これを進めていくと最も頻出するものが分かります
  12. 値が以前の最頻値より高ければ
  13. 現在の最頻値をキー/値に設定し直します
  14. リストを1度ループし終わると
  15. モードか同じ回数登場した値が複数ある場合
    モード内の値のうち1つを取り出せます
  16. そしてそれを返します
  17. 他にも方法があります
  18. Pythonのデフォルトの辞書を使って
    コードを少し短くする手法です
  19. これを少し変えて最初にキーを見つけた時に
  20. int機能を用い
    それを初期値として値をゼロとします
  21. この方法でコードを少し減らすことができ
  22. その値がすでに存在したかどうかチェックできます
  23. ハッシュ表を1度見ればいいだけです
  24. このような場合でも値に1を加えることに変わりはなく
  25. 初出の場合はデフォルト辞書で
    値を0にし1を加えるので値は1となり
  26. 基本的には前回と同じ動きになります
  27. 他のコードも同様に
    最頻値を見つけたらそれを返します
  28. 他にはPythonの組み込み関数maxを
    使う方法があります
  29. 値に1を加える時にデフォルトを使います
  30. 順番に値を検索する代わりに
    最後に最頻値を見に行きます
  31. lambda関数でリストの値の頻出度を測り
  32. それをmaxキーに返します
  33. さらにコンパクトにもできます
  34. Pythonのset関数を使う方法です
  35. 初期値または初期リストを取り出し
    重複を取り除くようにセットします
  36. その後max関数を使います
  37. 1行で表す簡潔なコードも作れます
  38. max関数を使って1行にまとめてしまうのです
  39. 特定の好きな値を選んで初期リストにセットし
  40. lambda関数を使って
  41. 初期リストにこの値が
    何度出てきたかをカウントし
  42. その値を返すのです
  43. 講義でも説明したやり方です
  44. 1行で表されているのでとても分かりやすいのですが
  45. 他の方法より処理速度が遅くなってしまいます
  46. この方法はリストの中での繰り返し作業が多いためです
  47. 多分一番処理が速いのはこれでしょう
  48. フォーラムでもっと速い方法を考えついた人もいます
  49. アンソニー・ペースさんが考えた比較関数で
    テストをしてみました
  50. 試すのは楽しいです
  51. 同じ目的のための様々な異なる方法があります
  52. 辞書を使った簡潔な方法を考え出すのは有効です
  53. 確実にΘ(n)時間内に終了します