Return to Video

18-09 Make Big Index

  • 0:00 - 0:04
    ループが何も行わない偽プログラムの実行時間を
  • 0:04 - 0:07
    測定する例をいくつか確認しました
  • 0:07 - 0:11
    注目すべきはインデックスコード化の実行時間です
  • 0:11 - 0:15
    次に行うのはインデックスするコードの実行時間を
  • 0:15 - 0:18
    テストできるプログラムを書くことです
  • 0:18 - 0:20
    よいテストにするため
    大きなインデックスを作る必要があります
  • 0:20 - 0:25
    手作業で行えば多くの時間と労力を要するでしょう
  • 0:25 - 0:28
    代わりに大きなインデックスを作成する
    関数を見つけます
  • 0:28 - 0:31
    使うのはsizeです
  • 0:31 - 0:34
    多数の言葉でインデックスを埋めます
  • 0:34 - 0:37
    多数のキーワードでインデックスをいっぱいにし
  • 0:37 - 0:40
    異なる言葉を作る必要があります
  • 0:40 - 0:43
    lettersと呼ばれるリストを作成しました
  • 0:43 - 0:47
    最初はすべてaになっています
  • 0:47 - 0:52
    sizeの数だけループを行い文字列を作成し続けます
  • 0:52 - 0:56
    次に文字列を追加しますが
    make_stringについてはあとで説明します
  • 0:56 - 1:00
    インデックスに文字列を追加しlettersを変更します
  • 1:00 - 1:06
    zになるまで文字を増やし続け1周します
  • 1:06 - 1:09
    このコードはすべて理解しなければならないほど
    重要ではありませんが
  • 1:09 - 1:10
    少し試してみましょう
  • 1:10 - 1:13
    このループが行っているのはすべての位置と
  • 1:13 - 1:16
    aの文字を処理しています
    8つの異なる要素です
  • 1:16 - 1:19
    今度はこれら8つの要素を
  • 1:19 - 1:23
    逆から処理していきます このループ処理は
  • 1:23 - 1:26
    要素数ー1からゼロでー1でステップします
  • 1:26 - 1:30
    各文字を調べていきます 文字がzより小さい場合は
  • 1:30 - 1:32
    増やすことができることを意味しています
  • 1:32 - 1:35
    このコードを使って増やします
    文字を数字に変換するコードについては
  • 1:35 - 1:38
    すぐにお話ししますが
    この式が行うことは次の文字を
  • 1:38 - 1:41
    取得することです なので文字が結果なら
  • 1:41 - 1:48
    これがbになったあと文字リストのその位置にある
    文字を次の文字に置き換えます
  • 1:48 - 1:53
    文字がzならアルファベットを終わらせたくないので
    代わりにaを設定します
  • 1:53 - 1:56
    そして次の文字を見つけるループに戻ります
  • 1:56 - 1:59
    zより小さなものを見つけたら停止します
  • 1:59 - 2:02
    1つの文字しか変える必要ありません
  • 2:02 - 2:07
    make_string関数をここに呼び出します
    この関数は配列を1つの文字列に変えます
  • 2:07 - 2:10
    pの要素を1つ1つ調べます
  • 2:10 - 2:13
    変わり続ける文字のこのリストです
  • 2:13 - 2:16
    そしてこのすべての文字を1つの文字列に連結させます
  • 2:16 - 2:19
    大きなインデックスが簡単に
    作成できるところがポイントです
  • 2:19 - 2:23
    異なるサイズのインデックスでテストできます
    Pythonインタプリタで試しましょう
  • 2:23 - 2:26
    make_big_indexを使用した時の結果がどうなるか
    お見せします
  • 2:26 - 2:29
    とても小さなものから開始します 渡す3つのものは
  • 2:29 - 2:32
    サイズです make_big_indexによって
  • 2:32 - 2:35
    3つのキーワードaaaaaaaaとaaaaaaabと
  • 2:35 - 2:40
    aaaaaaacからなるインデックスを得ました
    それぞれにfakeという名のURLがあります
  • 2:40 - 2:44
    もしインデックスに大きな値を与えれば
  • 2:44 - 2:49
    例えば100のキーワードを与えることにした場合
    サイズも100になります
  • 2:49 - 2:51
    大きなインデックスが得られます
  • 2:51 - 2:54
    最後の文字から2つ目が変わることが確認できます
  • 2:54 - 2:59
    それぞれの言葉が次の言葉と異なることを
    確実にするために行うのは
  • 2:59 - 3:03
    異なるサイズのインデックスにかかる
    実行時間を調べることです
  • 3:03 - 3:07
    大きなインデックスを作成しましょう
  • 3:07 - 3:11
    インデックスサイズを10,000にします
  • 3:11 - 3:13
    注目すべきはlookupの時間だということです
    これはよく使う操作です
  • 3:13 - 3:16
    大きなインデックスを作成する時間は計りません
  • 3:16 - 3:19
    lookupを行う時間を確認してみましょう
  • 3:19 - 3:22
    インデックス10,000のキーワードでlookupの
  • 3:22 - 3:27
    実行時間を計ります 言葉によって違いが生まれます
  • 3:27 - 3:29
    まず言葉udacityをlookupしてみましょう
  • 3:29 - 3:33
    これは悲しいことにインデックスにありません
  • 3:33 - 3:35
    udacityになるようにもっと大きな
  • 3:35 - 3:42
    インデックスが必要になります
    実行時間はここに示されます 0.0008秒です
  • 3:42 - 3:45
    まだ1ミリ秒に近くとても速いです
  • 3:45 - 3:48
    もっと大きなインデックスを作成しましょう
  • 3:48 - 3:53
    今回は100,000キーワードです
    作成するには少し長い時間がかかるでしょう
  • 3:53 - 3:57
    ここで気にすべきは作成する時間ではなく
    lookupを行う時間です
  • 3:57 - 3:59
    “約5分経過”
  • 3:59 - 4:03
    長い時間がかかるようにします
    どれくらいのエントリがあるか見てみましょう
  • 4:03 - 4:09
    インデックスの最後の要素を調べます
    aaaafrydになっています
  • 4:09 - 4:14
    どう発音するのか分かりませんが
    これを確認する別の方法は
  • 4:14 - 4:19
    まだ話していませんが負の数字を使うことで
    後ろからインデックスできます
  • 4:19 - 4:21
    インデックスとしてー1を使用すると
    リストの最後のエントリが得られます
  • 4:21 - 4:24
    ここで時間を計る実行を行います
  • 4:24 - 4:27
    10,000サイズのインデックスでlookupします
  • 4:27 - 4:31
    実行時間は前のものとよく似た値になりました
  • 4:31 - 4:34
    今回も1ミリ秒以下になります
  • 4:34 - 4:38
    それでは10,000インデックスではなく
  • 4:38 - 4:43
    100,000サイズのインデックスで
    同じlookupを試してみます
  • 4:43 - 4:45
    時間が10倍になったことが確認できます
  • 4:45 - 4:55
    つまり今回は約8.6ミリ秒です
    前回は0.9ミリ秒でした
  • 4:55 - 4:57
    行うたびにこれらの時間が
    少しずつ変わることに注意します
  • 4:57 - 5:00
    時間が変化する理由はたくさんあります
  • 5:00 - 5:03
    コンピュータは同時に他のことを
    たくさん実行しているので
  • 5:03 - 5:07
    プロセッサを完全に制御していませんし
  • 5:07 - 5:10
    毎回まったく同じものを実行している訳ではありません
  • 5:10 - 5:12
    他のプログラムが他のことを行っているからです
  • 5:12 - 5:14
    その他の理由にメモリがあります
  • 5:14 - 5:18
    メモリにある値をとても速く
    lookupすることもありますし
  • 5:18 - 5:21
    長い時間要することもあります
  • 5:21 - 5:24
    これについては詳しくお話ししません
  • 5:24 - 5:27
    重要なのは実行する度に時間は大体同じになることと
  • 5:27 - 5:31
    入力のサイズによって時間が決まるということです
  • 5:31 - 5:33
    入力tableのサイズの場合はテーブルのサイズを
  • 5:33 - 5:36
    100,000のエントリがあるものに増やすと
  • 5:36 - 5:40
    10,000のエントリがある時の10倍遅くなります
  • 5:40 - 5:43
    このような時間がどう機能するか
    小テストを行いましょう
タイトル:
18-09 Make Big Index
概説:

18-09 Make Big Index

more » « less
Video Language:
English
Team:
Udacity
プロジェクト:
CS101 - Intro to Computer Science
Duration:
05:45

Japanese subtitles

改訂