[C#] 컴파일 타임에 1 + 2 + 3 +… + 1000을 계산하기 위해 C #, C ++ 또는 Java 컴파일러를 구동하는 방법은 무엇입니까?

최근 인터뷰에서 정말 이상한 질문을 받았습니다. 면접관은 컴파일러 기능을 사용하여 어떻게 1 + 2 + 3 + … + 1000을 계산할 수 있는지 물었습니다. 즉, 프로그램을 작성하고 실행할 수는 없지만 컴파일 중에이 합계를 계산하고 컴파일이 완료되면 결과를 인쇄하도록 컴파일러를 구동 할 수있는 프로그램을 작성해야합니다. 힌트로 그는 컴파일러의 제네릭 및 전 처리기 기능을 사용할 수 있다고 말했습니다. C ++, C # 또는 Java 컴파일러를 사용할 수 있습니다. 어떤 아이디어 ???

이 질문은 여기에서 요청한 루프없이 합계를 계산하는 것과 관련이 없습니다 . 또한 합계는 컴파일 중에 계산되어야합니다. C ++ 컴파일러 지시문을 사용하여 결과 만 인쇄하는 것은 허용되지 않습니다.


게시 된 답변에 대해 더 많이 읽으면서 C ++ 템플릿을 사용하여 컴파일하는 동안 문제를 해결하는 것이 메타 프로그래밍 이라는 것을 알았습니다 . 이것은 C ++ 언어를 표준화하는 과정에서 Erwin Unruh 박사가 우연히 발견 한 기술입니다. 이 주제에 대한 자세한 내용 은 메타 프로그래밍의 위키 페이지 에서 읽을 수 있습니다 . Java 주석을 사용하여 Java로 프로그램을 작성할 수있는 것 같습니다. 아래 에서 maress의 답변을 볼 수 있습니다 .

C에서 메타 프로그래밍 ++에 대한 좋은 책은 이것 . 관심이 있다면 살펴볼 가치가 있습니다.

유용한 C ++ 메타 프로그래밍 라이브러리는 Boost의 MPL this link 입니다.



답변

향상된 재귀 깊이로 지금 업데이트 되었습니다! 깊이를 높이 지 않고 MSVC10 및 GCC에서 작동합니다. 🙂


간단한 컴파일 타임 재귀 + 추가 :

template<unsigned Cur, unsigned Goal>
struct adder{
  static unsigned const sub_goal = (Cur + Goal) / 2;
  static unsigned const tmp = adder<Cur, sub_goal>::value;
  static unsigned const value = tmp + adder<sub_goal+1, Goal>::value;
};

template<unsigned Goal>
struct adder<Goal, Goal>{
  static unsigned const value = Goal;
};

테스트 코드 :

template<unsigned Start>
struct sum_from{
  template<unsigned Goal>
  struct to{
    template<unsigned N>
    struct equals;

    typedef equals<adder<Start, Goal>::value> result;
  };
};

int main(){
  sum_from<1>::to<1000>::result();
}

GCC에 대한 출력 :

오류 : ‘struct sum_from <1u> :: to <1000u> :: equals <500500u>’선언

Ideone의 라이브 예 .

MSVC10의 출력 :

error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors
      with
      [
          Start=1,
          Goal=1000,
          Result=500500
      ]


답변

컴파일 타임에 오류에 대한 C # 예제.

class Foo
{
    const char Sum = (1000 + 1) * 1000 / 2;
}

다음 컴파일 오류를 생성합니다.

Constant value '500500' cannot be converted to a 'char' 


답변

컴파일하는 동안이 합계를 계산하고 컴파일이 완료되면 결과를 인쇄하도록 컴파일러를 구동 할 수있는 프로그램을 작성해야합니다.

컴파일 중에 숫자를 인쇄하는 인기있는 트릭은 인쇄하려는 숫자로 인스턴스화 된 템플릿의 존재하지 않는 구성원에 액세스하려고하는 것입니다.

template<int> struct print_n {};

print_n<1000 * 1001 / 2>::foobar go;

그런 다음 컴파일러는 다음과 같이 말합니다.

error: 'foobar' in 'struct print_n<500500>' does not name a type

이 기법에 대한 더 흥미로운 예는 컴파일 타임에 8 개의 퀸 문제 해결을 참조 하십시오 .


답변

인터뷰 질문에 컴파일러도 언어도 지정되지 않았기 때문에 GHC를 사용하여 Haskell에 솔루션을 제출할 수 있습니다.

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices #-}
module Main where

main :: IO ()
main = print $(let x = sum [1 :: Int .. 1000] in [| x |])

컴파일 :

$ ghc compsum.hs
[1 of 1] Compiling Main             ( compsum.hs, compsum.o )
Loading package ghc-prim ... linking ... done.
<snip more "Loading package ..." messages>
Loading package template-haskell ... linking ... done.
compsum.hs:6:16-56: Splicing expression
    let x = sum [1 :: Int .. 1000] in [| x |] ======> 500500
Linking compsum ...

그리고 우리는 또한 작동하는 프로그램을 얻었습니다.


답변

constexpr현재 gcc 4.6 이상에서만 지원되지만 컴파일 시간 계산을위한 함수를 추가하는 C ++ 11을 사용하면 삶이 훨씬 더 쉬워 질 것 입니다.

constexpr unsigned sum(unsigned start, unsigned end) {
    return start == end ? start :
        sum(start, (start + end) / 2) +
        sum((start + end) / 2 + 1, end);
}

template <int> struct equals;
equals<sum(1,1000)> x;

표준은 컴파일러가 512의 재귀 깊이를 지원하도록 요구하므로 여전히 선형 재귀 깊이를 피해야합니다. 출력은 다음과 같습니다.

$ g++-mp-4.6 --std=c++0x test.cpp -c
test.cpp:8:25: error: aggregate 'equals<500500> x' has incomplete type and cannot be defined

물론 다음 공식을 사용할 수 있습니다.

constexpr unsigned sum(unsigned start, unsigned end) {
    return (start + end) * (end - start + 1) / 2;
}

// static_assert is a C++11 assert, which checks
// at compile time.
static_assert(sum(0,1000) == 500500, "Sum failed for 0 to 1000");


답변

Java에서는 주석 처리 사용에 대해 생각했습니다. apt 도구는 소스 파일을 실제로 javac 명령으로 구문 분석하기 전에 소스 파일을 스캔합니다.

소스 파일을 컴파일하는 동안 출력이 인쇄됩니다.

@Documented
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.TYPE, ElementType.METHOD})
public @interface MyInterface {

