Dual pivot quicksort（C++）

雑談

(2010-06-17　quick sortに誤りがあったので結果とコードを削除した)

前回の「Dual pivot quicksort - 鯨飲馬食コード」で書いたコードをC++でテンプレートとイテレータを用いて書き直し、ソートアルゴリズムの簡単な比較を行った。

比較したのは以下。

  • comb sort
  • dual pivot quicksort
  • merge sort
  • heap sort
  • sort(STL)

merge sortにはSTLのalgorithmのinplace_merge()を、heap sortにはmake_heap()とsort_heap()を用いた。そのため、merge sortはin-place merge sortになっている。なお、今回はOpenSUSE(64bit)のGCC 4.3.2でコンパイルと実行を行った。CPUは恐らくCore i7 920。前回と同じく、ランダムに初期化した対象をシャッフルし、それを100回ソートした合計時間（単位は秒）を計測した。以下が、intの配列、doubleの配列、vectorに対する結果である。

int[] 10^2 10^3 10^4 10^5 10^6
comb 0.00080 0.01284 0.12394 1.41319 17.32017
dp quick 0.00050 0.00748 0.05842 0.73328 8.771995
merge 0.00083 0.00661 0.09138 1.12073 13.10182
heap 0.00089 0.00904 0.09432 1.12579 14.80598
sort(STL) 0.00054 0.00444 0.05765 0.71067 8.436584
double[] 10^2 10^3 10^4 10^5 10^6
comb 0.00088 0.00863 0.11711 1.53876 19.94226
dp quick 0.00058 0.00507 0.06853 0.84975 10.32859
merge 0.00088 0.00725 0.10579 1.27179 17.16877
heap 0.00098 0.00803 0.10171 1.29183 15.04881
sort(STL) 0.00064 0.00529 0.06886 0.84865 10.08956
vector 10^2 10^3 10^4 10^5 10^6
comb 0.00186 0.01654 0.22988 2.99571 36.49776
dp quick 0.00114 0.00945 0.12397 1.52977 18.23587
merge 0.00175 0.01295 0.18170 2.11738 24.20834
heap 0.00140 0.01046 0.13905 2.09955 37.41475
sort(STL) 0.00128 0.01000 0.12771 1.55464 18.32365

流石と言うべきか、algorithmのsort()は速い。

自分で実装したcomb sort、dual pivot quicksortはランダムアクセスイテレータだけでなく、双方向イテレータでも動作するように書いた（つもりな）ので、ついでにlistも対象とした。比較対象としてlist::sort()を用いた結果が以下。なおランダムシャッフルに時間がかかったので、対象の長さは短めとなっている。

list 10^2 10^3 10^4
comb 0.00248 0.02489 0.35177
dp quick 0.00170 0.01433 0.19432
list::sort 0.00240 0.01881 0.31493

以下コード。

続きを読む

Dual pivot quicksort

雑談

(2009-11-05追記　heap sortにバグをあったのでコードを差し替え、計測しなおした)
(2009-11-06追記　heap sortのコードと結果を削除した)
(2010-06-17追記　quick sortに誤りがあったので結果とコードを削除した)

先日、dual pivot quicksortというソート法があるということを耳にしたので、空き時間に他のソート法の復習も兼ねて書いてみた。なお、dual pivot quicksortについてはDualPivotQuicksort.pdf(PDF)を、他のソート法についてはWikipediaのソートアルゴリズムの項を参照した。テストも不十分なnaiveな実装であることについてはご容赦いただきたい。

Cのintの配列を対象とし、配列の長さを変えて各手法の実行時間を計測した。対象とした配列はランダムに初期化し、シャッフルして100回ソートした。以下はその100回のソートに要した合計時間（単位は秒）である。コンパイルはGCC 4.23（Ubuntu 8.04）で-O3オプションを用い、Pentium4の3GHzくらいのマシン上で実行した。

algorithm 10^2 10^3 10^4 10^5 10^6 10^7
comb 0.00080 0.01187 0.13390 1.77721 22.96319 275.91818
merge 0.00065 0.00870 0.09282 1.14258 14.43083 181.81334
dual pivot quick 0.00055 0.00789 0.07945 0.99821 11.98756 139.99590
stdlib 0.00174 0.02288 0.20753 2.47627 29.83281 348.54542

ランダムなint配列に対してはdual pivot quicksortはなかなか良さそうな結果が出た。stdlibのsortが振るわないが、恐らく私の用い方が悪いのだろう。

以下コード。C++でテンプレートとイテレータを使って書きおなそうかとも思ったが、今回は見送った。

続きを読む

Tera TermからVimを使うときにBackSpaceが効かない

雑談

