/*
java.exe -Xms1024m A
Jagged unopt time 85.958287 msc
Jagged opt time 602.58672 msc
Simple unopt time 69.588572 msc
Simple opt time 412.327974 msc
*/
class A {
private final static int n = 8000;
private final static int g[][] = new int[n][n];
private final static int a[] = new int[n*n];
for(int i=0;i<10;i++) {
testRun1(args);
testRun2(args);
testRun3(args);
testRun4(args);
}
}
public static void testRun1
(String[] args
) { long st, en;
// one
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
g[i][j] = i + j + i*n + j*n;
}
}
System.
out.
println("Jagged unopt time " + (en
- st
)/1000000.
d + " msc"); }
public static void testRun2
(String[] args
) { long st, en;
// two
for(int i = 0; i < n; i++) {
g[i][i] = i + i + i*n + i*n;
for(int j = 0; j < i; j++) {
g[j][i] = g[i][j] = i + j + i*n + j*n;
}
}
System.
out.
println("Jagged opt time " + (en
- st
)/1000000.
d + " msc"); }
public static void testRun3
(String[] args
) { long st, en;
// two
for(int i = 0; i < n; i++) {
final int in = i*n;
for(int j = 0; j < n; j++) {
final int jn = j*n;
a[in + j] = in + j + i + jn;
}
}
System.
out.
println("Simple unopt time " + (en
- st
)/1000000.
d + " msc"); }
public static void testRun4
(String[] args
) { long st, en;
// two
for(int i = 0; i < n; i++) {
final int in = i*n;
a[in + i] = in + i + i + in;
for(int j = 0; j < i; j++) {
final int jn = j*n;
a[jn + i] = a[in + j] = in + i + j + jn;
}
}
System.
out.
println("Simple opt time " + (en
- st
)/1000000.
d + " msc"); }
}
LyoKIGphdmEuZXhlIC1YbXMxMDI0bSBBCgogSmFnZ2VkIHVub3B0IHRpbWUgODUuOTU4Mjg3IG1zYwogSmFnZ2VkIG9wdCB0aW1lIDYwMi41ODY3MiBtc2MKIFNpbXBsZSB1bm9wdCB0aW1lIDY5LjU4ODU3MiBtc2MKIFNpbXBsZSBvcHQgdGltZSA0MTIuMzI3OTc0IG1zYwoqLwpjbGFzcyBBIHsKCiAgICBwcml2YXRlIGZpbmFsIHN0YXRpYyBpbnQgbiA9IDgwMDA7CiAgICBwcml2YXRlIGZpbmFsIHN0YXRpYyBpbnQgZ1tdW10gPSBuZXcgaW50W25dW25dOwogICAgcHJpdmF0ZSBmaW5hbCBzdGF0aWMgaW50IGFbXSA9IG5ldyBpbnRbbipuXTsKCnB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBFeGNlcHRpb24gewoKICAgIGZvcihpbnQgaT0wO2k8MTA7aSsrKSB7CiAgICAgIHRlc3RSdW4xKGFyZ3MpOyAKICAgICAgdGVzdFJ1bjIoYXJncyk7IAogICAgICB0ZXN0UnVuMyhhcmdzKTsgCiAgICAgIHRlc3RSdW40KGFyZ3MpOyAKICAgICAgU3lzdGVtLm91dC5wcmludGxuKCk7CiAgICAgIGlmKGk9PTMpIFRocmVhZC5zbGVlcCgxMDAwKTsKICAgIH0KfQpwdWJsaWMgc3RhdGljIHZvaWQgdGVzdFJ1bjEoU3RyaW5nW10gYXJncykgeyAKICAgIGxvbmcgc3QsIGVuOwogICAgIAogICAgLy8gb25lCiAgICBzdCA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgZm9yKGludCBqID0gMDsgaiA8IG47IGorKykgewogICAgZ1tpXVtqXSA9IGkgKyBqICsgaSpuICsgaipuOwogICAgfQogICAgfQogICAgZW4gPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbigiSmFnZ2VkIHVub3B0IHRpbWUgIiArIChlbiAtIHN0KS8xMDAwMDAwLmQgKyAiIG1zYyIpOwp9CnB1YmxpYyBzdGF0aWMgdm9pZCB0ZXN0UnVuMihTdHJpbmdbXSBhcmdzKSB7CiAgICBsb25nIHN0LCBlbjsKICAKICAgIC8vIHR3bwogICAgc3QgPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgIGdbaV1baV0gPSBpICsgaSArIGkqbiArIGkqbjsKICAgIGZvcihpbnQgaiA9IDA7IGogPCBpOyBqKyspIHsKICAgIGdbal1baV0gPSBnW2ldW2pdID0gaSArIGogKyBpKm4gKyBqKm47CiAgICB9CiAgICB9CiAgICBlbiA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgU3lzdGVtLm91dC5wcmludGxuKCJKYWdnZWQgb3B0IHRpbWUgIiArIChlbiAtIHN0KS8xMDAwMDAwLmQgKyAiIG1zYyIpOwogICAgfQoKcHVibGljIHN0YXRpYyB2b2lkIHRlc3RSdW4zKFN0cmluZ1tdIGFyZ3MpIHsKICAgIGxvbmcgc3QsIGVuOwogIAogICAgLy8gdHdvCiAgICBzdCA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGZpbmFsIGludCBpbiA9IGkqbjsKICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgbjsgaisrKSB7CiAgICAgICAgICBmaW5hbCBpbnQgam4gPSBqKm47CiAgICAgICAgICBhW2luICsgal0gPSBpbiArIGogKyBpICsgam47CiAgICAgICAgfQogICAgfQogICAgZW4gPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbigiU2ltcGxlIHVub3B0IHRpbWUgIiArIChlbiAtIHN0KS8xMDAwMDAwLmQgKyAiIG1zYyIpOwogICAgfQoKcHVibGljIHN0YXRpYyB2b2lkIHRlc3RSdW40KFN0cmluZ1tdIGFyZ3MpIHsKICAgIGxvbmcgc3QsIGVuOwogIAogICAgLy8gdHdvCiAgICBzdCA9IFN5c3RlbS5uYW5vVGltZSgpOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGZpbmFsIGludCBpbiA9IGkqbjsKICAgICAgICBhW2luICsgaV0gPSBpbiArIGkgKyBpICsgaW47CiAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IGk7IGorKykgewogICAgICAgICAgIGZpbmFsIGludCBqbiA9IGoqbjsKICAgICAgICAgICBhW2puICsgaV0gPSBhW2luICsgal0gPSBpbiArIGkgKyBqICsgam47CiAgICAgICAgfQogICAgfQogICAgZW4gPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbigiU2ltcGxlIG9wdCB0aW1lICIgKyAoZW4gLSBzdCkvMTAwMDAwMC5kICsgIiBtc2MiKTsKICAgIH0KfQ==