    int offset() default 0;

    int last() default 100;
}

프로세서 공장 :

public class MyInterfaceAnnotationProcessorFactory implements AnnotationProcessorFactory {

    public Collection<String> supportedOptions() {
        System.err.println("Called supportedOptions.............................");
        return Collections.EMPTY_LIST;
    }

    public Collection<String> supportedAnnotationTypes() {
        System.err.println("Called supportedAnnotationTypes...........................");
        return Collections.singletonList("practiceproject.MyInterface");
    }

    public AnnotationProcessor getProcessorFor(Set<AnnotationTypeDeclaration> set, AnnotationProcessorEnvironment ape) {
        System.err.println("Called getProcessorFor................");
        if (set.isEmpty()) {
            return AnnotationProcessors.NO_OP;
        }
        return new MyInterfaceAnnotationProcessor(ape);
    }
}

실제 주석 프로세서 :

public class MyInterfaceAnnotationProcessor implements AnnotationProcessor {

    private AnnotationProcessorEnvironment ape;
    private AnnotationTypeDeclaration atd;

    public MyInterfaceAnnotationProcessor(AnnotationProcessorEnvironment ape) {
        this.ape = ape;
        atd = (AnnotationTypeDeclaration) ape.getTypeDeclaration("practiceproject.MyInterface");
    }

    public void process() {
        Collection<Declaration> decls = ape.getDeclarationsAnnotatedWith(atd);
        for (Declaration dec : decls) {
            processDeclaration(dec);
        }
    }

    private void processDeclaration(Declaration d) {
        Collection<AnnotationMirror> ams = d.getAnnotationMirrors();
        for (AnnotationMirror am : ams) {
            if (am.getAnnotationType().getDeclaration().equals(atd)) {
                Map<AnnotationTypeElementDeclaration, AnnotationValue> values = am.getElementValues();
                int offset = 0;
                int last = 100;
                for (Map.Entry<AnnotationTypeElementDeclaration, AnnotationValue> entry : values.entrySet()) {
                    AnnotationTypeElementDeclaration ated = entry.getKey();
                    AnnotationValue v = entry.getValue();
                    String name = ated.getSimpleName();
                    if (name.equals("offset")) {
                        offset = ((Integer) v.getValue()).intValue();
                    } else if (name.equals("last")) {
                        last = ((Integer) v.getValue()).intValue();
                    }
                }
                //find the sum
                System.err.println("Sum: " + ((last + 1 - offset) / 2) * (2 * offset + (last - offset)));
            }
        }
    }
}

그런 다음 소스 파일을 만듭니다. MyInterface 주석을 사용하는 간단한 클래스 :

 @MyInterface(offset = 1, last = 1000)
public class Main {

    @MyInterface
    void doNothing() {
        System.out.println("Doing nothing");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Main m = new Main();
        m.doNothing();
        MyInterface my = (MyInterface) m.getClass().getAnnotation(MyInterface.class);
        System.out.println("offset: " + my.offset());
        System.out.println("Last: " + my.last());
    }
}

주석 프로세서는 jar 파일로 컴파일되고 apt 도구는 소스 파일을 다음과 같이 컴파일하는 데 사용됩니다.

apt -cp "D:\Variance project\PracticeProject\dist\practiceproject.jar" -factory practiceproject.annotprocess.MyInterfaceAnnotationProcessorFactory "D:\Variance project\PracticeProject2\src\practiceproject2\Main.java"

프로젝트의 결과 :

Called supportedAnnotationTypes...........................
Called getProcessorFor................
Sum: 5000
Sum: 500500


답변

다음은 VC ++ 2010에서 작동하는 구현입니다. 템플릿이 500 회 이상 반복 될 때 컴파일러가 불평했기 때문에 계산을 3 단계로 나눠야했습니다.

template<int t_startVal, int t_baseVal = 0, int t_result = 0>
struct SumT
{
    enum { result = SumT<t_startVal - 1, t_baseVal, t_baseVal + t_result +
        t_startVal>::result };
};

template<int t_baseVal, int t_result>
struct SumT<0, t_baseVal, t_result>
{
    enum { result = t_result };
};

template<int output_value>
struct Dump
{
    enum { value = output_value };
    int bad_array[0];
};

enum
{
    value1 = SumT<400>::result,                // [1,400]
    value2 = SumT<400, 400, value1>::result,   // [401, 800]
    value3 = SumT<200, 800, value2>::result    // [801, 1000]
};

Dump<value3> dump;

이것을 컴파일 할 때 다음과 같은 컴파일러의 출력을 볼 수 있습니다.

1>warning C4200: nonstandard extension used : zero-sized array in struct/union
1>          Cannot generate copy-ctor or copy-assignment operator when UDT contains a
zero-sized array
1>          templatedrivensum.cpp(33) : see reference to class template
instantiation 'Dump<output_value>' being compiled
1>          with
1>          [
1>              output_value=500500
1>          ]