가장 빠른 알고리즘의 경쟁 실행

Question

나는 골프 대회와 같은 대회를 운영하고 싶지만 우승자에게는 가장 작은 알고리즘이 아닌 가장 빠른 알고리즘이 적용됩니다.

• 알고리즘의 속도를 측정하는 올바른 방법 중 하나는 Java의 JVM과 같은 중립 가상 머신을 사용하는 것입니다. 실행 된 JVM 명령어의 총 수를 쉽게 알 수 있습니까? (항목이 다수의 스레드를 사용하는 경우, JVM 명령들의 총 개수는 모든 스레드에 걸쳐 합산된다.) 예를 들어

코드

public class simple { 
    public static int main(String argc[]) { 
     int i; 

     i = 3; 
     while (i > 0) { 
      i--; 
     } 

    return 0; 
    } 
} 

는 JVM 코드를 생성

0: iconst_3 
1: istore_1 
2: iload_1 
3: ifle 12 
6: iinc 1, -1 
9: goto 2 
12: iconst_0 
13: ireturn 

그리고 정확히 계산하면 18 개의 JVM 명령어가 실행됩니다.

• 나는 사람들이 집에서 자신의 항목을 실행할 수 있고, 판사가 무엇을 볼 수 있는지보고 싶습니다. 분명히, 내가 프로그램에 의견을 제공한다면, 가장 빠른 해결책은 메모를 작성하고 미리 계산 된 답변을 내뱉는 것입니다. 객관적으로 사람들이 집에서 프로그램을 실행하게하고 메모 된 답을 볼 수 없게하는 방법이 있습니까?

• 비공식 "가장 빠른 코드 경쟁"이 발생하지 않도록하는 다른 문제는 무엇입니까?

고마워요!

Answer 1

공정한 비교는 일반적인 하드웨어에서 가장 짧은 완료 시간입니다. 프로그램을 완료하는 데 걸리는 시간은 전적으로 하드웨어에 달려 있습니다. 그렇지 않은 경우 더 많은 전력 기계에 돈을 쓰는 것이 무엇이겠습니까?

재현 가능한 결과를 얻는 가장 가까운 방법은 상대 속도를보고하는 것입니다. 시간의 50 %를 실행하는 사용자 프로그램의 기간에 샘플 프로그램 및 보고서를 제공하십시오. 한 대의 PC에서 두 배 빠른 속도의 프로그램은 다른 컴퓨터에서 두 배 빠른 속도를 보입니다.

uni에서는 "secret"입력에 대해 실행될 과제를 제출하지만 오류를 수정하기 위해 두 번 이상 제출할 수 있습니다. 첫 번째 제출은 전혀 작동하지 않았지만 모든 입력을 기록했습니다. ;)

편집 : 더 긴 대답.

는 다음과 같은 프로그램을 고려

public class FibMain { 
    public static void main(String... args) { 
     { 
      long start = System.nanoTime(); 
      System.out.println(iteration_fib(Integer.parseInt(args[0]))); 
      long time = System.nanoTime() - start; 
      System.out.printf("Iteration took %,d us%n", time/1000); 
     } 
     { 
      long start = System.nanoTime(); 
      System.out.println(recursive_fib(Integer.parseInt(args[0]))); 
      long time = System.nanoTime() - start; 
      System.out.printf("Recursion took %,d us%n", time/1000); 
     } 
    } 

    public static long iteration_fib(int n) { 
     long t1 = 1; 
     long t2 = 1; 
     while (n-- > 2) { 
      long t = t2; 
      t2 += t1; 
      t1 = t; 
     } 
     return t2; 
    } 

    public static long recursive_fib(int n) { 
     if (n <= 2) return 1; 
     return recursive_fib(n - 1) + recursive_fib(n - 2); 
    } 
} 

당신은 그래서 첫 번째 예는 더 이상 두 번째는 당신이 의심 할 수 있도록한다는 것입니다 당신이

public static long iteration_fib(int); 
    Code: 
    0: lconst_1 
    1: lstore_1 
    2: lconst_1 
    3: lstore_3 
    4: iload_0 
    5: iinc 0, -1 
    8: iconst_2 
    9: if_icmple  25 
    12: lload_3 
    13: lstore 5 
    15: lload_3 
    16: lload_1 
    17: ladd 
    18: lstore_3 
    19: lload 5 
    21: lstore_1 
    22: goto 4 
    25: lload_3 
    26: lreturn 

public static long recursive_fib(int); 
    Code: 
    0: iload_0 
    1: iconst_2 
    2: if_icmpgt  7 
    5: lconst_1 
    6: lreturn 
    7: iload_0 
    8: iconst_1 
    9: isub 
    10: invokestatic #13; //Method recursive_fib:(I)J 
    13: iload_0 
    14: iconst_2 
    15: isub 
    16: invokestatic #13; //Method recursive_fib:(I)J 
    19: ladd 
    20: lreturn 

