Значительное замедление выполнения кода на C++

Question

Так что я должен решить одну проблему USACO, связанную с вычислением всех простых чисел < = 100M и печать этих из них, которые являются палиндромами, в то время как ограничения составляют 16 МБ памяти и 1 секунду времени выполнения. Поэтому мне пришлось сделать много оптимизаций. Пожалуйста, обратите внимание на следующий блок кода:

for(int i = 0; i < all.size(); ++i) 
    { 
     if(all[i] < a) continue; 
     else if(all[i] > b) break; 
     if(isPrime(all[i])) 
     { 
      char buffer[50]; 
      //toString(all[i], buffer); 
      int c = all[i]; 
      log10(2); 
      buffer[3] = 2; 
      //buffer[(int)log10(all[i])+1] = '\n'; 
      //buffer[(int)log10(all[i])+2] = '\0'; 
      //fputs(buffer, pFile); 
     } 
    } 

Теперь он выполняет в удовлетворяющем диапазоне 0,5 сек, но когда я изменяю log10(2) к log10(all[i]) он взлетает почти до 2 секунд! Без видимой причины. Я назначаю все [i] переменной c, и это не замедляет выполнение вообще, но когда я передаю все [i] как параметр, это делает код в 4 раза медленнее! Любые идеи, почему это происходит и как я могу это исправить?

Всего код:

/* 
ID: xxxxxxxx 
PROG: pprime 
LANG: C++11 
*/ 
#include <fstream> 
#include <iostream> 
#include <vector> 
#include <queue> 
#include <stack> 
#include <set> 
#include <string> 
#include <cstring> 
#include <algorithm> 
#include <list> 
#include <ctime> 
#include <cstdio> 
using namespace std; 

typedef struct number Number; 
ifstream fin("pprime.in"); 
ofstream fout("pprime.out"); 
int MAXN = 100000000; 
unsigned short bits[2000000] = {}; 
vector<int> primes; 
vector<int> all; 
int a, b; 
short getBit(int atPos) 
{ 
    int whichNumber = (atPos-1)/16; 
    int atWhichPosInTheNumber = (atPos-1) % 16; 
    return ((bits[whichNumber] & (1 << atWhichPosInTheNumber)) >> atWhichPosInTheNumber); 
} 

void setBit(int atPos) 
{ 
    int whichNumber = (atPos-1)/16; 
    int atWhichPosInTheNumber = (atPos-1) % 16; 
    int old = bits[whichNumber]; 
    bits[whichNumber] = bits[whichNumber] | (1 << atWhichPosInTheNumber); 
} 

