Od dawna mam zrobione to zadanko ale o czasie aż 0.01 .
czy postarać się włożyć ciało funkcji do maih?
C++ 
- Rejestracja:około 8 lat
- Ostatnio:minuta
- Postów:4888
0
Tak, chociaz, ciekawe czy Miller-Rabin by dal rade.
2
Co do zasady, wspóczesne kompilatory są na tyle sprytne, że się zorientują, czy inline’owanie funkcji w prostych programach ma sens, czy nie, bez ręcznej interwencji.
Spróbować można, ale początkujący mają potężną tendencję do przeceniania wpływu takich mikrooptymalizacji…
- Rejestracja:prawie 6 lat
- Ostatnio:około 3 godziny
- Lokalizacja:Kraków
- Postów:639
0
Możesz też zamiast przenosić kod z funkcji do funkcji wywołującej po prostu nadać tej funkcji kwalifikator inline co powinno spowodować to samo (chociaż zdarza się że niektóre kompilatory ignorują ten kwalifikator) mimo że logicznie w kodzie źródłowym funkcja pozostanie odrębną funkcją.
- Rejestracja:ponad 9 lat
- Ostatnio:dzień
- Postów:1082
1
Ja jeszcze dodam do wypowiedzi @Althorion że takie mikrooptymalizacje (w ogólności) mają tyle samo sensu co dyskusja czy i++ vs ++i. Oczywiście przy 1 000 000 000 000 wywołań 1 linijkowej funkcji może mieć znaczenie do ogólnej wydajności.
W tym przypadku pewnie problem jest gdzieś indziej. Spoj jak to spoj, tutaj czasami nawet do zaliczenia zadania wymagane będzie odprawianie magii na IO celem zmieszczenia się w limitach. Swoją drogą 0.01 to nie jest zły wynik. Algorytm zapewne masz optymalny. Musisz szukać w Fast I/O. Jest tam parę tematów na forum.
- Rejestracja:ponad 6 lat
- Ostatnio:około 2 godziny
- Postów:699
0
sig napisał(a):
O ile dobrze pamiętam, w tym zadaniu da się stworzyć tablicę bool i "wpakować" do niej co jest liczbą pierwszą a co nie. Żadnych funkcji nie trzeba
Niedawno się zastanawiałem patrząc na zadania na spoj jakie tam jest podejście do używania lookup table. Czy temat prowokował jakieś debaty.
- Rejestracja:około 17 lat
- Ostatnio:minuta
1
#include <iostream>
#include <array>
#include <exception>
template<size_t N>
class EratostenesSive
{
public:
constexpr EratostenesSive()
{
oddPrimes[0] = false;
for(size_t i = 1; i < (N + 1) / 2; ++i) oddPrimes[i] = true;
for (size_t p = 3; p * p <= N; p += 2) {
if (oddPrimes[p/2]) {
for (size_t i = p * p; i <= N; i += 2 * p) {
oddPrimes[i/2] = false;
}
}
}
}
constexpr bool isPrime(size_t x) const
{
if (x < 2) return false;
if (x == 2) return true;
if (x > max()) throw std::invalid_argument("Sive limit reached");
return x%2 != 0 && oddPrimes[x/2];
}
constexpr size_t max() const {
return N | 1;
}
private:
bool oddPrimes[(N + 1) / 2] = {};
};
constexpr auto primes = EratostenesSive<100000>{};
int main()
{
static constexpr const char* const boolDesc[] {
"NIE\n",
"TAK\n",
};
size_t x, n;
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
while (n-- && std::cin >> x) {
std::cout << boolDesc[primes.isPrime(x)];
}
return 0;
}
Takie coś, operate o constexpr kompiluje się jako C++14 clang 8.0 i gcc 8.3.
Ergo ładna look up table obliczana w trakcie kompilacji.
Niestarty uzyskuje zwykle czas 0.02 a jedno uruchomianie dało 0.01.
Żeby uzyskać 0.00 stawiam na jakiś jakieś optymalizacje operacji IO, względnie szczęście podczas pomiaru czasu (na SPOJ jest spoko LeetCode pot tym względem to tragedia).
Dzięki za przypomnienie dlaczego C++ powinien zostać zdelegalizowany.
i++i++ioptymalizuje się do tego samego