Сам числа в C++

cout или printf в цикле будет медленным. Если вы сможете удалить любые отпечатки из цикла, то производительность будет значительно увеличена.

Вот пара идеи, которые у меня было ... Не уверен вообще, они будут работать;)

1) Попробуйте поймать мероприятие, используя метод QMENU, охватывающий (); Может быть, вы можете «отменить» процесс скрытого процесса?

2) Может быть, вы могли бы рассмотреть возможность использования EventFilter?

Постарайтесь взглянуть на: http://qt.nokia.com/doc/4.6/ Qobject.html # Installeventfilter

3) В противном случае вы можете переосмыслить QMENU, чтобы добавить свое поведение, но мне кажется много работы ...

Надеюсь, это немного поможет!

Эти моды (% ) выглядят дорогими. Если вам разрешено переходить на базу 16 (или даже базы 2), то вы можете, вероятно, вы можете записать это намного быстрее. Если вам придется оставаться в десятичной памяти, попробуйте создать массив цифр для каждого места (единицы, десятки, сотни) и построить какой-то код роловеса. Это сделает суммирующие числа гораздо проще.

В качестве альтернативы вы можете распознать поведение функции ядра (давайте назовем это s ):

s = n + f(b,n)

где f (b, n) - сумма цифр Из числа N в базе B .

Для базы 10 ясно, что, как и те, которые известны как наименее значимые) цифры, перемещаются от 0,1,2, ..., 9, что n и f (b , n) Продолжайте в Lockstep, когда вы перемещаетесь из N n N + 1 , это только то, что 10% времени, которое 9 бросается до 0, которое он не так:

f(b,n+1) = f(b,n) + 1  // 90% of the time

Таким образом, функция ядра [111515348] продвигается как

n+1 + f(b,n+1) = n + 1 + f(b,n) + 1 = n + f(b,n) + 2

s(n+1) = s(n) + 2 // again, 90% of the time

в оставшихся (и легко идентифицируемых) 10% времени, 9 свернутых назад к нулю и добавляет один на следующую цифру, что в Самый простой чехол вычитает (9-1) из прохода, но может каскадом через серию 9с, чтобы вычесть 99-1, 999-1 и т. Д.

, поэтому первая оптимизация может удалить большую часть работы от 90 % ваших циклов!

if ((n % 10) != 0) 
{
  n + f(b,n) = n-1 + f(b,n-1) + 2;
}

ИЛИ

if ((n % 10) != 0)
{
  s = old_s + 2;
}

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

Если вы хотите больше, то выделите простым алгоритмом для изменения между итерациями для оставшихся 10%.

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

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

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

#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;
}

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

Это может помочь ускорить вывод C ++ IOSTreams:

cin.tie(0);
ios::sync_with_stdio(false);

Положите их в основной, прежде чем начать писать в Cout.

Поскольку диапазон ограничен (от 1 до 1000000), максимальная сумма цифр не превышает 9 * 6 = 54. Это означает, что для реализации сита A циркулярный буфер 54 элементов должен быть идеально Достаточно (и размер сита очень медленно растет, поскольку диапазон увеличивается).

У вас уже есть решение на основе сита, но он основан на предварительно построении полнометражного буфера (сито 1000000 элементов), который довольно неистеван (если не совсем неприемлемый). Производительность вашего решения также страдает от несмещения доступа к памяти.

Например, это возможная очень простая реализация

#define N 1000000U

void print_self_numbers(void)
{
  #define NMARKS 64U /* make it 64 just in case (and to make division work faster :) */

  unsigned char marks[NMARKS] = { 0 };
  unsigned i, imark;

  for (i = 1, imark = i; i <= N; ++i, imark = (imark + 1) % NMARKS)
  {
    unsigned digits, sum;

    if (!marks[imark])
      printf("%u ", i);
    else
      marks[imark] = 0;

    sum = i;
    for (digits = i; digits > 0; digits /= 10)
      sum += digits % 10;

    marks[sum % NMARKS] = 1;
  }
}

