Skip to content

Instantly share code, notes, and snippets.

@kuuso

kuuso/CPAC2015_Bench.cs

Last active September 17, 2019 16:33
Show Gist options
  • Save kuuso/2d7bb35a9c78966d6b97 to your computer and use it in GitHub Desktop.
Save kuuso/2d7bb35a9c78966d6b97 to your computer and use it in GitHub Desktop.
Download ZIP
CPAC 2015のベンチマーク用ソースコード
Raw
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;
}
}
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment