Возможные оптимизации для алгоритма Project Euler # 4

Идеи см. здесь

В C ++ я делаю так:

int euler004()
    {
    // A palindromic number reads the same both ways. The largest palindrome
    // made from the product of two 2-digit numbers is 9009 = 91  99.
    // Find the largest palindrome made from the product of two 3-digit numbers.
    const int N=3;
    const int N2=N<<1;
    int min,max,a,b,c,i,j,s[N2],aa=0,bb=0,cc=0;
    for (min=1,a=1;a<N;a++) min*=10; max=(min*10)-1;
    i=-1;
    for (a=max;a>=min;a--)
     for (b=a;b>=min;b--)
        {
        c=a*b; if (c<cc) continue;
        for (j=c,i=0;i<N2;i++) { s[i]=j%10; j/=10; }
        for (i=0,j=N2-1;i<j;i++,j--)
         if (s[i]!=s[j]) { i=-1; break; }
        if (i>=0) { aa=a; bb=b; cc=c; }
        }
    return cc; // cc is the output
    }

• нет необходимости в sqrt ...
• подвызов createPalindrome может замедлить работу из-за мусора кучи / стека
• манипуляции со строками m = str(m) + str(m)[::-1] медленные
• преобразование строки в int может быть быстрее, если вы сделаете это самостоятельно на массиве фиксированного размера
• моя реализация занимает около 1,7 мс, но большая часть этого времени - это вывод и форматирование приложения (32-битное приложение AMD 3,2 ГГц на W7 x64) ...

[edit1] реализация вашей формулы

int euler004()
    {
    int i,c,cc,c0,a,b;
    for (cc=0,i=999,c0=1100*i;i>=100;i--,c0-=1100)
        {
        c=c0-(990*int(i/10))-(99*int(i/100));
        for(a=999;a>=300;a--)
         if (c%a==0)
            {
            b=c/a;
            if ((b>=100)&&(b<1000)) { cc=c; i=0; break; }
            }
        }
    return cc;
    }

• это занимает ~ 0,4 мс

[edit2] дальнейшие оптимизации

//---------------------------------------------------------------------------
int euler004()
    {
    // A palindromic number reads the same both ways. The largest palindrome
    // made from the product of two 2-digit numbers is 9009 = 91  99.
    // Find the largest palindrome made from the product of two 3-digit numbers.
    int i0,i1,i2,c0,c1,c,cc=0,a,b,da;
    for (c0=  900009,i0=9;i0>=1;i0--,c0-=100001)    // first digit must be non zero so <1,9>
    for (c1=c0+90090,i1=9;i1>=0;i1--,c1-= 10010)    // all the rest <0,9>
    for (c =c1+ 9900,i2=9;i2>=0;i2--,c -=  1100)    // c is palindrome from 999999 to 100001
     for(a=999;a>=948;a-- )
      if (c%a==0)
        {
        // biggest palindrome is starting with 9
        // so smallest valid result is 900009
        // it is odd and sqrt(900009)=948 so test in range <948,999>
        b=c/a;
        if ((b>=100)&&(b<1000)) { cc=c; i0=0; i1=0; i2=0; break; }
        }
    return cc;
    }
//---------------------------------------------------------------------------

• это слишком быстро для меня, чтобы правильно измерить время (необработанное время составляет около 0,037 мс)
• удалены деления и умножения из генерации палиндрома
• изменил диапазоны после некоторого числового анализа и размышлений в ожидании автобуса
• первый цикл можно исключить (результат начинается с 9)

Кажется, что самое большое замедление в моем коде - это преобразование целого числа в строку, добавление ее обратного и преобразование результата обратно в целое число.

Я поискал дополнительную информацию о палиндромах и наткнулся на эту формулу, которая позволяет мне преобразовать 3-значное число «n» в 6-значное палиндром «p» (может быть адаптировано для других цифр, но меня это не беспокоит. ).

p = 1100*n−990*⌊n/10⌋−99*⌊n/100⌋

Мой исходный код выполняется примерно за 0,75 мс, а новый занимает практически такое же количество времени (не говоря уже о том, что формулу пришлось бы адаптировать в зависимости от количества цифр «n»), поэтому я предполагаю, что их было не так много осталось выполнить оптимизацию.

Я написал это некоторое время назад, когда только начинал изучать Python, но вот он:

for i in range (999, 800, -1):

for j in range (999,800, -1):

    number = i*j
    str_number = str(number)

rev_str_number = str_number[::-1]

if str_number == rev_str_number:

    print("%s a palendrome") % number

Я не проверил все числа, которые вы сделали, но все же получил правильный ответ. Что я действительно узнал в этом упражнении, так это «::» и то, как это работает. Вы можете проверить это здесь.

Удачи с Эйлером!