(я не собираюсь наилучшим образом возможным производительность в терминах часов CPU здесь, просто иллюстрируя ключевую идею с циркулярным буфером.)

Конечно Диапазон может быть легко превращен в параметр функции, в то время как размер куркулянного буфера может быть легко рассчитан во время выполнения от диапазона.

Что касается «оптимизации» ... Нет смысла пытаться оптимизировать код, содержащий операции ввода / вывода. Вы не достигнете никакого достижения таких оптимизаций. Если вы хотите проанализировать производительность самого алгоритма, вам придется поставить сгенерированные номера в массив вывода и распечатать их позже.

MultiThread (используйте разные массивы / диапазоны для каждого потока). Кроме того, не используйте больше потоков, чем ваш номер CPU Cores =)

Если вы хотите, чтобы ваш выход был быстрым, возможно, стоит изучить замену вывода iostream простым старым printf () - зависит от правил победы в конкурсе, важно ли это.

Существует два метода реализации службы отображения, подобных описанному вами.

1. Клиенты отправляют глобально уникальные идентификаторы, или
2. Сервер генерирует глобально уникальные идентификаторы

Клиенты отправляют глобально уникальные идентификаторы

Насколько мне известно, 1. следует пытаться только с помощью Guid , если только вы не разработаете аналогичное средство для передачи достаточно четкой информации в короткий поток байтов. В любом случае, если у вас есть поток байтов, которые представляют глобально уникальный идентификатор, вы можете сделать что-то подобное

// source is either a Guid, or some other globally unique byte stream
byte[] bytes = Guid.NewGuid ().ToByteArray ();
string base64String = Convert.ToBase64String (bytes).Trim ("=");

, чтобы получить считываемую пользователем строку алфавитно-цифровых чисел, которая выглядит случайной, но избегает конфликтов, присущих другим случайным схемам. Guid содержит 16 байт или 128 бит, что соответствует приблизительно 19 символам для полной кодировки Base64.

Преимущество этого подхода в том, что клиенты могут генерировать свои собственные крошечные Uris без центрального органа. Минусом является большая длина, если вы катитесь с Guid или реализуете свой собственный глобально уникальный поток байтов, который - давайте посмотрим правде в глаза - склонен к ошибкам.

Если вы действительно идете по этому маршруту, рассмотрите глобально уникальные потоки байтов Google или такие. О, и ДЕРЖИТЕСЬ ПОДАЛЬШЕ ОТ СЛУЧАЙНЫХ БАЙТОВ , иначе вам придется построить разрешение коллизий ПОВЕРХ вашего крошечного генератора URI.

Сервер генерирует глобальные уникальные идентификаторы

Опять же, основное преимущество вышеизложенного состоит в том, что Клиент может генерировать свой Uris априори . Особенно удобно, если вы собираетесь отправить длительный запрос, который вы хотите проверить. Это может не иметь особого отношения к вашей ситуации и может дать лишь ограниченную ценность.

Таким образом, если не считать серверно-ориентированного подхода, в котором единый орган власти генерирует и выдает идентификаторы, может быть более привлекательным. Если это выбранный маршрут, то вопрос только в том, как долго вы хотите ваш URI?

Предполагая желаемую длину 5 символов, и допустим, вы идете с Base64 кодировкой, каждый идентификатор может представлять до 5 символов на 7 бит на символ равно 35 бит или 2 ^ 35 [34 359 738 368] различных значений. Это довольно большой домен. *

Тогда возникает вопрос о возврате значения для данного представления. Вероятно, есть много способов сделать это, но я бы пошел с чем-то вроде этого,

• Перечислить все возможные значения в "список свободных элементов" в базе данных
• Удалить значение из списка свободных элементов при использовании
• Добавить значение в список свободных элементов при выпуске

Усовершенствования или оптимизации могут включать

