Self номера в C ++

Question

Эй, мои друзья и я пытаемся побить время выполнения друг друга для генерации " Self Numbers " от 1 до миллиона. Я написал свой на C ++ и все еще пытаюсь сбрить драгоценное время.

Вот что у меня есть,

#include <iostream>

using namespace std;

bool v[1000000];
int main(void) {
  long non_self = 0;
  for(long i = 1; i < 1000000; ++i) {
    if(!(v[i])) std::cout << i << '\n';
    non_self = i + (i%10) + (i/10)%10 + (i/100)%10 + (i/1000)%10 + (i/10000)%10 +(i/100000)%10;
    v[non_self] = 1;
  }
  std::cout << "1000000" << '\n';
  return 0;
}

Теперь код работает нормально, я просто хочу его оптимизировать. Какие-нибудь советы? Спасибо.

Answer 1

Для такой простой задачи лучшим вариантом было бы придумать альтернативные алгоритмы для получения того же результата. % 10 обычно не считается быстрой операцией.

Answer 2

Забавная проблема. Проблема, как указано, не определяет, на какой базе она должна быть. Я немного возился с ней и написал версию base-2. Он генерирует дополнительные несколько тысяч записей, потому что точка завершения 1 000 000 не так естественна для base-2. Это предварительно подсчитывает количество бит в байте для поиска в таблице. Генерация набора результатов (без ввода / вывода) заняла 2,4 мс.

Одна интересная вещь (при условии, что я написал это правильно) состоит в том, что версия base-2 имеет от 250 000 «собственных чисел» до 1 000 000, в то время как в этом диапазоне находится чуть менее 100 000 собственных чисел base-10.

#include <windows.h>
#include <stdio.h>
#include <string.h>

void StartTimer( _int64 *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

double StopTimer( _int64 t1 )
{
   _int64 t2, ldFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&ldFreq );
   return ((double)( t2 - t1 ) / (double)ldFreq) * 1000.0;
}

#define RANGE 1000000

char sn[0x100000 + 32];

int bitCount[256];

 // precompute bitcounts for each byte
void PreCountBits()
{
    int i;

    // generate count of bits in each byte
    memset( bitCount, 0, sizeof( bitCount ));
    for ( i = 0; i < 256; i++ )
        {
        int tmp = i;

        while ( tmp )
            {
            if ( tmp & 0x01 )
                bitCount[i]++;
            tmp >>= 1;
            }
        }
}


void GenBase2( )
{
    int i;
    int *b1, *b2, *b3;
    int b1sum, b2sum, b3sum;

    i = 0;
    for ( b1 = bitCount; b1 < bitCount + 256; b1++ )
        {
        b1sum = *b1;
        for ( b2 = bitCount; b2 < bitCount + 256; b2++ )
            {
            b2sum = b1sum + *b2;
            for ( b3 = bitCount; b3 < bitCount + 256; b3++ )
                {
                sn[i++ + *b3 + b2sum] = 1;
                }
            }

        // 1000000 does not provide a great termination number for base 2.  So check
        // here.  Overshoots the target some but avoids repeated checks
        if ( i > RANGE )
            return;
        }
}


int main( int argc, char* argv[] )
{
    int i = 0;
    __int64 t1;


    memset( sn, 0, sizeof( sn ));
    StartTimer( &t1 );
    PreCountBits();
    GenBase2();
    printf( "Generation time = %.3f\n", StopTimer( t1 ));

    #if 1
    for ( i = 1; i <= RANGE; i++ )
        if ( !sn[i] ) printf( "%d\n", i );
    #endif
    return 0;
}

Answer 3

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

#include <iostream>
#include <boost/progress.hpp>

class SelfCalc
{
private:
    bool    array[1000000];
    int     non_self;

public:
    SelfCalc()
    {
        memset(&array, 0, sizeof(array));
    }

    void operator()(const int i)
    {
        if (!(array[i]))
            std::cout << i << '\n';

        non_self = i + (i%10) + (i/10)%10 + (i/100)%10 + (i/1000)%10 + (i/10000)%10 +(i/100000)%10;
        array[non_self] = true;
    }
};

class IntIterator
{
private:
    int value;

public: 
    IntIterator(const int _value):value(_value){}

    int operator*(){ return value; } 
    bool operator!=(const IntIterator &v){ return value != v.value; }
    int operator++(){ return ++value; }
};

int main()
{
    boost::progress_timer t;

    SelfCalc selfCalc;
    IntIterator i(1), end(100000);

    std::for_each(i, end, selfCalc);

    std::cout << 100000 << std::endl;
    return 0;
}

Answer 4

Может быть, попробуйте просто вычислить рекуррентное соотношение, определенное ниже?

http://en.wikipedia.org/wiki/Self_number

Answer 5

Интересно, поможет ли многопоточность. Этот алгоритм выглядит так, как будто он хорошо подходит для многопоточности. (Тест бедняков: создайте две копии программы и запустите их одновременно. Если она выполняется менее чем в 200% случаев, многопоточность может помочь).