Return to Video

04ps-01 Finding the Mode

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

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

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

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS215 - Intro to Algorithms
Duration:
04:10

Japanese subtitles

Revisions Compare revisions