ヒューマンリソースの緩やかな斜陽
これは単なるポエムなので、抽象的に記載する。
プロジェクト上、ヒューマンリソースを大事にしているのに、プロジェクトにまだ火種がくすぶっているのに、そこにいる人間はやめたいと思うのだろうか。
抜けていく人に雑談で聞いたときに、ここにいて自分に何の利点があるんだろうかみたいな話をされる。
確かに保守運用フェイズに入ってきたので「技術的にダイナミックな知見を得る」というよりは「既存を破壊せずいかに改善活動を行うのか」にシフトしている。
今いる人たちは前者に興味があって入ってきているので、炎上して結構つらい局面でも祭りとして、やりきるしかねえ!で乗り切ってきて、後者にシフトしたときに、優先順位付けた改修、前回実施内容に対する小さいPDCAを回すことに切り替わってきているので、緩やかにやる気を失ってしまうのかなと思う。
この緩やかさは気づいていたら髪が伸びていたみたいにふと感じて、その時にはもう積もりすぎてもう遅いのかもしれない。
じゃあどうしたらいいのかって、向き不向きがあるので必ずしもベストプラクティスがあるわけではないのかもしれない。
正直今の俺にはどうしたらいいのかよくわからない。
目先のことばかり考えている次期はもう終わりだよ。そろそろ、少し高い所から遠くを見る時がきたんだよ
こういう時にSHIROBAKOのロロの言葉を思い出す。
そういうプロジェクトにいる人たちは今、そういうときなのかもしれない。
RedshiftでのROW_NUMBER()関数のNULL挙動について
仕事していてRedshiftでのROW_NUMBER()関数のNULL挙動ってどうなんだっけと思ったので、メモしておく。
ORDER BYした時のソートでNULLがどうなるかって話。
docs.aws.amazon.com
テストデータについて
ROW_NUMBER()関数のテストとして、PARTITION BYの値はすべて同じ。
ORDER BYにNULLと値が混ざっている状態にした。
select * from schema.test_rownum;
結果
昇順ソート
select column1, column2, column3, ROW_NUMBER() OVER ( PARTITION BY column1 ORDER BY column3 ASC ) AS row_num from schema.test_rownum;
結果
NULLが値よりも上位でソートされるので、row_numberはnullが1となる。
降順ソート
select column1, column2, column3, ROW_NUMBER() OVER ( PARTITION BY column1 ORDER BY column3 DESC ) AS row_num from schema.test_rownum;
結果
値がNULLよりも上位でソートされるので、row_numberは値が1 となる。
こういう細かいところPostgreSQLやOracle DBで若干違ったりするから地味だけどちゃんと確認しないとなー。
何気なく使っているアルゴリズムを歴史から『世界でもっとも強力な9のアルゴリズム』を読んだ
足りない頭でアルゴリズム勉強している。
『なっとく! アルゴリズム』から続くアルゴリズムをもう少し勉強しようの一環で読んだ。
- 作者: ジョン・マコーミック,長尾高弘
- 出版社/メーカー: 日経BP社
- 発売日: 2012/07/19
- メディア: 単行本
- 購入: 15人 クリック: 437回
- この商品を含むブログ (20件) を見る
『なっとく! アルゴリズム』がソースコードが記載されていたり数式の記載があったりと比較的エンジニア向きに対し、この書籍は文章がメインとなる。
文章自体もイメージをつかんでもらうことが前提とした例メインなので読みにくいということはないと思う。
そのためソースコードが読めないという人でも、概要はつかめると思う。
文章で想像する分、ちょっと分からなくなるとそのままずるずると分からなくなるので、立ち止まったり戻ったりするので読むのには時間がかかった。
目次
第1章 イントロダクション―コンピュータが日常的に使っているすごいアイデアはどんなものか第2章 検索エンジンのインデクシング―世界最大の藁山から針を探す
第3章 ページランク―グーグルを起ち上げたテクノロジー
第4章 公開鍵暗号法―葉書で機密情報を書き送る
第5章 誤り訂正符号―自分で誤りを訂正するシステム
第6章 パターン認識―経験から学ぶ
第7章 データ圧縮―無から有を生み出す
第8章 データベース―一貫性の追求
第9章 デジタル署名―このソフトウェアを本当に書いたのは誰か
第10章 決定不能性とはなにか
第11章 まとめ―指先の天才はもっと賢くなるか
基本情報処理試験で見たことあるアルゴリズム
目次を見ると分かるように基本情報処理試験で出るような分野の内容が多い。改めて基本情報処理試験は世の中で使用されているものを網羅的に試験にしているのだなと感じた。
基本情報処理試験のような要素というよりは、試験で出てくるワードを処理の変遷から追いかける要素が強いので、これを読めば基本情報処理試験完璧だというものではないのは銘打っておく。
公開鍵暗号方式を絵具という超アナログな表現で説明していたのは、今まで解説しているサイトや書籍を見てきたがない要素だった。
そんなアナログな表現がくみ取れず、どういうことだ?みたいな感じに最初なってしまったのは、俺の読み取りが甘いからかなと思ってる。
RSAがロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの3人の名前からとられているなんて初めて知った。
個人的に面白かった点
個人的には5章の誤り訂正符号の解説はかなりわかりやすかった。ここも処理の変遷をベースにどう処理が移り変わっていくのかを記載しているんだけど、ここの例は分かりやすい。
この辺りよく分からないという人は読んでみて損はないかなと。
概論だった6章と難しすぎる10章
逆に6章のパターン認識については、広い範囲の話を1章でまとめようとしているので、概論で終わってしまったなあと思う。10章は正直読んでいてよくわからなかった。
文章表現向きじゃないテーマなのではと思いつつも、正直内容よくわからないのでもっと深掘りして読んでいく必要があると感じた。
20年ぶりの君との再会――感想「センチメンタルグラフティ20周年スペシャルイベント~再会~」
「センチメンタルグラフティ20周年スペシャルイベント~再会~」に行ってきた。
あなたに、会いたい…
— センチ20thプロジェクト (@senti_20th) January 22, 2018
このツイートから約1年後、2019年1月19日(土)に一ツ橋ホールにて開催。
まさか20年経ってセンチメンタルグラフティのイベントに参加できると思わなかったし、20年前のイベントはまだ中学生ということもあり参加できなかったので、今回一部・二部両方参加。
初のクラウドファンディングで支援したイベントで、クラウドファンディング開始寸前に開催側と出資側間の行き違いで揉めたり一時期は本当に開催されるかと思っていたけど、無事に開催れることになって一安心。
クラウドファンディングも9分で目標金額の1000万円を突破したりと、正直このコンテンツをなめていた。
それだけファンも数多かったゲームだったということなんだなって。
クラウドファンディングでグッズ買うと、当日の物販並ばなくて楽だなーと思っていたけど、結局物販に並んで買ってしまうというね。
夏穂クリアファイルはクラウドファンディングで、千恵と明日香は当日物販で購入。
千恵は裏の私服バージョンの姿が最高過ぎてな。
客層はほぼ男性(1割程度女性?)で年齢層はやっぱりというか30歳オーバーでいい歳したおっさんが多かった気がする
(俺含め)
このイベントに参加できないと次の機会はもうないと思ったので、一部二部両方参加できてよかった。
一部
一部はコミュニティイベントがメインで、生アフレコやミニゲームがメイン。各メンバーの生アフレコは各声優さんがチョイスした名シーンをそのままゲームの立ち絵、イベントスチルを使ったもの。
永倉えみりゅんの生アフレコ中にトラブルで映像(ゲーム画面)が止まって、さすがオカルト好きキャラのえみりゅん外さねえなwみたいな笑いがあったのが印象的。
全体的には終盤のイベントが多くて、これファン泣かしに来てんのか?って思った。
終盤イベントのアフレコでも山本るりかのイベントは本当いいよなあと改めて思った。
森井夏穂のアフレコがだんじり祭りイベで、確かに夏穂らしいイベントだよなあと思った。
夏穂の終盤イベントも是非聞いてみたかったなあ。
イラスト伝言ゲームは北チームとヤング南チームでの戦い。時間が短かったこともあってイラストがぐっだぐだで二人目から原型とどめていないという。
北チームの罰ゲームでの物まねは、有島モユさんの豊嶋真千子さんこと大御所の物まねが似すぎてた。
多部田さんと濱田さんのノープラン場つなぎはほぼ多部田さんの「当時は力及ばず申し訳ありません」で大爆笑だった。
20年前の発売延期の話を20年後に謝罪されるという。多分今日来た人はそれについて言及する人だれもいないと思うぞって感じだった。
クラウドファンディングで一時は開催すら危ぶまれていたけど、結局この人のぶっちゃけトークとこの人のいじられキャラの性格からかしゃーねーなみたいになったのが印象的。
ゲーム会社の社長なのに物販担当だったり、声優陣に囲まれて無理やり参加させられた感出す割には結構尽力されてたなあという印象。
二部
二部は歌がメイン。基本的には『センチメンタルグラフティ』の曲が多かった印象。スタンディングは空気読んでという感じだったし、客層が30台オーバーがメインなので立っている人はいなかったなという印象。
この手のイベントってオタ芸が少なからずあるんだけど、そういう人はおらず、特徴で古き良きアイドルのコールをしている人がいたなというのが特徴的だったなと。
開始1曲目2曲目が「LongDistanceCall」と「Two dreams」の名曲2曲で、もう俺的にクライマックス。
「日曜日の丘」でW妙子になる演出はすごくよかったなあと。W妙子の岡田純子さんと有島モユさんは一部から双子コーデで、それも併せてすごくいい演出だったなあと。
夏穂曲は「君がいれば…」だったんだけど、
夏穂曲の時、推しに恥かかせちゃいかんみたいな感じでコール頑張ったんだが、みんなこんな感じなんか?
— kawase (@snofra) January 19, 2019
ここが「アイカツ!」のライブと違うように感じた。
「アイカツ!」はアニメの曲だけどアーティストはアイドルだから、キャラクターよりアイドルメインと思っているからかなあ。
最後の「たった一つの思い出」は声優さんの挨拶もあって、周りのおじさんおばさんも結構泣いている人がいたなあ。
俺もこのゲームと知り合って、今日までの20年の合間を一気に振り返ってすごく感動できた。
最後に
センチ20thイベント一部二部参加したけど本当に楽しかった。
— kawase (@snofra) January 19, 2019
周りのおじさんみんな泣いてた。おじさんの俺も泣いてた。
みんなの愛と大御所の頑張りと圧(笑)でできたいいイベントだったなあ。
またヒロインのみんなに会えることを楽しみしてる。#センチメンタルグラフティ#センチ20th
20年という期間はすごく長かったけど、もうこんな日が来ることがないと思っていたので参加できてよかった。
いつまでも夏穂は俺の中で好きなキャラクターでい続けるんだろうなって、そう思えたイベントだったなあ。
イベント後にセンチメンタルグラフティ好きな人たちと飲みに行って、こんなにみんなセンチメンタルグラフティ好きなんだなって思たのであって本当にいい一日だった。
このイベントは声優の皆様が率先して動いてくださった結果、開催できたものだと思います。
20周年イベントやろうという話が出なければこのイベントが開催されることもなかったと思うと、皆20周年イベントに前向きであったことはありがたい限りです。
多部田さん含め声優さんに巻き込まれる形でサポートしてくださった皆様にも感謝したいと思います。
本当にありがとうございました。
分析モデルの説明責任の話
機械学習モデルの判断根拠の説明という、興味深い動画があったので、思ったことをメモしていく。
www.slideshare.net
結局俺がこうあってほしいでモデルが作られる
「この納得感のいくモデル」ひとつを探しだそうとしているから難しいという言葉は、一度機械学習を触ったことのある人にとって、1度は思ったことなのではないかなって思う。
特に俺はプロジェクト経験として機械学習をやっているわけではないので特に思う。
モデルって(裏のアルゴリズムはある程度分かっていても)調整のパラメータって経験やカンがすごい影響するものだなって思ってる。
じゃあその経験やカンで作って精度の高いものを客先にちゃんと報告したときに理解してもらえるのか。
客先がこうあるべきなモデルが作るべき
ビジネス的な側面を見ても「だからこうである」はちゃんと提示できていないと、意味があるのかないのか判断がつかないものができてしまう。精度が高ければ確かにいいんだけど、どんなに高くても客先が思っている「だからこうである」にヒットしなければ無駄な時間だけかけた不要なものになってしまう。
精度と信頼性をどれだけ担保するべきなのかって点を考えるべきなんだろうなって。
その担保をどうするのかって色々なアプローチのモデルを作って、モデル作成にあたっての経緯をどう説明(どのレベル感で説明)するか何だろうなと思う。
当然分析に明るい人が必ずしも客先にいるわけでもないので、そこのレベル感に合わせた説明資料は用意すべきで、その説明するためのアプローチがこの動画の内容だと思った。
多分この辺りをビジネスにしている人は当然の話をしているんだろうけど。
動画から知ったことのメモ
モデルへの信頼性
A→XXX→BとなったときにAを入れるとBになるのは分かる。だが、XXXがブラックボックスだと、どんなに精度が高くても、なぜAをinputにしたらBになるのかが分からない。
分からないとモデルへの信頼性が不足してしまう。何故かよく分からないものは使いたくないのは当然。
それが分からないと客先(ユーザ)側が、そのモデルに正当性があるのかどうか分からない。
日本及びEUでの機械学習への信頼性
〇日本の場合www.soumu.go.jp
http://www.soumu.go.jp/main_content/000564157.pdf
⑦~⑩が信頼の醸成にかかわるところ。
つまり利用者は人間の尊厳を保とう。自身をコントロールできるようにしましょう。
AIサービスプロバイダやビジネス利用者はサービスによって個人が不要に差別されないように留意しましょう。入出力は検証可能、結果の説明可能な状態とし利用者へ説明責任を果たせるように留意しましょう。
〇EUの場合
「EU一般データ保護規則」がそれにあたる。
ja.wikipedia.org
データ主体は、当該データ主体に関する法的効果をもたらすか又は当該データ主体に同様の重
大な影響をもたらすプロファイリングなどの自動化された取扱いのみに基づいた決定に服しな
い権利を持つ。
第 2 項(a)号及び(c)号で定める状況に関して、データ管理者は、データ主体の権利及び自由並
びに正当な利益を保護するための適切な対策を実施し、少なくとも管理者側で人を介在させる
権利、当該データ主体の観点を表明する権利、及び決定に同意する権利を実施するものとする。
https://www.jipdec.or.jp/archives/publications/J0005075
どのように説明するのか
代表的な説明法- 重要な特徴の提示
- 重要な学習データの提示
- 自然言語による説明
- モデルの可読化
説明は当然だが、「目の前にある課題」や「誰に向けた説明か」に対してどのように説明をすべきか考えなければならないので、100%これという回答はない。
説明のアプローチ
LIMEの応用例。
画像のうち何パーセントが判断に使われていたのか。判断に使用された部分だけを表示させる。(スライド27p)
influence応用例。
DataPoisoning。指定したテストデータにノイズ(何かちょっと変なデータを入れる)と結果が全然違ってくる。(スライド47p)
説明の手段で本当に欲しいのは
モデルひとつを作るって提示するパターンだと、相手が思っているデータの関連性にヒットしないかもしれない。そのためいくつか作ってユーザに委ねるというのが必要なのでは。それを各説明アプローチを使用しながら提示できるようにする必要がある。
『なっとく! アルゴリズム』メモその2 リスト・ハッシュテーブル
『なっとく! アルゴリズム』を読んで並行して勉強したことをメモしておく。
- 作者: アディティア・Y・バーガバ,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2017/02/01
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
配列
配列を定義するときはその配列の要素分メモリを確保することになる。
初心者に説明するときには大体箱で説明すると思う。
大きな箱1つの中に小さい箱5個あって、そこに必要なアイテムものを入れていくと思うんだけど最初に5個定義したときに、以下の問題が発生する。
- 箱が5個あるが入れるアイテムが1つしかない
- 箱が5個あるが入れるアイテムが6つある
- 箱が5個あってアイテムが3つある場合、1つめと2つ目の間にアイテムを挿入したい
- 箱が5個あってアイテムが3つある場合、2つ目の間を削除したい
メモリに確保する要素の数の問題
要素数に対して格納される値が少ない場合は、メモリに確保している数がもったいない。
要素数に対して格納される値が少ない場合は、要素数を増やす必要がある。
しかし、その増やすべき要素数が分からない場合その対応を何回すればいいのだという問題がある。
これの対応としては配列の動的確保である。
前述の例では、プログラム中で宣言時に指定した固定のサイズ(整数定数)による配列確保(静的確保)であった。実用的には、配列の要素数が宣言時(あるいはコンパイル時)に静的に決まってしまうよりも、実行時に要素数を動的に指定して配列を確保できたほうが便利なことがある。例えば、縦横任意サイズの画像ファイルから全画素情報を読み出す場合や、コンピュータで利用可能な空きメモリ量に合わせて扱うデータ個数上限を変化させたい場合などである。
配列 - Wikipedia
要素間のデータの検索
ビッグオー記法ではにあたる。
配列の特徴としてランダムアクセスが可能、つまりアイテム2を取ってくるにあたって直接アイテム1は確認しなくてよいということ。
要素間のデータの挿入・削除
ビッグオー記法ではにあたる。これはデータの挿入も削除も同じ。
箱にあるアイテムを追加したり削除したりするのはいつも一番最後とは限らない。アイテム間のアイテムを削除したいときもある。
その場合、間に入れたらその次の要素を隣にずらしていかなければらないが、それって単純にはできない。
アイテム2とアイテム3の間を挿入したいとして、単純検索としてアイテム1~アイテム5まで順番に確認していって、アイテム2とアイテム3の間にアイテム2´をセットしなければならんから。
リンクリスト
リンクリスト要素と要素でつながりがあるリストになる。
例えるのであれば食堂で、「食券を買う」→「食券を渡す」→「注文したものを受け取る」→「皿を返却する」のこの流れ。
リンクリストの特徴として、事前にメモリを確保しなくてもよい点、要素の追加削除が用意、シーケンシャルアクセスである。
データ同士が参照する関係
データ同士は独立している。配列でいう大きな箱に入っていない状態となる。
要素の順番ではなくて、データが次のデータ(ノード)へのリンクを含んでいるので、メモリを事前に確保する必要がない。
処理の終わりはNULLで定義される。
「食券を買う」(次は食券を渡す)→「食券を渡す」(次は注文したものを受け取る)→「注文したものを受け取る」(次は皿を返却する)→「皿を返却する」(NULL)
要素間のデータの検索
ビッグオー記法ではにあたる。
シーケンシャルアクセルが特徴と上で記載した通り、値を取ってきたい場合は先頭から順番に見ていかなければならない。
「食券を渡す」を取ってきたい場合、まずは食券を買わなければならない。
要素間のデータの挿入・削除
ビッグオー記法ではにあたる。これはデータの挿入も削除も同じ。
配列と違うのは単純検索としてアイテム1~アイテム5まで順番に確認する必要がないという点。
食券を渡した後「水を汲む」という動作を入れる場合、
「食券を買う」(次は食券を渡す)→「食券を渡す」(次は注文したものを受け取る)→「注文したものを受け取る」(次は皿を返却する)→「皿を返却する」(NULL)
↓「食券を買う」(次は食券を渡す)→「食券を渡す」(次は水をくむ)→「水を汲む」(次は注文したものを受け取る)→「注文したものを受け取る」(次は皿を返却する)→「皿を返却する」(NULL)
となる。
ハッシュテーブル
key:value型のテーブル構成のこと。ハッシュ関数を使用する。
ハッシュ関数は文字列を渡すと数値を返却する関数のこと。以下みたいな感じ
ハッシュ(インデックス) | key | value |
---|---|---|
1 | apple | red |
2 | banana | yellow |
5 | egg | white |
key:value型であればkey=ハッシュなんじゃないのかって思ったけど、上の数値、つまりハッシュ関数はインデックスのことを指す。
appleであれば、1,apple:red
bananaであれば、2,banana:yellow
こんな感じでインデックスを持っていてインデックス順に並んでいる。
ハッシュ関数の特徴として
上のapple、banana、eggのケースで考えると、この3つの要素は必ず同じインデックスである。2回目と3回目でインデックス番号は変化しない。
この場合3つしか要素がないので、ハッシュ関数で100は返さない。有効なものだけ返す。
インデックス採番の落とし穴
これだけだとあたかも簡単そうな感じだが、インデックス番号の振り方に1つ問題がある。
apple、banana、eggのインデックス番号の振り方を先頭1文字の英字からとってこようとした場合、avocadosがappleと同じインデックスになってしまう問題。
ハッシュ(インデックス) | key | value |
---|---|---|
1 | apple | red |
1 | avocados | green |
2 | banana | yellow |
5 | egg | white |
そうしたときに、appleは赤だが、avocadosは緑として更新すると、appleをkeyとして取得したときにgreenという全然違う値が取得されてしまう問題が発生する。
それを衝突という。
要素間のデータの検索・挿入・削除
ビッグオー記法では平均時間計算量としてはにあたる。
最悪時間計算量としてはとなる。
これはデータの挿入も削除も同じ。
ハッシュテーブルの特徴として1つのハッシュ関数を使用して値を取得する場合は処理がものすごく速い。
keyを指定指定してあげることでハッシュを通してvalueが出力できるから。
ただし、最悪時間計算量にも記載の通り、ハッシュテーブルは必ずしも早いわけではない。
ハッシュテーブルは順序保証がないという弱点を持っているから。
順序保障がないというのはどういうことかというと、プログラム上でハッシュテーブルに追加した順番と、メモリ上で持っている順番が必ずしもイコールであるとは限らないということ。
プログラム上、apple→avocados→banana→eggの順番で実装したとしてなんとなく上記順番でメモリに格納されているのではないかと思っている。
ただ実際のハッシュは以下になっている。
ハッシュ(インデックス) | key | value |
---|---|---|
1 | apple | red |
2 | banana | yellow |
5 | egg | white |
6 | avocados | green |
だからavocadosの値を取ってくるときにkeyで指定せずに単純検索、つまりforループで順番に取ってきた場合に要素2にあると思い込んでいると、実は要素4にあったので処理に時間がかかったという状況になる。
Pythonでのリスト・ハッシュリストのビッグオー記法
Pythonで実装する上でのパフォーマンスを知るためにも各型別の時間計算量をメモした。
順序保障はハッシュテーブルに記載している通り、要素を追加したときの順番をちゃんと守っているのか。
要素指定はひとつの値を取ってくるのに明示的に指定することができるか(リスト型なら要素番号、ハッシュテーブルならkey)。
要素変更は要素の追加・削除ができるか。
なお、辞書型で順序保障がされていない問題についてはPython3.7で解消された模様。
dict オブジェクトの挿入順序を保存するという性質が、公式に Python 言語仕様の一部であると 宣言されました 。
What's New In Python 3.7 — Python 3.7.2 ドキュメント
『なっとく! アルゴリズム』メモその1 ビッグオー記法
『なっとく! アルゴリズム』を読んで並行して勉強したことをメモしておく。
- 作者: アディティア・Y・バーガバ,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2017/02/01
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
ビッグオー記法とは何か
アルゴリズムがどのくらい高速なのかをあらわすもの。英語の大文字Oを使用する。 どうやらこれはランダウの記号というらしい。
ランダウの記号(ランダウのきごう、英: Landau symbol)は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。
ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O (オーもしくはオミクロン Ο。数字の0ではない)を用いることから(ランダウの)O-記法、ランダウのオミクロンなどともいう。
記号 O は「程度」の意味のオーダー(Order)から。 ランダウの記号 - Wikipedia
上記にも書いた通り、これでアルゴリズムがどれだけ高速であるのかをあらわすのだが、それを計算量という。
どれだけ高速なのかというのは、時間計算量という。
時間計算量には平均と最悪がそれぞれ存在する。
平均時間計算量:普通に処理したときの処理時間
最悪時間計算量:処理に一番時間がかかる場合に遭遇した時の処理時間
最悪時間計算量は単純に言うと、電話帳で「わ」から始まる人を調べるときに「あ」から順番に調べることと同義。
この場合、「あ」から「わ」まですべての人を見ていくことになるので途方もない時間がかかる。
ビッグオー記法の代表的な時間計算量
表記 | 意味 | 例 | 参照 |
---|---|---|---|
定数時間 | ハッシュテーブルへのアクセス | 定数時間 - Wikipedia | |
対数 | 二分探索 | 対数 - Wikipedia | |
線形関数 | 単純探索 | 一次関数 - Wikipedia | |
線形対数 | クイックソートのソートアルゴリズム | ||
多項式時間 | 選択ソートを使用した低速なアルゴリズム | 多項式時間 - Wikipedia | |
階乗関数 | 巡回セールスマン問題のような非常に低速なアルゴリズム |
上の表で上に行くほど処理が速くて、下に行くほど処理が遅い。
どのくらい時間が違うか
pythonで1~10までのデータ個数でどのくらい違うのかを以下を参考にしつつあらわしてみる。
import numpy as np import pandas as pd import math # 1~10の等差数列 input_data = np.arange(1,11,1) o_1 = np.array([1,1,1,1,1,1,1,1,1,1]) o_log = np.log(input_data) o_n = input_data o_nlog = input_data * np.log(input_data) o_n2 = input_data * input_data o_n_fact = np.array([math.factorial(w - 1) for w in input_data] ) pd.DataFrame([o_1, o_log, o_n, o_nlog, o_n2, o_n_fact], index=["O(1)", "O(logn)", "O(n)", "O(nlogn)", "O(n2)" ,"O(n!)"])
上記実装の結果
は問題外として、定数のが一番早い。
KeyValue型のアクセスは高速であるということが分かる。*1
データ個数が少ない場合は処理時間にそんなに変化がないことは分かるが、大きくなればなるほどその差が如実にあらわれる。
はアルゴリズム上ハッシュテーブルへのアクセス程度にしか使えないので、ソート等のアルゴリズムを見たときにが一番早いと認識してよさそう。
そもそもってなんだろう
が速いってことは分かった。
だけど、そもそも「」って何だって話。
atarimae.biz
ここにも書いているが、「〇を何乗すると×になるか」ということをあらわす。これを対数という。
の場合、2を何乗したら8になるのかということ。
この時のが対数。 言い方的には「2を底とする8の対数」と言うらしい。
この場合、「2を底とする8の対数」は3となる。
で、上に戻って「log n」の話になるんだけど、これ代入できる数値ひとつしかないじゃないの?って思った。
「???を底とするのn対数」この???はどこに行ったのか。
自然対数とネイピア数
「???を底とするのn対数」この???を理解するためには自然対数を理解しなければならない。
自然対数とは、「ln(エルエヌ)」とも書き、「ネイピアの数eを底とする対数」のことです。
自然対数lnとは?底のeって何?定義や微分積分、常用対数変換公式も紹介 | Studyplus(スタディプラス)
ネイピア数(ネイピアすう、英: Napier's constant)は数学定数の一つであり、自然対数の底である。ネーピア数とも表記する。記号として通常は e が用いられる。その値は
e = 2.71828 18284 59045 23536 02874 71352 …
と続く超越数である。ネピアの定数、ネピア数とも呼ばれる。欧米ではオイラー数 (Euler's number) と呼ばれることもあるが、オイラーの定数 γ やオイラー数列とは異なる。オイラーにちなんで名づけられた物事の一覧#オイラー数(英語版)も参照。
ネイピア数 - Wikipedia
「」は「」のことであるよう。
「」は省略可能なので 上の書き方で書くならば「ネイピア数を底とするのn対数」ということになる。
*1:こんなことしなくてもわかることではあったが