本履歴

購入した古本の履歴と時々プログラミング

色々比較(アルゴリズム、Ruby v.s. Pascal、optimizationスイッチ)

The Algorithm Design Manualを眺めていたら、Median(wikipedia:中央値)を求めるのはソートして真ん中の値だからO(N*logN)かかりそうだけど、
クイックソートをちょっと変形するとO(N) expected timeで計算できるぜよ、とあったので考えてみた。

競技プログラミングっぽく

n個の値を入力として受け取り、中央値を出力するプログラム。

input:
n
v_1 v_2 ... v_n

output:
median of v

Constraints:
n=10**7+1
  small:v fits 16bit signed int
  large:v fits 32bit signed int

Ruby(1.9.2p290)とFreepascal(2.4.4)で実行。64bitの環境なのでRubyの整数はFixnumだ。
Pascalは{$R-,S-,Q-,I-,O+}スイッチを最初の行に付けてどのくらい速度に影響があるかチェックもしてみた(前からやりたかった)。
small, largeともに5個の入力を用意し(largeで100MBのファイル)、5個の実行結果のMedianをそのプログラムのrun timeとした!

Sortする方法

配列ソートして真ん中出力

Ruby
n=gets.to_i
puts gets.split.map(&:to_i).sort[n/2]

small:6.023sec
large:7.634sec

Pascal
var seq:array[0..10000009] of longint;
	k,n:longint;

procedure quicksort(l,r:longint);
var v,t,i,j:longint;
begin
	if l<r then begin
		v:=seq[r];i:=l-1;j:=r;
		repeat
			repeat inc(i) until v<=seq[i];
			repeat dec(j) until seq[j]<=v;
			t:=seq[i];seq[i]:=seq[j];seq[j]:=t;
		until j<=i;
		seq[j]:=seq[i];seq[i]:=seq[r];seq[r]:=t;
		quicksort(l,i-1);
		quicksort(i+1,r);
	end;
end;

begin
	readln(n);
	for k:=1 to n do read(seq[k]);
	quicksort(1,n);
	writeln(seq[(n+1) div 2]);
end.

small:3.409sec(3.232sec with opt on)
large:4.582sec(4.417sec)

NArrayのmedian

NArrayにmedianメソッドがあったので、使ってみた。

Ruby
require"narray"
n=gets.to_i
na=NArray.to_na(gets.split.map(&:to_i))
puts na.median

small:5.634sec
large:6.724sec
3行目、ArrayからNArrayを作っているのでなんかあほらしいことしてる気が。もっとうまい方法があるかも。

small限定バケツソート

Rangeが狭いとき限定のO(N)バケツソートを試してみた。

Ruby
D=32768
n=gets.to_i
buckets=Array.new((1<<16)+1,0)
gets.split.map(&:to_i).each{|v|buckets[v+D]+=1}
m=n/2
buckets.each_with_index{|count,i|
	m-=count
	if m<=0
		puts i-D
		exit
	end
}

small:4.956sec

Pascal
var buckets:array[-32768..32767] of longint;
	i,k,m,n,v:longint;

begin
	fillchar(buckets,sizeof(buckets),0);
	readln(n);
	for k:=1 to n do begin
		read(v);
		inc(buckets[v]);
	end;
	m:=(n+1) div 2;
	for i:=-32768 to 32767 do begin
		dec(m,buckets[i]);
		if m<=0 then begin
			writeln(i);
			break;
		end;
	end;
end.

small:1.997sec(1.880sec)

クイックソート変形Median

quicksortの最初の処理の、あるpivotを選択し左にその数以下、右にその数以上にしたあと、Medianが左右どちらに入っているか判断し、片方だけチェックする方法。

Pascal
var seq:array[0..10000009] of longint;
	i,n:longword;

function selection(l,k,r:longint):longint;
var v,t,i,j:longint;
begin
	if l<r then begin
		v:=seq[r];i:=l-1;j:=r;
		repeat
			repeat inc(i) until v<=seq[i];
			repeat dec(j) until seq[j]<=v;
			t:=seq[i];seq[i]:=seq[j];seq[j]:=t;
		until j<=i;
		seq[j]:=seq[i];seq[i]:=seq[r];seq[r]:=t;
		if k=i then selection:=seq[i] else
		if k<i then selection:=selection(l,k,i-1) else
			selection:=selection(i+1,k,r);
	end else selection:=seq[k];
end;

begin
	readln(n);
	for i:=1 to n do read(seq[i]);
	writeln(selection(1,(n+1) div 2,n));
end.

small:2.140sec(2.067sec)
large:3.101sec(3.040sec)

結論

  1. Ruby意外に健闘、思ったより速いじゃん。
  2. 値の範囲が狭い場合はバケツソート最強
  3. やはりアルゴリズム重要〜
  4. {$R-,S-,Q-,I-,O+}スイッチは気持ち程度