読者です 読者をやめる 読者になる 読者になる

藻のブログ

日記,IT,学問(ジェンダー,人工知能など)について書かれることでしょう。

計数ソート,基数ソート,ヒープソートを実装した

日記 アルゴリズム プログラミング

6月11日の日記。


正午過ぎに起きた。

出かけることはなかった。


お昼過ぎは、きのう習得した計数ソート基数ソートJava で実装した。

基数ソートの実行時間は  Ο(n) なので、理論上、  Ο(n \lg n) であるクイックソートよりも漸近的に高速なのだが、そうはならなかった。

不思議だ。実行は  n = 10000000 で試しているのだが、それでも基数ソートがクイックソートりょうする境界に至っていないのだろうか。それとも、実装が悪いのだろうか。

それはそれとして、工夫がたりない部分もあるかも知れない。基数ソートにはまだ興味がある。


夕方ころは、放置していたヒープソートの実装をやった。Python で途中まで書いてあったものを完成させた。

最初は、実行してみると、全然正しくソートできていなかった。まあ、それは良いのだが、私は Python の知識がないので、デバッグにもけっこう時間がかかった(1時間ぐらい……?)。まあ、最終的にはうまく行った。

Python では JavaC# のようにブレイクポイントを設定できるのだろうか……(インタプリタ言語ではステップ実行ができないというイメージがあるが、実際のところはどうなのだろうか?)。

実装

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にインストールできるソフトウェア群)のバージョンが古過ぎるという話も聞いていた(実際、私もそう思う。)。

そこで、これを機に、 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 はインストールした。


この日は、くるみ餅さんの調子が悪かったのでゲームの配信をやらなかった。良くなると良いのだが……。