geditからVim派に改宗してからというもの、快適なエディタ生活を送っていたのだが、つい最近Tera Termで接続してからVimを使うと、なぜかBackSpaceキーで文字が消せないということに気付いた。カーソルは左に移動するのだが文字が消えないのだ。Ubuntu環境では問題ないので放っておいたのだが、やはり気になるので調べてみた。

ウェブ上で検索すると「TeraTermからViエディタを使用するとDelete、BackSpaceキーがきかない - 教えて！goo」が見つかったが解決法はない。仕方ないので、とりあえず.vimrcをmvしてみると問題なく文字が削除できることがわかった。というわけで、.vimrcのどこかが悪さをしていると分かり、一つずつ調べて原因を探り当てた。

inoremap <C-h> <left>

カーソルが左に移動するので気付かなかった。BackSpaceで「^H」、Deleteで「^?」か。

PageRankアップデート（2009年5月）

雑談

気付いたら「鯨飲馬食コード」のPageRankが3になっていた（2009-05-30 10時ごろ Firefox版GoogleToolbar調べ）。以前「PageRankアップデート（2009年1月）」で書いたようにPageRank4は一時的なものだったようだ。

今回のアップデートにより「個人ニュースサイトのPageRank - 鯨飲馬食コード」や「はてなダイアリーのPageRank - 鯨飲馬食コード」のデータも変化していると予測される。新しいデータを調べてみたい人は「RubyでPageRankの参照 - 鯨飲馬食コード」にRubyのスクリプトがあるので、参考にしてもらいたい。

Google App EngineでRSS

雑談

PythonとGoogle App Engineの勉強を兼ねて、性懲りもなくRSSのジェネレータを作ったよ。データベースの知識がなかったのでかなり手間取ったけども。

おそらく以前Pipesで作ったものと解析精度は変わらないけど、今回は更新日時を表示できるようにした。表示が遅いのはdjangoのテンプレートを使っているせいかもしれない。データベースへのリクエストはmemcacheでキャッシュしているのでボトルネックにはなりにくいと思っている。

そろそろRSSというかXMLを吐く方じゃなくて、それを処理する方を手がけなくてはいけないなと思う。もう2009年だし。

重複なしリスト

Python

Pythonで、RubyのArray#uniqみたいにリストから重複している要素を削除する方法ってないかなと思ったのでメモ。原理的にはこういうことだよね。

#!/usr/bin/python
#coding: utf-8
#for Python2.5

def uniq(ol):
  ul = list()
  s = set()
  for x in ol:
    if x not in s:
      ul.append(x)
      s.add(x)
  return ul

orig_list = [3,2,4,1,2,3,1,4,4,1,3,2]
set_list = list(set(orig_list))
uniq_list = uniq(orig_list)

print orig_list
print set_list
print uniq_list

以下実行結果。

[3, 2, 4, 1, 2, 3, 1, 4, 4, 1, 3, 2]
[1, 2, 3, 4]
[3, 2, 4, 1]

いったんlistからsetにしてまた戻す方法だと重複はなくなるが、順番が保持されずにソートされたようになる。この方法だと"x not in s"の計算量がどれくらいかが気になるところ。

Web API関連（Python3.0）

Python

前回の「Web API関連」は、正規表現を使ったところがいまいちだった。ウェブ上で探してみると、どうやらPython2.6から標準でjsonのパーサがライブラリに含まれるらしい。そこでUbuntu8.10のリポジトリに含まれていたPython3.0（rc1+）の環境で書き直してみた。

#!/usr/bin/python
#for Python3.0

from xml.etree import ElementTree
import xmlrpc.client
import urllib.request
import json

username = "geiinbashoku2"

# はてなブックマーク件数
srv = xmlrpc.client.ServerProxy('http://b.hatena.ne.jp/xmlrpc')
print(srv.bookmark.getTotalCount("http://d.hatena.ne.jp/" + username + "/"))

# livedoor reader 購読者数
d = urllib.request.urlopen("http://rpc.reader.livedoor.com/count?feedlink=http://d.hatena.ne.jp/" + username + "/rss")
print(d.read().decode())
d.close()

# はてなスター数
d = urllib.request.urlopen("http://s.hatena.ne.jp/blog.json/http://d.hatena.ne.jp/" + username + "/")
print(json.loads(d.read().decode())["star_count"])
d.close()

# livedoor clip数
srv = xmlrpc.client.ServerProxy('http://rpc.clip.livedoor.com/count')
values = srv.clip.getCount("http://d.hatena.ne.jp/" + username + "/").values()
print(list(values)[0])

# PageRank
d = urllib.request.urlopen("http://www.trynt.com/google-pagerank-api/v1/?u=http://d.hatena.ne.jp/" + username + "/")
print(ElementTree.parse(d).findall("//Pagerank")[0].text)
d.close()

jsonパーサはすごく使いやすそうだ。