• Не перечислять все значения в диапазоне [0, 2 ^ 35], вместо перечисления управляемого подмножества, скажем, 100 000 значений одновременно, и когда все значения будут израсходованы, просто создайте еще 100 000 значений в последовательности и продолжите
• Добавьте дату истечения к значениям,и повторно использовать просроченные значения в конце дня
• Распределите ваш сервис, когда параллелизация вашего сервиса просто вынимает небольшие взаимоисключающие подмножества вашего списка бесплатных услуг

Вывод

Итог: вы хотите гарантировать уникальность - так что коллизии являются большим нет-нет.

* = 34 359 738 368 - размер необработанного домена, это все идентификаторы от 0 длины до 5 длины. Если вы заинтересованы в ограничении всех идентификаторов минимальной и максимальной длиной 5, то ваш домен выглядит так, что все идентификаторы длиной от 0 до 5 (2 ^ 35) меньше, чем все идентификаторы длиной от 0 до 4 (2 ^ 28) составляет от 2 ^ 35 до 2 ^ 28 = 34 091 302 912, что все еще довольно велико:)

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

Проблема веселья. Проблема в том виде, в котором она изложена, не уточняет, в какой базе она должна быть. Я немного пошатался с ней и написал версию 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;
}

Почему бы не использовать вместо этого отношение к рекуррентам, указанное на странице Википедии? Это должно быть молниеносно быстро.

