感性理解 EOJ 测评机速度 (Past)

ultmaster edited 6 年前

This is a past version of blog 感性理解 EOJ 测评机速度

对比测试

# Language Loop Euler Sieve Floyd-Warshall std::set Memory Alloc (new)
Codeforces G++ 5.1.0 (-O2) 288 295 967 701 857
LibreOJ(2017.12.10) G++ 5.4.0 (-O2) 301 319 823 850 736
Universal Online Judge G++ 4.8.4 (-O2) 435 530 1377 996 918
BZOJ G++ 4.4.5 (-O2) 504 1280 2092 1368 1568
HUSTOJ G++ 4.4.5 (-O2) 908 1460 1413 1553 Unexpected MLE (ML = 512MB)
EOJ (Goat) G++ 5.4.0 (-O2) 464 344 1120 672 736 (ML = 1GB)
EOJ (Cow) G++ 5.4.0 (-O2) 332 388 1056 736 768 (ML = 1GB)

测试代码

// Test 1: Loop
#include<cstdio>

using namespace std;

int main(){
    int a=1000000000,b=1;
    while(a)b<<=1,a--;
    printf("%d\n",b);
    return 0;
}
// Test 2: Euler Sieve
#include<cstdio>

using namespace std;
const int MX=50000000;
int p[MX],m[MX],pc;
int main(){
    for(int i=2;i<MX;i++){
        if(!m[i])p[++pc]=m[i]=i;
        static int k;
        for(int j=1;j<=pc&&p[j]<=m[i]&&(k=p[j]*i)<MX;j++)m[k]=p[j];
    }
    int ans=0;
    for(int i=1;i<=pc;i++)ans^=p[i];
    printf("%d\n",ans);
    return 0;
}
// Test 3: Floyd-Warshall
#include<cstdio>

using namespace std;
const int MX=1000;
int G[MX][MX];
int sed=0;
inline int rand(){return sed=(sed*sed*73+sed*233+19260817)&0x0000ffff;}
int main(){
    for(int i=0;i<MX;i++)
        for(int j=0;j<MX;j++)
            G[i][j]=rand();
    for(int i=0;i<MX;i++)
        for(int j=0;j<MX;j++)
            for(int k=0;k<MX;k++)
                if(G[j][k]>G[j][i]+G[i][k])G[j][k]=G[j][i]+G[i][k];
    int ans=0;
    for(int i=0;i<MX;i++)
        for(int j=0;j<MX;j++)
            ans^=G[i][j];
    printf("%d\n",ans);
    return 0;
}
// Test 4: std::set
#include<cstdio>
#include<algorithm>
#include<set>

using namespace std;

const int MX=1000000;
int sed=0;
inline int rand(){return sed=(sed*sed*73+sed*233+19260817);}
int main(){
    set<int>S;
    for(int i=0;i<MX;i++)S.insert(rand());
    int ans=0;
    for(set<int>::iterator it=S.begin();it!=S.end();it++)ans^=*it;
    printf("%d\n",ans);
    return 0;
}
// Test 5: Memory Alloc (new)
#include<cstdio>

using namespace std;
const int MX=20000000;
int *it[MX];
int main(){
    for(int i=0;i<MX;i++)it[i]=new int;
    for(int i=0;i<MX;i++)*it[i]=i;
    int ans=0;
    for(int i=0;i<MX;i++)ans^=*it[i];
    printf("%d\n",ans);
    return 0;
}

IO test

3 million non-negative integers in one single line.

Input will be faster if it is naturally buffered (for example in Python).

Time limit is 5 seconds. All numbers are in millisecond(s).

# Machine $[0,2)$ $[0,8)$ $[0,2^{15})$ $[0,2^{31})$ $[0,2^{63})$
fread Goat 20 12 52 72 120
fread Cow 16 12 48 88 104
getchar Goat 64 52 140 252 452
getchar Cow 60 68 160 268 520
cin.tie(0) Goat 460 560 764 1344 2044
cin.tie(0) Cow 464 696 948 1344 3096
scanf Goat 288 252 444 600 844
scanf Cow 256 260 572 516 1148
cin Goat 516 608 848 1340 2100
cin Cow 514 516 860 1444 2456
Java Goat 2732 3016 3368 3928 4440
Java Cow 2572 2904 3184 4396 TL
Java Buffered Goat 780 900 996 916 1864
Java Buffered Cow 652 620 836 1220 1472
Python Goat 836 992 1052 1052 1072
Python Cow 984 616 672 812 948