CPAC 2015のベンチマーク用ソースコード

CPAC2015_Bench.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Linq;
using System.Diagnostics;
class TEST{
	static void Main(){
		new TEST().GoBench();
	}
	
	void GoBench(){
		
		sw=new Stopwatch();
		sw.Start();
		long allstart=sw.ElapsedMilliseconds;
		
		String flnm="BenchMark.csv";
		Encoding sjisEnc = Encoding.GetEncoding("Shift_JIS");
		using(StreamWriter wr=new StreamWriter(flnm,false,sjisEnc)){
			wr.WriteLine("V,density,E,Dijk1,Dijk2,Dijk2f,Berm,SPFA");
			for(int v=10;v<4000;v+=10){
				for(int density=0;density<4;density++){
					int[][] AA=CreateGraph(v,density);

					int N=v;
					List<Pair>[] E=new List<Pair>[N];
					for(int i=0;i<N;i++){
						E[i]=new List<Pair>();
					}
					for(int i=0;i<N;i++){
						for(int j=i+1;j<N;j++){
							if(AA[i][j]==0)continue;
							E[i].Add(new Pair(j,AA[i][j]));
							E[j].Add(new Pair(i,AA[j][i]));
						}
					}
					int Ec=E.Select(x=>x.Count).Sum();
					long Dijk1=BenchDijk1(v,E);	Console.WriteLine("V:{0},density:{1},Ec:{2},Dijk1:{3}",v,density,Ec,Dijk1);
					long Dijk2=BenchDijk2(v,E);	Console.WriteLine("V:{0},density:{1},Ec:{2},Dijk2:{3}",v,density,Ec,Dijk2);
					long Dijk2f=BenchDijk2f(v,E);	Console.WriteLine("V:{0},density:{1},Ec:{2},Dijk2f:{3}",v,density,Ec,Dijk2f);
					long Berm=BenchBerm(v,E);	Console.WriteLine("V:{0},density:{1},Ec:{2},Berm:{3}",v,density,Ec,Berm);
					long SPFA=BenchSPFA(v,E);	Console.WriteLine("V:{0},density:{1},Ec:{2},SPFA:{3}",v,density,Ec,SPFA);
					
					String res=String.Format("{0},{1},{2},{3},{4},{5},{6},{7}",v,density,Ec,Dijk1,Dijk2,Dijk2f,Berm,SPFA);
					wr.WriteLine(res);
				}
			}
			long allend=sw.ElapsedMilliseconds;
			Console.WriteLine("Total:{0}ms",allend-allstart);
			wr.WriteLine("Total:{0}ms",allend-allstart);
		}
	}
	static Stopwatch sw;
	static Xor128 rnd=new Xor128();
	static int CostMax=10000;
	static int INF=(int)1e9;
	
	
	static int[][] CreateGraph(int N,int density){
		int[][] ret=new int[N][];
		for(int i=0;i<N;i++)ret[i]=new int[N];
		
		// make a tree
		int[] Randomizer=new int[N];
		int[] ord=new int[N];
		for(int i=0;i<N;i++){
			Randomizer[i]=rnd.Next((int)1e5);
			ord[i]=i;
		}
		Array.Sort(Randomizer,ord);
		List<int> L=new List<int>();
		L.Add(ord[0]);
		
		for(int i=1;i<N;i++){
			int cost=rnd.NextI(1,CostMax);
			int trgt=L[rnd.Next(L.Count)];
			ret[trgt][ord[i]]=ret[ord[i]][trgt]=cost;
			L.Add(ord[i]);
		}
		int EC=0;
		int ratio=0;
		switch(density){
			case 0://iso 1.0-1.1
				ratio=rnd.NextI(100,110);
				EC=(int)(Math.Pow(N,ratio/100.0));
				break;
			case 1://mid 1,1-1.5
				ratio=rnd.NextI(110,150);
				EC=(int)(Math.Pow(N,ratio/100.0));
				
				break;
			case 2://dense 1.5-.2.0
				ratio=rnd.NextI(150,200);
				EC=(int)(Math.Pow(N,ratio/100.0));
				
				break;
			case 3://random;
				ratio=rnd.NextI(100,200);
				EC=(int)(Math.Pow(N,ratio/100.0));
				break;
		}
		
		List<int> Rest0=new List<int>();
		List<int> Rand0=new List<int>();
		for(int i=0;i<N;i++){
			for(int j=i+1;j<N;j++){
				if(ret[i][j]==0){
					Rest0.Add((i<<12)+j);
					Rand0.Add(rnd.NextI(0,(int)1e8));
				}
			}
		}
		var Rest=Rest0.ToArray();
		var Rand=Rand0.ToArray();
		Array.Sort(Rand,Rest);
		for(int i=0;i<Math.Min(EC,Rest.Length);i++){
			int r=Rest[i]>>12;
			int c=Rest[i]%(1<<12);
			ret[r][c]=ret[c][r]=rnd.NextI(1,CostMax);
		}
		return ret;
	}
	
	
	
	
	static long BenchDijk1(int N,List<Pair>[] E){
		long strt=sw.ElapsedMilliseconds;
		
		int[] Dist=new int[N];
		for(int i=0;i<N;i++)Dist[i]=INF;
		Dist[0]=0;
		bool[] used=new bool[N];
		for(int t=0;t<N;t++){
			int trgt=-1;
			int min=INF;
			for(int i=0;i<N;i++){
				if(used[i])continue;
				if(Dist[i]<min){
					min=Dist[i];
					trgt=i;
				}
			}
			foreach(var e in E[trgt]){
				if(Dist[trgt]+e.Cost<Dist[e.Pos]){
					Dist[e.Pos]=Dist[trgt]+e.Cost;
				}
			}
			used[trgt]=true;
		}
//Console.Write("Dijk1 :{0}\t",String.Join(" ",Dist));		
		long ed=sw.ElapsedMilliseconds;
		return ed-strt;
	}
	