를 참조 -c은 javap로 생성 된 바이트 코드를 보면 처음에는 더 오래 걸립니다. 그러나 'n'이 흥미로운 크기 인 경우 올바르지 않습니다.

내 컴퓨터에서 FibMain 44를 실행했는데 다음과 같은 결과가 나타납니다.

701408733 
Iteration took 495 us 
701408733 
Recursion took 19,174,036 us 

반복을 수행하기 위해 걸리는 시간은 (이 경우 701,408,733에서) 재귀 걸리는 시간은 결과에 비례하지만 선형 증가 광고 (여기서는 44) N에 비례하고이 성장하기 때문이다 기하 급수적으로.

입력으로 50 번 시도하면 깜박임으로 첫 번째로 완료되고, 두 번째 입력은 기다리는 시간이 너무 길어집니다.

Answer 2

(1) 왜 프로세스 실행 시간을 정하지 않으려합니까? 프로세스를 시작하는 것보다 실제 처리가 타이밍에서 가장 우세한 부분이되도록 퍼즐을 처리하고 평균을 얻기 위해 여러 번 반복해야합니다.

(2) 샘플 입력을 제공하지만 실제 컨테스트에는 대체 입력을 사용하십시오.

Answer 3

(2)와 마찬가지로 프로그래밍 컨테스트에서 일반적으로 사용되는 솔루션 (정확성 만 계산하는 경우)은 제한된 수의 예제 입력을 제공하지만 판단 시스템에서보다 포괄적 인 테스트 세트를 사용합니다.

(3)과 같이 사용 된 JVM 명령어의 수는 반드시 속도에 대한 좋은 척도는 아닙니다. 일부 구현은 각 명령어에 대해 더 길거나 짧을 수 있습니다. jitting 및 기타 최적화 작업을 시작하지도 않았습니다.

Answer 4

사람들은 자신의 코드를 제출하고 성능 결과 및 가장 빠른 속도 결과가 표시된 전자 메일을받을 수있는 autograder 형식 테스트 사이트를 구현할 수 있습니다. 그들은 입력을 얻지 못할 것이지만 공식 JVM이 생산할 결과를 얻을 것이다. 악용을 방지하려면 클래스 로더를 수정하여 나가는 연결 유형 항목을로드하지 않도록하고 성능 테스터를 주소 당 하루에 하나의 제출 또는 일부 다른 전략으로 제한하십시오.

Answer 5

가비지 수집기를 올바르게 제어하려면 아마도 realtime JVM을 사용해야합니다. 가비지 수집기가 실행되는 동안 한 경쟁자가 더 긴 런타임을 표시하면 불공정합니다.

Answer 6

유일한 실제적인 하드웨어의 시간입니다. 컴파일러는 실행 된 명령 개수가 아닌 시간에 최적화되므로 지침을 세면 많은 최적화가 실패하고 그 중 일부는 비관적이게됩니다. 명령은 다른 시간 량을 취할뿐만 아니라 예를 들어, 메모리 액세스는 크게 다를 수 있습니다.

Answer 7

다른 하드웨어 구성 관리 및 벤치 마크 & 유효성 검사 절차와 관련하여 FastCode을 보면 이러한 경쟁에 필요한 것을 많이 배울 수 있습니다.

Answer 8

VJM을 한 단계 더 발전시키고 전체 Linux 기반 VM을 구현하지 않는 이유는 무엇입니까? 클럭주기는 동일해야합니다 (VM 구현 방법에 따라 달라질 수 있습니다).

예를 들어 MINUX를 실행하는 256KB RAM 및 5MB 디스크 공간이있는 8088을 기반으로 VM을 만들 수 있습니다. 코드가 얼마나 빨리 실행되는지에 관계없이 8088이 실제로 Pentium Dual Core 또는 일부 구형 Power PC에 구현되었는지 여부에 관계없이 CPU주기 수가 동일하게 유지됩니다 (8088에 비해).

일단 가상 하드웨어를 설정하면 언어 선택이 "가장 빠른 알고리즘"경연 대회의 솔루션 부분이 될 수 있습니다.

Answer 9

또한 지침 수를 계산하는 것이 좋은 방법이라고 생각합니다.

내가보기에 유일한 단점은 JVM 명령어가 너무 강력하다는 것입니다. 나는 JVC를 모른다. 그러나 문자열에 대한 네이티브 지원이 가능할 수도있다. 문자열을 추가하면 은 일 수 있습니다. (그렇게 생각하지 마십시오.)

난 그냥 평범한 옛 time 명령을 사용하고 싶습니다. 이것은 실행 시간을 측정합니다. 을 거의 제거하지 않는 실시간은 백그라운드 프로세스에 의한 모든 영향이입니다.

Answer 10

SPOJ과 같은 온라인 도구로 경쟁을 할 수 있습니다 (이 제품은 무료이며 Java를 지원합니다). 이 방법을 사용하면 프로그램의 실행 시간을 측정하는 하나의 참조 컴퓨터가 있습니다.