D Paste by downs
Description: fannkuch benchmark
Hide line numbers

Create new paste
Post a reply
View replies

Paste:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
import std.stdio, std.string;

extern(C) {
  struct timeval {
    uint tv_sec;
    int tv_usec;
  }
  int gettimeofday(timeval *tv, void *tz);
}

void main(string[] args) {
  timeval start, end;
  foreach (arg; args[1..$]) {
    auto n=arg.atoi();
    gettimeofday(&start, null);
    writefln("Pfannkuchen(", n, ") = ", fannkuch(n));
    gettimeofday(&end, null);
    auto t1 = start.tv_sec*1000.0 + start.tv_usec/1000.0;
    auto t2 = end.tv_sec*1000.0 + end.tv_usec/1000.0;
    writefln("duration ", t2-t1);
  }
}

int fannkuch(int n) {
  int check, maxFlipsCount;
  auto perm=new int[n], perm1=new int[n], count=new int[n], maxPerm=new int[n];
  foreach (id, ref elem; perm1) elem=id;
  int r=n;
  while (true) {
    while (r != 1) { count[r-1]=r; --r; }
    if (!(perm1[0]==0 || perm1[n-1]==n-1)) {
      perm[]=perm1;
      int flipsCount, k;
      while ((k=perm[0])!=0) {
        int k2 = (k+1)>>1;
        foreach (i, ref elem; perm[0..k2]) { auto temp=elem; elem=perm[k-i]; perm[k-i]=temp; }
        flipsCount++;
      }
      if (flipsCount > maxFlipsCount) {
        maxFlipsCount = flipsCount;
        maxPerm[]=perm1;
      }
    }
    
    while (true) {
      if (r==n) return maxFlipsCount;
      auto perm0=perm1[0];
      foreach (id, elem; perm1[1..r+1]) perm1[id]=elem;
      perm1[r]=perm0;
      count[r]--;
      if (count[r]>0) break;
      ++r;
    }
  }
}

Replies:

    (some replies deleted)