	static long BenchDijk2(int N,List<Pair>[] E){
		long strt=sw.ElapsedMilliseconds;
		
		int[] Dist=new int[N];
		for(int i=0;i<N;i++)Dist[i]=INF;
		bool[] used=new bool[N];
		
		var SH=new SkewHeap<Pair>();
		SH.Push(new Pair(0,0));
		
		while(SH.Count>0){
			var p=SH.Top;SH.Pop();
			int now=p.Pos;
			if(used[now]){
				continue;
			}
			used[now]=true;
			Dist[now]=p.Cost;
			foreach(var e in E[p.Pos]){
				if(Dist[e.Pos]>p.Cost+e.Cost){
					//Dist[e.Pos]=p.Cost+e.Cost;
					//SH.Push(new Pair(e.Pos,Dist[e.Pos]));
					SH.Push(new Pair(e.Pos,p.Cost+e.Cost));
				}
			}
		}
		
//Console.Write("Dijk2 :{0}\t",String.Join(" ",Dist));		
		long ed=sw.ElapsedMilliseconds;
		return ed-strt;
	}
	
	static long BenchDijk2f(int N,List<Pair>[] E){
		long strt=sw.ElapsedMilliseconds;
		
		int[] Dist=new int[N];
		for(int i=0;i<N;i++)Dist[i]=INF;
		bool[] used=new bool[N];
		int cntused=0;
		
		var SH=new SkewHeap<Pair>();
		SH.Push(new Pair(0,0));
		
		while(SH.Count>0){
			var p=SH.Top;SH.Pop();
			int now=p.Pos;
			if(used[now]){
				continue;
			}
			used[now]=true;
			Dist[now]=p.Cost;
			cntused++;
			if(cntused==N){
				break;
			}
			foreach(var e in E[p.Pos]){
				if(Dist[e.Pos]>p.Cost+e.Cost){
					Dist[e.Pos]=p.Cost+e.Cost;
					SH.Push(new Pair(e.Pos,Dist[e.Pos]));
					//SH.Push(new Pair(e.Pos,p.Cost+e.Cost));
				}
			}
		}
		
//Console.Write("Dijk2f:{0}\t",String.Join(" ",Dist));		
		long ed=sw.ElapsedMilliseconds;
		return ed-strt;
	}
	
	static long BenchBerm(int N,List<Pair>[] E){
		long strt=sw.ElapsedMilliseconds;
		
		int[] Dist=new int[N];
		for(int i=0;i<N;i++)Dist[i]=INF;
		Dist[0]=0;
		
		for(int t=1;t<N;t++){
			bool update=false;
			for(int i=0;i<N;i++){
				if(Dist[i]==INF)continue;
				foreach(var e in E[i]){
					if(Dist[e.Pos]>Dist[i]+e.Cost){
						Dist[e.Pos]=Dist[i]+e.Cost;
						update=true;
					}
				}
			}
			if(update)continue;
			break;
		}
//Console.Write("Berm  :{0}\t",String.Join(" ",Dist));		
		
		long ed=sw.ElapsedMilliseconds;
		return ed-strt;
	}
	static long BenchSPFA(int N,List<Pair>[] E){
		long strt=sw.ElapsedMilliseconds;
		
		int[] Dist=new int[N];
		for(int i=0;i<N;i++)Dist[i]=INF;
		bool[] Queued=new bool[N];
		Queue<int> Q=new Queue<int>();
		
		Dist[0]=0;
		Queued[0]=true;
		Q.Enqueue(0);
		
		while(Q.Count>0){
			var now=Q.Dequeue();
			Queued[now]=false;
			foreach(var e in E[now]){
				if(Dist[e.Pos]>Dist[now]+e.Cost){
					Dist[e.Pos]=Dist[now]+e.Cost;
					if(!Queued[e.Pos]){
						Q.Enqueue(e.Pos);
						Queued[e.Pos]=true;
					}
				}
			}
		}
		
//Console.Write("SPFA  :{0}\t",String.Join(" ",Dist));		
		long ed=sw.ElapsedMilliseconds;
		return ed-strt;
	}
	
}

class Pair : IComparable<Pair> {
	public int Pos;
	public int Cost;
	public Pair(int p, int c) {
		Pos = p; Cost = c;
	}
	public int CompareTo(Pair t) {
		return this.Cost > t.Cost ? 1 : this.Cost < t.Cost ? -1 : 0;
	}
}
class SkewHeap<T> where T:IComparable<T>{
	public int Count{
		get{return cnt;}
		private set{cnt=value;}
	}
	
	public SkewHeap(){
		root=null;
		this.Count=0;
	}
	
	public void Push(T v){
		NodeSH<T> p=new NodeSH<T>(v);
		root=NodeSH<T>.Meld(root,p);
		this.Count++;
	}
	
	public void Pop(){
		if(root==null)return;
		root=NodeSH<T>.Meld(root.L,root.R);
		this.Count--;
	}
	
	public T Top{
		get{return root.Val;}
	}
	
	int cnt;
	NodeSH<T> root;
	
	class NodeSH<S> where S : IComparable<S> {
		public NodeSH<S> L, R;
		public S Val;
		public NodeSH(S v){
			Val = v;
			L = null; R = null;
		}
		public static NodeSH<S> Meld(NodeSH<S> a, NodeSH<S> b){
			if(a == null)return b;
			if (b == null) return a;
			if (a.Val.CompareTo(b.Val) > 0) swap(ref a, ref b);
			a.R = Meld(a.R, b);
			swap(ref a.L, ref a.R);
			return a;
		}
		static void swap<U>(ref U x, ref U y) {
			U t = x; x = y; y = t;
		}
	}
}

class Xor128{
	static uint x = 123456789;
	static uint y = 362436069;
	static uint z = 521288629;
	static uint w = 88675123; 
	uint t;
	
	public Xor128(){
	}
	
	public Xor128(uint seed){
		z ^= seed;
		z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
	}
	
	
	public uint Next(){
		t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}
	public int Next(int ul){
		return NextI(0,ul-1);
	}
	public int NextI(int from,int to){
		int mod=to-from+1;
		int ret=(int)(Next()%mod);
		return ret+from;
	}
}

gistfile1.txt

Competitive Programming Advent Calendar 2015　の記事用のベンチマーク

Competitive Programming Advent Calendar 2015
  http://www.adventar.org/calendars/850
自分の記事：
  http://kuuso1.hatenablog.com/entry/2015/12/20/212620

大まかな流れ：
  static int[][] CreateGraph(int N,int density)　：ランダムに頂点数Nのグラフを生成
    最初に木を作って、あとは適当に辺を追加する
    densityは追加する辺の数を調整するためのフラグ
    　0:V-1.0 - V^1.1 の乱数
    　1:V-1.1 - V^1.5 の乱数
    　2:V-1.5 - V^2.0 の乱数
    　0:V-1.0 - V^2.0 の乱数
    　÷２してないのに後で気付いたorz
    
	static long BenchDijk1(int N,List<Pair>[] E)  //O(V^2)ダイクストラ，
	static long BenchDijk2(int N,List<Pair>[] E)  //O((E+V)logE)ダイクストラ
	static long BenchDijk2f(int N,List<Pair>[] E)  //O((E+V)logE)ダイクストラ・枝刈りあり
	static long BenchBerm(int N,List<Pair>[] E)   //O(VE) ベルマンフォード
	static long BenchSPFA(int N,List<Pair>[] E)   //O(VE) SPFA
		  それぞれベンチマーク。返り値に実行時間[ms]を返す。
		  アルゴリズムの正常動作はそれぞれsmall caseで一応確認済み。
	
	class Xor128
	  Xorシフトでの乱数生成器
	
	class SkewHeap<T> where T:IComparable<T>
	  skew heap。C#にはプライオリティキューがないので自作
	  　以下を参考（というかほぼコピペ）
	  　　http://hos.ac/blog/#blog0001