W niedawnym wywiadzie zadano mi naprawdę dziwne pytanie. Prowadzący wywiad zapytał mnie, jak mogę obliczyć 1 + 2 + 3 + ... + 1000 używając tylko funkcji kompilatora. Oznacza to, że nie wolno mi pisać programu i wykonywać go, ale powinienem po prostu napisać program, który mógłby zmusić kompilator do obliczenia tej sumy podczas kompilacji i wydrukować wynik po zakończeniu kompilacji. Jako wskazówkę, powiedział mi, że mogę używać generycznych i preprocesorowych funkcji kompilatora. Możliwe jest użycie kompilatora C ++, C # lub Java. Jakieś pomysły???
To pytanie nie jest związane z obliczaniem sumy bez zadanych tu pętli . Dodatkowo należy zaznaczyć, że suma POWINNA zostać obliczona podczas kompilacji. Drukowanie samego wyniku przy użyciu dyrektyw kompilatora C ++ jest niedopuszczalne.
Czytając więcej o zamieszczonych odpowiedziach, stwierdziłem, że rozwiązywanie problemów podczas kompilacji przy użyciu szablonów C ++ nazywa się metaprogramowaniem . Jest to technika, która została przypadkowo odkryta przez dr Erwina Unruha podczas procesu standaryzacji języka C ++. Możesz przeczytać więcej na ten temat na stronie wiki o metaprogramowaniu . Wygląda na to, że można napisać program w Javie przy użyciu adnotacji java. Możesz rzucić okiem na odpowiedź maress poniżej.
Ładna książka o metaprogramowaniu w C ++ to właśnie ta . Warto zajrzeć, jeśli jesteś zainteresowany.
Użyteczną biblioteką metaprogramowania C ++ jest MPL Boost'a ten link .
const int value = 1 + 2 + 3.... + 1000; Console.WriteLine(value);
; POdpowiedzi:
Zaktualizowano teraz z poprawioną głębią rekurencji! Działa na MSVC10 i GCC bez zwiększonej głębokości. :)
Prosta rekurencja w czasie kompilacji + dodawanie:
Kod testowy:
Wyjście dla GCC:
Przykład na żywo w Ideone .
Wyjście dla MSVC10:
źródło
C # przykład błędu w czasie kompilacji.
Powoduje następujący błąd kompilacji:
źródło
Popularną sztuczką drukowania liczby podczas kompilacji jest próba uzyskania dostępu do nieistniejącego elementu szablonu, którego instancja ma numer, który chcesz wydrukować:
Następnie kompilator mówi:
Aby uzyskać bardziej interesujący przykład tej techniki, zobacz Rozwiązywanie problemu z ośmioma królowymi w czasie kompilacji .
źródło
print_n
pozostać niezdefiniowanym, zobacz moją odpowiedź.Ponieważ w pytaniu wywiadowym nie podano ani kompilatora, ani języka, ośmielam się przedstawić rozwiązanie w Haskellu z użyciem GHC:
Skompiluj to:
Mamy też program roboczy.
źródło
Życie będzie dużo łatwiejsze z C ++ 11, który dodaje
constexpr
funkcje do obliczania czasu kompilacji, chociaż obecnie są one obsługiwane tylko przez gcc 4.6 lub nowsze.Standard wymaga tylko, aby kompilator obsługiwał głębokość rekursji równą 512, więc nadal musi unikać głębokości rekursji liniowej. Oto wynik:
Oczywiście możesz po prostu użyć wzoru:
źródło
constexpr
na chwilę zupełnie o nim zapomniałem . Może po prostu za bardzo kocham szablony. :(/ 2
obsłużenie pełnego zakresu możliwychunsigned
wyników, wartość, którą przesuwasz w prawo, musiałaby mieć szerokość n + 1 bitów, ale tak nie jest. Aby tego uniknąć, można zmienić kolejność formuły, tak jak robi to clang w przypadku zakresów zmiennych czasu wykonywania: godbolt.org/z/dUGXqg pokazuje, że clang zna formułę zamkniętą i używa jej do optymalizacjitotal += i
pętli.W Javie myślałem o przetwarzaniu adnotacji. Narzędzie apt skanuje plik źródłowy przed faktycznym przeanalizowaniem pliku źródłowego do polecenia javac.
Podczas kompilacji plików źródłowych wynik zostanie wydrukowany:
Fabryka procesorów:
Rzeczywisty procesor adnotacji:
Następnie tworzymy plik źródłowy. prosta klasa korzystająca z adnotacji MyInterface:
Procesor adnotacji jest kompilowany do pliku jar, a następnie narzędzie apt jest używane do kompilowania pliku źródłowego jako:
Wyniki projektu:
źródło
Oto implementacja, która działa pod VC ++ 2010. Musiałem podzielić obliczenia na 3 etapy, ponieważ kompilator skarżył się, gdy szablony powtarzały się ponad 500 razy.
Kiedy to kompilujesz, powinieneś zobaczyć następujące dane wyjściowe kompilatora, mniej więcej tak:
źródło
Czuję się zobowiązany do podania tego kodu w C, ponieważ nikt inny jeszcze nie:
A wszystko, co muszę zrobić, to sprawdzić montaż, aby znaleźć odpowiedź!
I widzę:
źródło
x
byłby globalny, kompilator byłby (mniej więcej) wymagany do oceny wyrażenia w czasie kompilacji. ISO C nie zezwala na inicjowanie zmiennych środowiska uruchomieniowego dla globalnych. Oczywiście konkretna implementacja może wyemitować wywołanie funkcji static-init podobnej do konstruktora, która oblicza ją w czasie wykonywania i magazynach. Ale ISO C pozwala na użycie stałych czasu kompilacji jako rozmiarów tablic (jakint y[x];
na przykład w definicji struktury lub innej globalnej), więc każda hipotetyczna pesymizująca implementacja nadal musiałaby to obsługiwać.Rozszerzony na podstawie odpowiedzi Carla Walsha, aby faktycznie wydrukować wynik podczas kompilacji:
wyjścia gcc:
źródło
Możesz używać (i głównie nadużywać) makr / szablonów C ++ do wykonywania metaprogramowania . AFAIK, Java nie pozwala na takie rzeczy.
źródło
Teoretycznie możesz użyć tego:
(na podstawie kodu opublikowanego przez Xeo). Ale GCC daje mi ten błąd:
plus ogromny pseudo-ślad stosu.
źródło
Używając javy możesz zrobić coś podobnego do odpowiedzi w C #:
możesz to zrobić w scali, używając liczb peano ponieważ możesz zmusić kompilator do wykonywania rekursji, ale nie sądzę, że możesz zrobić to samo w c # / java
inne rozwiązanie nie używające -Xprint, ale jeszcze bardziej podejrzane
bez użycia jakichkolwiek flag kompilatora. ponieważ możesz sprawdzić dowolną liczbę stałych (nie tylko 500500), to rozwiązanie powinno być akceptowalne.
źródło
500500
.for (i = 0; i < 100000; ++i) {if (i == 1000*1000/2) print i}
. mam plik java 160mb, który to robi i działa :)Chociaż faktycznie działa to z małymi liczbami, clang ++ zwraca mi błąd kompilatora, jeśli używam sum_first, gdzie N> 400.
źródło