計数ソート,基数ソート,ヒープソートを実装した
6月11日の日記。
正午過ぎに起きた。
出かけることはなかった。
お昼過ぎは、きのう習得した計数ソート,基数ソートを Java で実装した。
基数ソートの実行時間は なので、理論上、 であるクイックソートよりも漸近的に高速なのだが、そうはならなかった。
不思議だ。実行は で試しているのだが、それでも基数ソートがクイックソートを凌駕する境界に至っていないのだろうか。それとも、実装が悪いのだろうか。
それはそれとして、工夫がたりない部分もあるかも知れない。基数ソートにはまだ興味がある。
夕方ころは、放置していたヒープソートの実装をやった。Python で途中まで書いてあったものを完成させた。
最初は、実行してみると、全然正しくソートできていなかった。まあ、それは良いのだが、私は Python の知識がないので、デバッグにもけっこう時間がかかった(1時間ぐらい……?)。まあ、最終的にはうまく行った。
Python では Java や C# のようにブレイクポイントを設定できるのだろうか……(インタプリタ言語ではステップ実行ができないというイメージがあるが、実際のところはどうなのだろうか?)。
実装
import math class Heap(object): def __init__(self, array = []): self.array = array def build_max_heap(self): self.heap_size = len(self.array) for i in reversed(range(0, math.floor(len(self.array) / 2))): self.max_heapify(i) def max_heapify(self, i): largest = self.largest_index(i) if largest != i: Heap.swap(self.array, i, largest) self.max_heapify(largest) def largest_index(self, i): left = Heap.left(i) right = Heap.right(i) if left < self.heap_size and self.array[left] > self.array[i]: largest = left else: largest = i if right < self.heap_size and self.array[right] > self.array[largest]: return right else: return largest def heap_sort(self): self.build_max_heap() for i in reversed(range(1, len(self.array))): Heap.swap(self.array, 0, i) self.heap_size -= 1 self.max_heapify(0) @staticmethod def left(i): return i * 2 + 1 @staticmethod def right(i): return i * 2 + 2 @staticmethod def swap(array, i, j): (array[i], array[j]) = (array[j], array[i]) @staticmethod def sorted(array): heap = Heap(array) heap.heap_sort() return heap.array
使い方
elements = [2,1,0,7,6,5,9] print(elements) print(Heap.sorted(elements))
出力
[2, 1, 0, 7, 6, 5, 9] [0, 1, 2, 5, 6, 7, 9]
土曜日は「つぶやき取得アプリケーション」の日。この日は、 Vagrant の設定をやった。
つぶやき取得アプリケーションの開発コードネームを「人間の条件」とした(ややこし過ぎるのでは……。)。
人間の条件は、ウェブサイトとして公開するタイプのアプリケーションにするつもり。ということで、プログラム(など)をウェブサーバに設置することになるのだが、ここで、ウェブサーバのOS(オペレーティングシステム)も決めることになる。
Linux ということは決まっているのだが、 Linux にもいろいろ種類がある。その中で、私が最も慣れている(って言うか、これしか使ったことがない。)のが CentOS というOSだ。ということで、今回も CentOS を利用するつもりだった。
ところが、先日、「CentOS は日本では熱心に利用されているが、世界的にはそうでもない」という話を目にした。加えて、真鍋さんから、 CentOS はリポジトリ(OSにインストールできるソフトウェア群)のバージョンが古過ぎるという話も聞いていた(実際、私もそう思う。)。
@bromne CentOS のリポジトリは話にならないほど古いから関係者全員皆○しにしたい
— Hiroshi Manabe@2時に寝る (@takeda25) 2016年5月11日
そこで、これを機に、 Ubuntu を利用することにした。 Ubuntu は世界的に非常にポピュラーなOSで、日本でもよく使われている。まったく使ったことがないので、慣れるまで大変だと思うが……。
Ansible の設定も試みた。以前仕事中に(勝手に)作った Ansible の設定ファイル(Playbook という。)をコピーして Vagrant を起動してみたのだが、まったくもって正常に動かない。それというのも、 Playbook が CentOS 用に作られているからだ。とりあえずは、 Playbook を Ubuntu 用に変更しなければならない。
ところで、 Vagrant の新しいバージョン 1.8.3
が公開されていた。たぶん、1か月ぐらい前までは 1.8.1
だったと思うんだけど……。 1.8.2
のが公開されてからすぐに 1.8.3
が公開されたということだろうか。1.8.3
はインストールした。
この日は、くるみ餅さんの調子が悪かったのでゲームの配信をやらなかった。良くなると良いのだが……。