EDIT: Игнорируйте это ... отношение к рекуррентности генерирует некоторые, но не все собственные номера. На самом деле, только очень немногие из них. Это не совсем понятно из страницы Википедии, хотя :(

Сгенерировать числа один раз, скопировать вывод в свой код в виде гигантской строки. Распечатайте строку.

Если вы хотите, чтобы ваш вывод был быстрым, это может стоить исследовать замену выхода IOSTream с простым старым printf () - зависит от правил для выигрыша конкуренции, важно ли это.

Я создал решение на основе CUDA, основанное на втором алгоритме Карла Смотрича. Сам код для идентификации Self Numbers чрезвычайно быстр - на моей машине он выполняется за ~45 наносекунд; это примерно в 150 раз быстрее, чем алгоритм Карла Смотрича, который работал на моей машине за 7 миллисекунд.

Однако, есть узкое место, и это, кажется, интерфейс PCIe. Моему коду потребовалось 43 миллисекунды, чтобы перенести вычисленные данные с видеокарты обратно в оперативную память. Это может быть оптимизировано, и я буду смотреть в этом направлении.

Тем не менее, 45 наносениц довольно чертовски быстро. На самом деле, страшно быстро, и я добавил код в свою программу, которая работает по алгоритму Карла Смотрича и сравнивает результаты с точностью. Результаты точные. Вот выход программы (скомпилированной в 64-битной версии VS2008, Windows7):

UPDATE

Я перекомпилировал этот код в режиме релиза с полной оптимизацией и использованием статических библиотек исполнения, со значительными результатами. Оптимизатор, похоже, очень хорошо справился с алгоритмом Карла, уменьшив время исполнения с 7 мс до 1 мс. Реализация CUDA также ускорилась - с 35 до 20. Не пострадала копия памяти с видеокарты в оперативную память.

Выход программы:

Running on device: 'Quadro NVS 295'
Reference Implementation Ran In 15603 ticks (7 ms)
Kernel Executed in 40 ms -- Breakdown:
  [kernel] : 35 us (0.09%)
  [memcpy] : 40 ms (99.91%)
CUDA Implementation Ran In 111889 ticks (51 ms)
Compute Slots: 1000448 (1954 blocks X 512 threads)
Number of Errors: 0

Код выглядит следующим образом:

файл: main.h

#pragma once

#include <cstdlib>
#include <functional>

typedef std::pair<int*, size_t> sized_ptr;
static sized_ptr make_sized_ptr(int* ptr, size_t size)
{
    return make_pair<int*, size_t>(ptr, size);
}

__host__ void ComputeSelfNumbers(sized_ptr hostMem, sized_ptr deviceMemory, unsigned const blocks, unsigned const threads);

inline std::string format_elapsed(double d) 
{
    char buf[256] = {0};

    if( d < 0.00000001 )
    {
        // show in ps with 4 digits
        sprintf(buf, "%0.4f ps", d * 1000000000000.0);
    }
    else if( d < 0.00001 )
    {
        // show in ns
        sprintf(buf, "%0.0f ns", d * 1000000000.0);
    }
    else if( d < 0.001 )
    {
        // show in us
        sprintf(buf, "%0.0f us", d * 1000000.0);
    }
    else if( d < 0.1 )
    {
        // show in ms
        sprintf(buf, "%0.0f ms", d * 1000.0);
    }
    else if( d <= 60.0 )
    {
        // show in seconds
        sprintf(buf, "%0.2f s", d);
    }
    else if( d < 3600.0 )
    {
        // show in min:sec
        sprintf(buf, "%01.0f:%02.2f", floor(d/60.0), fmod(d,60.0));
    }
    // show in h:min:sec
    else 
        sprintf(buf, "%01.0f:%02.0f:%02.2f", floor(d/3600.0), floor(fmod(d,3600.0)/60.0), fmod(d,60.0));

    return buf;
}

inline std::string format_pct(double d)
{
    char buf[256] = {0};
    sprintf(buf, "%.2f", 100.0 * d);
    return buf;
}

файл: main.cpp

#define _CRT_SECURE_NO_WARNINGS 

#include <windows.h>
#include "C:\CUDA\include\cuda_runtime.h"
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
#include <cmath>
#include <map>
#include <algorithm>
#include <list>

#include "main.h"

int main()
{
    unsigned numVals = 1000000;
    int* gold = new int[numVals];
    memset(gold, 0, sizeof(int)*numVals);

    LARGE_INTEGER li = {0}, li2 = {0};
    QueryPerformanceFrequency(&li);
    __int64 freq = li.QuadPart;

    // get cuda properties...
    cudaDeviceProp cdp = {0};
    cudaError_t err = cudaGetDeviceProperties(&cdp, 0);
cout << "Running on device: '" << cdp.name << "'" << endl;

    // first run the reference implementation
    QueryPerformanceCounter(&li);
    for( int j6=0, n = 0; j6<10; j6++ ) 
    {
        for( int j5=0; j5<10; j5++ ) 
        {
            for( int j4=0; j4<10; j4++ ) 
            {
                for( int j3=0; j3<10; j3++ ) 
                {
                    for( int j2=0; j2<10; j2++ ) 
                    {
                        for( int j1=0; j1<10; j1++ )  
                        {
                            int s = j6 + j5 + j4 + j3 + j2 + j1;
                            gold[n + s] = 1;
                            n++;
                        }
                    }
                }
            }
        }
    }
    QueryPerformanceCounter(&li2);
    __int64 ticks = li2.QuadPart-li.QuadPart;
    cout << "Reference Implementation Ran In " << ticks << " ticks" << " (" << format_elapsed((double)ticks/(double)freq) << ")" << endl;

    // now run the cuda version...
    unsigned threads = cdp.maxThreadsPerBlock;
    unsigned blocks = numVals/threads;
    if( numVals%threads ) ++blocks;
    unsigned computeSlots = blocks * threads;   // this may be != the number of vals since we want 32-thread warps

    // allocate device memory for test
    int* deviceTest = 0;
    err = cudaMalloc(&deviceTest, sizeof(int)*computeSlots);
    err = cudaMemset(deviceTest, 0, sizeof(int)*computeSlots);

    int* hostTest = new int[numVals];   // the repository for the resulting data on the host
    memset(hostTest, 0, sizeof(int)*numVals);

    // run the CUDA code...
    LARGE_INTEGER li3 = {0}, li4={0};
    QueryPerformanceCounter(&li3);
    ComputeSelfNumbers(make_sized_ptr(hostTest, numVals), make_sized_ptr(deviceTest, computeSlots), blocks, threads);
    QueryPerformanceCounter(&li4);

    __int64 ticksCuda = li4.QuadPart-li3.QuadPart;
    cout << "CUDA Implementation Ran In " << ticksCuda << " ticks" << " (" << format_elapsed((double)ticksCuda/(double)freq) << ")" << endl;
    cout << "Compute Slots: " << computeSlots << " (" << blocks << " blocks X " << threads << " threads)" << endl;


    unsigned errorCount = 0;
    for( size_t i = 0; i < numVals; ++i )
    {
        if( gold[i] != hostTest[i] )
        {
            ++errorCount;
        }
    }

    cout << "Number of Errors: " << errorCount << endl;

    return 0;
}

файл: self.cu

#pragma warning( disable : 4231)
#include <windows.h>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
#include "main.h"

__global__ void SelfNum(int * slots)
{
    __shared__ int N;
    N = (blockIdx.x * blockDim.x) + threadIdx.x;

    const int numDigits = 10;

    __shared__ int digits[numDigits];
    for( int i = 0, temp = N; i < numDigits; ++i, temp /= 10 )
    {
        digits[numDigits-i-1] = temp - 10 * (temp/10)      /*temp % 10*/;
    }

    __shared__ int s;
    s = 0;
    for( int i = 0; i < numDigits; ++i )
        s += digits[i];

    slots[N+s] = 1;
}

__host__ void ComputeSelfNumbers(sized_ptr hostMem, sized_ptr deviceMem, const unsigned  blocks, const unsigned threads)
{
    LARGE_INTEGER li = {0};
    QueryPerformanceFrequency(&li);
    double freq = (double)li.QuadPart;

    LARGE_INTEGER liStart = {0};
    QueryPerformanceCounter(&liStart);

    // run the kernel
    SelfNum<<<blocks, threads>>>(deviceMem.first);
    LARGE_INTEGER liKernel = {0};
    QueryPerformanceCounter(&liKernel);

    cudaMemcpy(hostMem.first, deviceMem.first, hostMem.second*sizeof(int), cudaMemcpyDeviceToHost); // dont copy the overflow - just throw it away
    LARGE_INTEGER liMemcpy = {0};
    QueryPerformanceCounter(&liMemcpy);

    // display performance stats
    double e = double(liMemcpy.QuadPart - liStart.QuadPart)/freq,
        eKernel = double(liKernel.QuadPart - liStart.QuadPart)/freq,
        eMemcpy = double(liMemcpy.QuadPart - liKernel.QuadPart)/freq;

    double pKernel = eKernel/e,
        pMemcpy = eMemcpy/e;

    cout << "Kernel Executed in " << format_elapsed(e) << " -- Breakdown: " << endl
        << "  [kernel] : " << format_elapsed(eKernel) << " (" << format_pct(pKernel) << "%)" << endl
        << "  [memcpy] : " << format_elapsed(eMemcpy) << " (" << format_pct(pMemcpy) << "%)" << endl;



}

UPDATE2:

Я рефакторировал свою реализацию CUDA, чтобы попытаться ее немного ускорить. Для этого я вручную разворачивал циклы, исправлял сомнительное использование памяти __shared__, что могло быть ошибкой, и избавлялся от избыточности.

Вывод моего нового кернела:

Reference Implementation Ran In 69610 ticks (5 ms)
Kernel Executed in 2 ms -- Breakdown:
  [kernel] : 39 us (1.57%)
  [memcpy] : 2 ms (98.43%)
CUDA Implementation Ran In 62970 ticks (4 ms)
Compute Slots: 1000448 (1954 blocks X 512 threads)
Number of Errors: 0

Единственный код, который я изменил, это сам кернел, так что это все, что я напишу здесь:

__global__ void SelfNum(int * slots)
{
    int N = (blockIdx.x * blockDim.x) + threadIdx.x;

    int s = 0;

    int temp = N;
    s += temp - 10 * (temp/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;
    s += temp - 10 * ((temp/=10)/10)      /*temp % 10*/;

    slots[N+s] = 1;
}