void calcSieve() 
{ 
    for(int i = 2; i < MAXN; ++i) 
    { 
     if(getBit(i) == 0) 
     { 
      for(int j = 2*i; j <= (MAXN); j += i) 
      { 
       setBit(j); 
      } 
      primes.push_back(i); 
     } 
    } 
} 
int toInt(list<short> integer) 
{ 
    int number = 0; 
    while(!integer.empty()) 
    { 
     int current = integer.front(); 
     integer.pop_front(); 
     number = number * 10 + current; 
    } 
    return number; 
} 
void toString(int number, char buffer[]) 
{ 
    int i = 0; 
    while(number != 0) 
    { 
     buffer[i] = number % 10 + '0'; 
     number /= 10; 
    } 
} 
void DFS(list<short> integer, int N, int atLeast) 
{ 
    if(integer.size() > N) 
    { 
     return; 
    } 
    if(!(integer.size() > 0 && (integer.front() == 0 || integer.back() % 2 == 0)) && atLeast <= integer.size()) 
    { 
     int toI = toInt(integer); 
     if(toI <= b) all.push_back(toInt(integer)); 
    } 

    for(short i = 0; i <= 9; ++i) 
    { 
     integer.push_back(i); 
     integer.push_front(i); 
     DFS(integer, N, atLeast); 
     integer.pop_back(); 
     integer.pop_front(); 
    } 
} 
bool isPrime(int number) 
{ 
    for(int i = 0; i < primes.size() && number > primes[i]; ++i) 
    { 
     if(number % primes[i] == 0) return false; 
    } 
    return true; 
} 
int main() 
{ 
    int t = clock(); 
    ios::sync_with_stdio(false); 
    fin >> a >> b; 
    MAXN = min(MAXN, b); 
    int N = (int)log10(b) + 1; 
    int atLeast = (int)log10(a) + 1; 
    for(short i = 0; i <= 9; ++i) 
    { 
     list<short> current; 
     current.push_back(i); 
     DFS(current, N, atLeast); 
    } 
    list<short> empty; 
    DFS(empty, N, atLeast); 
    sort(all.begin(), all.end()); 
    //calcSieve 
    calcSieve(); 
    // 


    string output = ""; 
    int ends = clock() - t; 
    cout<<"Exexution time: "<<((float)ends)/CLOCKS_PER_SEC<<" seconds"; 
    cout<<"\nsize: "<<all.size()<<endl; 
    FILE* pFile; 
    pFile = fopen("pprime.out", "w"); 


    for(int i = 0; i < all.size(); ++i) 
    { 
     if(all[i] < a) continue; 
     else if(all[i] > b) break; 
     if(isPrime(all[i])) 
     { 
      char buffer[50]; 
      //toString(all[i], buffer); 
      int c = all[i]; 
      log10(c); 
      buffer[3] = 2; 
      //buffer[(int)log10(all[i])+1] = '\n'; 
      //buffer[(int)log10(all[i])+2] = '\0'; 
      //fputs(buffer, pFile); 
     } 
    } 

    ends = clock() - t; 
    cout<<"\nExexution time: "<<((float)ends)/CLOCKS_PER_SEC<<" seconds"; 
    ends = clock() - t; 
    cout<<"\nExexution time: "<<((float)ends)/CLOCKS_PER_SEC<<" seconds"; 
    fclose(pFile); 
    //fout<<output; 

    return 0; 
} 

Answer 1

Я думаю, что вы сделали это в обратном направлении. Кажется странным генерировать все возможные палиндромы (если это то, что на самом деле делает DFS ... эта функция меня смущает), а затем проверьте, какие из них являются первичными. Тем более, что вам все равно нужно генерировать простые числа.

Другое дело, что вы выполняете линейный поиск в isPrime, который не использует тот факт, что массив отсортирован. Вместо этого используйте двоичный поиск.

А также, используя list вместо vector для вашей функции DFS повредит ваше время выполнения. Попробуйте использовать deque.

Теперь, все, что сказал, я думаю, что вы должны сделать это наоборот. Существует огромное количество палиндромов, которые не будут первыми. В чем смысл их генерации? Простой стек - это все, что вам нужно, чтобы проверить, является ли число палиндром. Как это:

bool IsPalindrome(unsigned int val) 
{ 
    int digits[10]; 
    int multiplier = 1; 
    int *d = digits; 

    // Add half of number's digits to a stack 
    while(multiplier < val) { 
     *d++ = val % 10; 
     val /= 10; 
     multiplier *= 10; 
    } 

    // Adjust for odd-length palindrome 
    if(val * 10 < multiplier) --d; 

    // Check remaining digits 
    while(val != 0) { 
     if(*(--d) != val % 10) return false; 
     val /= 10; 
    } 

    return true; 
} 

Это исключает необходимость вызова log10 вообще, а также устраняет все, что поколение палиндром. Сито довольно быстро, и после этого у вас будет всего несколько тысяч простых чисел для тестирования, большинство из которых не будут палиндромами.

Теперь вся ваша программа становится чем-то вроде этого:

calcSieve(); 
for(vector<int>::iterator it = primes.begin(); it != primes.end(); it++) { 
    if(IsPalindrome(*it)) cout << *it << "\n"; 
} 

Еще одна вещь, чтобы указать. Две вещи, на самом деле:

int MAXN = 100000000; 
unsigned short bits[2000000] = {}; 

1. bits слишком коротка, чтобы представить 100 миллионов флагов.
2. bits неинициализирован.

Для решения обеих этих проблем, попробуйте:

unsigned short bits[1 + MAXN/16] = { 0 };