qsortってquickじゃなくね? - ここにタイトルを入力|

haskellの例文で有名なqsort

sort [] = [];
sort (x:xs) = sort [y | y<-xs, y<x] ++ [x] ++ sort [y | y<-xs, y>=x]

こんなの。
haskell学んでるときに、この内包表記とか反則だろとか思った。
数学的に書くと
{ y | y ∈ xs, y < x }
みたいな?

ってそのまんまやん。

で、これ、このsort。
確かに形的にはquickSortなんだけど、[x]の前後の内包表記でxsを全部触ってるよね?
ふつにqsortをcとかで実装すると両側からポインタ移動させるから、探査がリストの長さ分で済むケド、↑の場合2倍に...。
あ、でもオーダー的にはquickなのか。
係数が違うだけか。

ってことを考えてみてたのだが、論より証拠。実際に実行してみて計ってみた。
今回比較したのはこの三つ。

C++(ccSort.cc)

#include <set>
#include <iostream>

int main ( int argc, char* argv[] )
{
	using namespace std;

	string line;
	set<string> lines;
	set<string>::iterator it;

	while( !getline( cin, line ).eof() ) {
		lines.insert( line );
	}
	
	for( it = lines.begin(); it != lines.end(); ++it ) {
		cout << *it << endl;
	}
}

頑張ってSTLつかってみた。

haskellその1(hsSort1.hs)

import List
main = do ls <- getContents
	  putStr $ unlines $ List.sort $ lines ls

module使ってみた

haskellその2(hsSort2.hs)

sort [] = [];
sort (x:xs) = sort [y | y<-xs, y<x] ++ [x] ++ sort [y | y<-xs, y>=x]
main = do ls <- getContents
	  putStr $ unlines $ sort $ lines ls

例のqsort

で測定用のシェルスクリプトはこちら

#!/usr/bin/env bash

outfileHs1="Hs1.result"
outfileHs2="Hs2.result"
outfileCc="Cc.result"
infile="rndList"
rm $outfileHs1
rm $outfileHs2
rm $outfileCc
for(( i=1024; i<=131072; i+=1024 )) {
	echo -ne "$i\t" >> $outfileCc
	echo -ne "$i\t" >> $outfileHs1
	echo -ne "$i\t" >> $outfileHs2
	seq -w $i | shuffle -s1 > $infile
	time ./ccSort < $infile 2>&1 >/dev/null | sed -n "s/^.*\(.....\)elapsed.*$/\1/p" >> $outfileCc
	time ./hsSort1 < $infile 2>&1 >/dev/null | sed -n "s/^.*\(.....\)elapsed.*$/\1/p" >> $outfileHs1
	time ./hsSort2 < $infile 2>&1 >/dev/null | sed -n "s/^.*\(.....\)elapsed.*$/\1/p" >> $outfileHs2
}