Python でアルゴリズム

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

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

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

全体の流れ

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

1. 探索

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

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

2. 木

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

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

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

3. ソート

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

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

◯ TimSort

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

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

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

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

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

4. 素数

素数はおまけです。

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

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

目的

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

Last Updated: 5/24/2019, 2:47:11 AM