Python でアルゴリズム

はんぶんこにしたら
速くなります

目的

アルゴリズムと聞くと難しそうですが、  「はんぶんこにすると速くなる」  という雰囲気が伝わればと思いました。

これだけです。 頑張ってコードを書きましたが、個々の細かいコードは、あまり掘り下げなくてもいいかなと感じたりもします。

アルゴリズムは実際の仕事でよく使われるのか

ワイが言うより100億倍わかりやすいと思うので引用させていただきます。

長期目標

長期的な目標としては、プログラミングスキルを向上させたいと言う思いがあるとおもいます。 であれば、とりあえず全体像を捉えてしまえばいいのかなと思います。

YouTube やあるいは上記のアプリでサクサク全体像を捉えて、 頭の中でデータの動きが追えれば、アルゴリズムの入り口は、その辺りにあるのかなと思っています。

あとは AtCoder などの問題にチャレンジするのが良い様な気がします。 AtCoder とかの問題を見だすと無限大に広がりだします。

メチャクチャすごい人がいっぱいいてビビります笑 Twitter で何食わぬ顔して呟いていたりするので、 戦闘力みたいな感じでスコア書いておいて欲しいです笑

ワイの競プロライフは二分探索木で光の速さで終止符が打たれました。 じゃあ何お前偉そうなこと言うとるんや?という感じです。

アルゴリズムの入り口は比較的、決まった様な題材が取り上げられている気がします。 やらないといけないことが無限大にある気がすると、やる気が削がれます。

とっかかりについては、そんなことないですよ、という、そんな感じです。

短期目標

就活

短期的な目標としては、資格試験や就職面接があると思います。 就職面接の場合は、アルゴリズムの全体像を暗記せざる得ないのかなと言う気がします。 会社ごとに傾向も異なると思うので、情報収集も必要だとは思いますが...

資格試験

反面、資格試験、例えば、基本情報などだと穴埋め式になっています。 こう言う資格試験だと問題の癖があったりします。

基本情報のアルゴリズムは、悪くはないと思うのですが、 全体像を知りたいという流れの中では、かなり辛い出題形式の様な気がします。

一通りソートのコードを書いたいま現在、 基本情報の問題を見ても本当にチンプンカンプンです。

もし基本情報でヤバいと思ったら、適当にアプリをダウンロードして、 パズルを解くのが良い気がします。

上記のアプリを使ったことがないので、オススメであるかはわからないのですが。 とりあえず触って全体像が知れればそれで十分かな..と。 ちなみに日本語版もあります。

なにに力点をおくべきか

やり方によっては、とても速くなるということを押さえておけばいいのかなと思ったりもします。

「アルゴリズム」と言う言葉があって何に力点を置いて学べばいいのか分からないと言うのがあるのかなと思います。 「アルゴリズム」といえば種類は無限大にありそうな気がするし、実際無限大にあるのですが、覚えようとすると心が折れます。

ただ巷の書店でアルゴリズムの入門書などの目次を見ていると、だいたい似た様なものが書かれています。 アルゴリズムの入り口で必要とされていることは、そこまで多くはないのかなと言う気がします。

プログラミング能力を向上させると言う目的でアルゴリズムの勉強をするのをよく見かけます。 巷には良質なアルゴリズムに関する書籍やアプリがたくさんあります。

このページでは Python で、それらのコードを書いたらどうなるのかを書いています。

大抵アルゴリズムの本にはソートの話が載っています。 Python は既に sort, sorted を用意してくれています。 よくアルゴリズムの勉強不要論なども Twitter で見かけます。 わざわざ勉強する必要性はあるのでしょうか?

やらないよりはやった方が良いかな...と。 ありとあらゆることが、やらないよりはやった方が良いですが... アルゴリズムを書き換えるとメチャクチャ速くなることがあります。

そのことを知る意味ではソートは、一番簡単な例の様に思えます。 業務系のコードを書く中で、これを知る自分自身で体系的に知り得るということは、 かなり稀なんじゃないかなと思ったりします。

なんで早くなるの?

じゃあなんではんぶんこにすると速くなるの?と言う話になります。 これは比較回数が少なくなるからです。

いまはパッと説明が思いつかないのですが。 いつか、アニメーションにして説明して見たいと思います。

ソートや二分探索木の話は「はんぶんこにしたら速くなる」。 これだけ押さえておけばいいかなと思います。

巷の書店で売っているアルゴリズムのコードとかを読むときもそれでいいんじゃないかなと。

この「はんぶんこ」アルゴリズムを難しい言葉で「分割統治法」と言います。 なんでこんなに難しい言葉になってしまったのでしょうか笑

流れ

流れとしては、まず「探索」から始まり「木」、そして「ソート」に話を持っていきます。

1. 探索

最初に「二分探索」を持って来たのは、比較的簡単だからです。 また、そのあとの「二分探索 」につなげることができるからです。

二分探索では、標準ライブラリ bisect を取り上げます。 bisect.py は短く、取り掛かりやすい気がします。

2. 木

次に「ソート」の前に「二分木」を持って来たのは、「二分ヒープ」は「ヒープソート」を、 「二分探索木」は「クイックソート」を図示することができるからです。

「二分ヒープ」では標準ライブラリ heapq を題材に取り上げます。 heapq.py は開くとウワッって感じがするのですが、やっていることそのものは単純です。

標準ライブラリに慣れることも、このページの目的であります。

3. ソート

最後に「マージソート」と「挿入ソート」、「クイックソート」、「ヒープソート」について触れていきます。

「バブルソート」を改良すると挿入ソートになるので、バブルソートについて触れてから 挿入ソートに話を持って行っています。

◯ TimSort

最終的に Python で使われているソートアルゴリズム TimSort に関する以下の記事の雰囲気が伝わればと思っています。 自分も外面しかまだ読めてません。

ここで前提とされている知識、 クイックソート、マージソート、ヒープソート、挿入ソートには触れて、 なんとか興味が持てるくらいのラインにまでいければと考えています。

高速な安定ソートアルゴリズム TimSort の解説

しかしながら、オリジナルのTimSortのコードは若干複雑で、 実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。

そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解説してみたいと思います (  クイックソート、マージソート、ヒープソート、挿入ソート  の知識を前提とします)。

4. 素数

素数はおまけです。

「素数」については、力技で調べざるを得ないので、 あまり得るものはないかなという感じもします。 純粋にコードの書き方の世界という感じがします。

たまに競プロででてきたりするので、 雰囲気だけ押さえておけばいいかなとも思います。

まとめ

はんぶんこにしたら速くなることです。 細かいコードは掘り下げなくて大丈夫です。

Last Updated: 8/8/2019, 8:53:30 PM