Необычная разность оборотов между Python и C++

Вот версия C #:

using System;
using System.Collections.Generic;
using System.Text;

namespace CSharp
{
  class Program
  {
    static void Main (string [] args)
    {
      while (true)
      {
        Console.Write ("Pick an upper bound: ");

        String
          input = Console.ReadLine ();

        uint
          upper_bound;

        if (uint.TryParse (input, out upper_bound))
        {
          DateTime
            start = DateTime.Now;

          CalcHappyNumbers (upper_bound);

          DateTime
            end = DateTime.Now;

          TimeSpan
            span = end - start;

          Console.WriteLine ("Time taken = " + span.TotalSeconds + " seconds.");
        }
        else
        {
          Console.WriteLine ("Error in input, unable to parse '" + input + "'.");
        }
      }
    }

    enum State
    {
      Happy,
      Sad,
      Unknown
    }

    static void CalcHappyNumbers (uint upper_bound)
    {
      SortedDictionary<uint, State>
        happy = new SortedDictionary<uint, State> ();

      SortedDictionary<uint, bool>
        happy_numbers = new SortedDictionary<uint, bool> ();

      happy [1] = State.Happy;
      happy_numbers [1] = true;

      for (uint current = 2 ; current < upper_bound ; ++current)
      {
        FindState (ref happy, ref happy_numbers, current);
      }

      //foreach (KeyValuePair<uint, bool> pair in happy_numbers)
      //{
      //  Console.Write (pair.Key.ToString () + ", ");
      //}

      //Console.WriteLine ("");
    }

    static State FindState (ref SortedDictionary<uint, State> happy, ref SortedDictionary<uint,bool> happy_numbers, uint value)
    {
      State
        current_state;

      if (happy.TryGetValue (value, out current_state))
      {
        if (current_state == State.Unknown)
        {
          happy [value] = State.Sad;
        }
      }
      else
      {
        happy [value] = current_state = State.Unknown;

        uint
          new_value = 0;

        for (uint i = value ; i != 0 ; i /= 10)
        {
          uint
            lsd = i % 10;

          new_value += lsd * lsd;
        }

        if (new_value == 1)
        {
          current_state = State.Happy;
        }
        else
        {
          current_state = FindState (ref happy, ref happy_numbers, new_value);
        }

        if (current_state == State.Happy)
        {
          happy_numbers [value] = true;
        }

        happy [value] = current_state;
      }

      return current_state;
    }
  }
}

Я сравнил ее с кодом Dr_Asik на C ++. Для верхней границы 100000 версия C ++ работала примерно за 2,9 секунды, а версия C # - за 0,35 секунды. Оба были скомпилированы с помощью Dev Studio 2005 с использованием параметров сборки выпуска по умолчанию, и оба были выполнены из командной строки.

#!/usr/bin/env python

import timeit

upperBound = 0

def calcMain():
    known = set()
    for i in xrange(0,upperBound+1):
        next = False
        current = i
        history = set()
        while not next:
            squaresum=0
            while current > 0:
                current, digit = divmod(current, 10)
                squaresum += digit * digit
            current = squaresum
            if current in history:
                next = True
                if current == 1:
                    known.add(i)
            history.add(current)

while True:
    upperBound = input("Pick an upper bound: ")
    result = timeit.Timer(calcMain).timeit(1)
    print result, "seconds.\n"

Я внес несколько незначительных изменений в ваш исходный пример кода на Python, которые улучшили производительность кода более чем в 16 раз. Внесенные мной изменения увеличили для случая 100000 примерно с 9,64 секунды до примерно 3,38 секунды.

Основное изменение заключалось в том, чтобы изменения модуля 10 и аккумулятора выполнялись в цикле while. Я внес еще несколько изменений, которые улучшили время выполнения всего на доли сотых секунды. Первым незначительным изменением было изменение основного цикла for с понимания списка диапазонов на итератор xrange. Вторым незначительным изменением была замена класса набора на класс списка как для известных, так и для исторических переменных. Я также экспериментировал с пониманием итератора и предварительным вычислением квадратов, но оба они отрицательно влияли на эффективность. Кажется, я использую более медленную версию Python или более медленный процессор, чем некоторые другие участники. Мне были бы интересны результаты сравнения моего кода на Python с одной из оптимизированных версий C ++ того же алгоритма. Я также пробовал использовать оптимизацию python -O и -OO, но они дали обратный ожидаемый эффект.

Существует довольно много возможных оптимизаций:

(1) Используйте константные ссылки

bool inVector(int inQuestion, const vector<int>& known)
{
    for(vector<int>::const_iterator it = known.begin(); it != known.end(); ++it)
        if(*it == inQuestion)
            return true;
    return false;
}

int sum(const vector<int>& given)
{
    int sum = 0;
    for(vector<int>::const_iterator it = given.begin(); it != given.end(); ++it)
        sum += *it;
    return sum;
}

(2) Используйте обратный отсчет

int pow(int given, int power)
{
    int current = 1;
    while(power--)
        current *= given;
    return current;
}

Или, как говорили другие, используйте стандарт код библиотеки.

(3) Не выделяйте буферы там, где они не нужны

        vector<int> squares;
        for (int temp = current; temp != 0; temp /= 10)
        {
            squares.push_back(pow(temp % 10, 2));
        }

С такой же оптимизацией, что и PotatoSwatter, я получил время для 10000 чисел с 1,063 секунды до 0,062 секунды (за исключением того, что я заменил itoa на стандартный sprintf в оригинале).

При всех оптимизациях памяти (не передавайте контейнеры по значению - в C ++ вы должны явно решить, хотите ли вы копию или ссылку; перемещайте операции, которые выделяют память из внутренних циклов; если у вас уже есть номер в буфер символов, какой смысл копировать его в std :: string и т. д.) Я уменьшил его до 0,532.

Остальное время приходилось на использование% 10 для доступа к цифрам, а не на преобразование чисел в строку.

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

Вот пища для размышлений: если бы вы выбрали запуск алгоритма 1979 года для поиска простых чисел на компьютере 2009 года или алгоритма 2009 года на компьютере 1979 года, что бы вы выбрали?

Новый алгоритм на старом оборудовании был бы лучшим выбором с огромным отрывом. Взгляните на свои «вспомогательные» функции.

Вот еще один способ, основанный на запоминании всех уже изученных чисел. Я получил множитель x4-5, который на удивление устойчив по сравнению с кодом DrAsik для 1000 и 1000000, я ожидал, что кеш будет более эффективным, чем больше чисел мы исследуем. В остальном были применены такие же классические оптимизации. Кстати, если компилятор принимает NRVO (/ RNVO? Я никогда не помню точный термин) или ссылки rvalue, нам не нужно передавать вектор как параметр out .

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

enum Status {
    never_seen,
    being_explored,
    happy,
    unhappy
};

char const* toString[] = { "never_seen", "being_explored", "happy", "unhappy" };


inline size_t sum_squares(size_t i) {
    size_t s = 0;
    while (i) {
        const size_t digit = i%10;
        s += digit * digit;
        i /= 10;
    }
    return s ;
}

struct Cache {
    Cache(size_t dim) : m_cache(dim, never_seen) {}
    void set(size_t n, Status status) {
        if (m_cache.size() <= n) {
            m_cache.resize(n+1, never_seen);
        }
        m_cache[n] = status;
        // std::cout << "(c[" << n << "]<-"<<toString[status] << ")";
    }
    Status operator[](size_t n) const {
        if (m_cache.size() <= n) {
            return never_seen;
        } else {
            return m_cache[n];
        }
    }

private:
    std::vector<Status> m_cache;
};

void search_happy_lh(size_t upper_bound, std::vector<size_t> & happy_numbers)
{
    happy_numbers.clear();
    happy_numbers.reserve(upper_bound); // it doesn't improve much the performances

    Cache cache(upper_bound+1);
    std::vector<size_t> current_stack;

    cache.set(1,happy);
    happy_numbers.push_back(1);
    for (size_t i = 2; i<=upper_bound ; ++i) {
        // std::cout << "\r" << i << std::flush;
        current_stack.clear();
        size_t s= i;
        while ( s != 1 && cache[s]==never_seen)
        {
            current_stack.push_back(s);
            cache.set(s, being_explored);
            s = sum_squares(s);
            // std::cout << " - " << s << std::flush;
        }
        const Status update_with = (cache[s]==being_explored ||cache[s]==unhappy) ? unhappy : happy;
        // std::cout << " => " << s << ":" << toString[update_with] << std::endl;
        for (size_t j=0; j!=current_stack.size(); ++j) {
            cache.set(current_stack[j], update_with);
        }
        if (cache[i] == happy) {
            happy_numbers.push_back(i);
        }
    }
}

Просто чтобы получить немного больше Чтобы решить эту проблему, увидев, насколько быстро я действительно могу найти эти числа, я написал многопоточную реализацию алгоритма Dr_Asik на C ++. В отношении того факта, что эта реализация является многопоточной, важно понимать две вещи.

1. Больше потоков не обязательно ведет к улучшению времени выполнения, существует золотая середина для каждой ситуации в зависимости от объема чисел, которые вы хотите вычислить. .

2. Если вы сравните время между этой версией, работающей с одним потоком, и исходной версией, единственными факторами, которые могут вызвать разницу во времени, являются накладные расходы от запуска потока и проблемы с производительностью переменной системы. В остальном алгоритм тот же.

Код для этой реализации (вся заслуга алгоритма принадлежит Dr_Asik) здесь . Кроме того, я написал несколько тестов скорости с двойной проверкой для каждого теста, чтобы подтвердить эти 3 балла.

Расчет первых 100000000 счастливых чисел:

Исходный - 39,061 / 39,000 (исходная реализация Dr_Asik)

Код для этой реализации (вся заслуга алгоритма принадлежит Dr_Asik) здесь . Кроме того, я написал несколько тестов скорости с двойной проверкой для каждого теста, чтобы подтвердить эти 3 точки.

Вычисление первых 100000000 счастливых чисел:

Оригинал - 39,061 / 39,000 (исходная реализация Dr_Asik)

Код для этой реализации (вся заслуга алгоритма принадлежит Dr_Asik) здесь . Кроме того, я написал несколько тестов скорости с двойной проверкой для каждого теста, чтобы подтвердить эти 3 балла.

Расчет первых 100000000 счастливых чисел:

Исходный - 39,061 / 39,000 (исходная реализация Dr_Asik)
1 поток - 39,000 / 39,079
2 потока - 19,750 / 19,890
10 потоков - 11,872 / 11,888
30 потоков - 10,764 / 10,827
50 потоков - 10.624 / 10.561 <-
100 потоков - 11.060 / 11.216
500 потоков - 13,385 / 12,527

Судя по этим результатам, наша золотая середина составляет около 50 потоков, плюс-минус десять или около того.

Ну, я тоже бегло просмотрел. Однако я не тестировал и даже не компилировал.

Общие правила для числовых программ:

• Никогда не обрабатывайте числа как текст. Это то, что делает меньшие языки, чем Python, медленными, поэтому, если вы сделаете это на C, программа будет медленнее, чем Python.

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

• Держите копию ссылки на STL открытой, чтобы вы могли использовать ее, а не писать свои собственные функции.

void calcMain(int upperBound)
{
    vector<int> known;
    for(int i = 0; i <= upperBound; i++)
    {
        int current = i;
        vector<int> history;
        do
        {
            squaresum = 0
            for ( ; current; current /= 10 )
            {
                int digit = current % 10;
                squaresum += digit * digit;
            }
            current = squaresum;
            history.push_back(current);
        } while ( ! count(history.begin(), history.end() - 1, current) );

        if(current == 1)
        {
            known.push_back(i);
            //cout << i << "\t";
        }

    }
    //cout << "\n\n";
}

Я вижу, что у вас довольно много ненужных выделений кучи

Например:

while(!next)
        {
            char* buffer = new char[10];

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

Вы также используете функцию atoi (), которую я не знаю, действительно ли она оптимизирована. Может быть, лучше задать модуль 10 и получить цифру (вы должны измерить тебя, я не проверял это).

Тот факт, что у вас есть линейный поиск (inVector), может быть плохим. Замена векторной структуры данных на std :: set может ускорить процесс. Hash_set тоже может помочь.

Но я думаю, что самая большая проблема - это строка и это распределение материала в куче внутри этого цикла. Это не выглядит хорошо. Я бы сначала попробовал в тех местах.

Это мой второй ответ; который кэширует такие вещи, как сумма квадратов для значений <= 10 ** 6 :

        happy_list[sq_list[x%happy_base] + sq_list[x//happy_base]]

То есть

• число разделено на 3 цифры + 3 цифры
• предварительно вычисленная таблица используется для получения суммы квадратов для обеих частей
• эти два результата складываются
• предварительно вычисленная таблица используется для получения счастья числа:

Я не думаю Версия Python может быть сделана намного быстрее (хорошо, если вы откажетесь от возврата к старой версии, то есть try: overhead, это на 10% быстрее).

Я думаю, что это отличный вопрос , который показывает, что, действительно,

• вещи, которые должны быть быстрыми, должны быть написаны на C
• , однако обычно вам не нужно, чтобы что-то было быстро (даже если вам нужно, чтобы программа работала сутки, это будет меньше, чем объединенное время программистов, оптимизирующих его)
• легче и быстрее писать программы на Python
• , но для некоторых проблем, особенно вычислительных, решения C ++, подобные приведенным выше, на самом деле более читабельны и красивее, чем попытка оптимизировать программу Python.

Хорошо, вот она (теперь вторая версия ...):

#!/usr/bin/env python3
'''Provides slower and faster versions of a function to compute happy numbers.

slow_happy() implements the algorithm as in the definition of happy
numbers (but also caches the results).

happy() uses the precomputed lists of sums of squares and happy numbers
to return result in just 3 list lookups and 3 arithmetic operations for
numbers less than 10**6; it falls back to slow_happy() for big numbers.

Utilities: digits() generator, my_timeit() context manager.

'''


from time import time  # For my_timeit.
from random import randint # For example with random number.

upperBound = 10**5  # Default value, can be overridden by user.


class my_timeit:
    '''Very simple timing context manager.'''

    def __init__(self, message):
        self.message = message
        self.start = time()

    def __enter__(self):
        return self

    def __exit__(self, *data):
        print(self.message.format(time() - self.start))


def digits(x:'nonnegative number') -> "yields number's digits":
    if not (x >= 0): raise ValueError('Number should be nonnegative')
    while x:
        yield x % 10
        x //= 10


def slow_happy(number, known = {1}, happies = {1}) -> 'True/None':
    '''Tell if the number is happy or not, caching results.

    It uses two static variables, parameters known and happies; the
    first one contains known happy and unhappy numbers; the second 
    contains only happy ones.

    If you want, you can pass your own known and happies arguments. If
    you do, you should keep the assumption commented out on the 1 line.

    '''
    # This is commented out because <= is expensive.
    # assert {1} <= happies <= known 

    if number in known:
        return number in happies

    history = set()
    while True:
        history.add(number)
        number = sum(x**2 for x in digits(number))
        if number in known or number in history:
            break

    known.update(history)
    if number in happies:
        happies.update(history)
        return True


# This will define new happy() to be much faster ------------------------.

with my_timeit('Preparation time was {0} seconds.\n'):

    LogAbsoluteUpperBound = 6 # The maximum possible number is 10**this.
    happy_list = [slow_happy(x)
                  for x in range(81*LogAbsoluteUpperBound + 1)]
    happy_base = 10**((LogAbsoluteUpperBound + 1)//2)
    sq_list = [sum(d**2 for d in digits(x))
               for x in range(happy_base + 1)]

    def happy(x):
        '''Tell if the number is happy, optimized for smaller numbers.

        This function works fast for numbers <= 10**LogAbsoluteUpperBound.

        '''
        try:
            return happy_list[sq_list[x%happy_base] + sq_list[x//happy_base]]
        except IndexError:
            return slow_happy(x)

# End of happy()'s redefinition -----------------------------------------.


def calcMain(print_numbers, upper_bound):
    happies = [x for x in range(upper_bound + 1) if happy(x)]
    if print_numbers:
        print(happies)


if __name__ == '__main__':
    while True:

        upperBound = eval(input(
            "Pick an upper bound [{0} default, 0 ends, negative number prints]: "
            .format(upperBound)).strip() or repr(upperBound))
        if not upperBound:
            break

        with my_timeit('This computation took {0} seconds.'):
            calcMain(upperBound < 0, abs(upperBound))

        single = 0
        while not happy(single):
            single = randint(1, 10**12)
        print('FYI, {0} is {1}.\n'.format(single,
                    'happy' if happy(single) else 'unhappy')) 

    print('Nice to see you, goodbye!')

Есть новая, радикально более быстрая версия, как отдельный ответ , поэтому этот ответ устарел.

Я переписал ваш алгоритм, сделав его кешем всякий раз, когда он находит число быть счастливым или несчастным. Я также попытался сделать его настолько питоническим, насколько мог, например, создав отдельные функции digits () и happy () . Извините за использование Python 3, но я также могу похвастаться парочкой полезных вещей из него.

Эта версия намного быстрее . Он работает со скоростью 1,7 с , что в 10 раз быстрее, чем ваша исходная программа, которая занимает 18 с (ну, мой MacBook довольно старый и медленный :))

#!/usr/bin/env python3

from timeit import Timer
from itertools import count

print_numbers = False
upperBound = 10**5  # Default value, can be overidden by user.


def digits(x:'nonnegative number') -> "yields number's digits":
    if not (x >= 0): raise ValueError('Number should be nonnegative')
    while x:
        yield x % 10
        x //= 10


def happy(number, known = {1}, happies = {1}) -> 'True/None':
    '''This function tells if the number is happy or not, caching results.

    It uses two static variables, parameters known and happies; the
    first one contains known happy and unhappy numbers; the second 
    contains only happy ones.

    If you want, you can pass your own known and happies arguments. If
    you do, you should keep the assumption commented out on the 1 line.

    '''

#        assert 1 in known and happies <= known  # <= is expensive

    if number in known:
        return number in happies

    history = set()
    while True:
        history.add(number)
        number = sum(x**2 for x in digits(number))
        if number in known or number in history:
            break

    known.update(history)
    if number in happies:
        happies.update(history)
        return True


def calcMain():
    happies = {x for x in range(upperBound) if happy(x) }
    if print_numbers:
        print(happies)


if __name__ == '__main__':
    upperBound = eval(
            input("Pick an upper bound [default {0}]: "
                    .format(upperBound)).strip()
            or repr(upperBound))
    result = Timer(calcMain).timeit(1)
    print ('This computation took {0} seconds'.format(result))

Похоже, вы передаете векторы по значению другим функциям. Это будет значительным замедлением, потому что программа фактически сделает полную копию вашего вектора, прежде чем передать его вашей функции. Чтобы обойти это, передайте постоянную ссылку на вектор вместо его копии. Поэтому вместо:

int sum(vector<int> given)

Используйте:

int sum(const vector<int>& given)

Когда вы это сделаете, вы больше не сможете использовать vector :: iterator, потому что он не постоянный. Вам нужно будет заменить его на vector :: const_iterator.

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

Я не эксперт в оптимизации C ++, но считаю, что разница в скорости может быть связана с тем, что в списках Python предварительно выделено больше места в начале, в то время как ваши векторы C ++ должны перераспределяться и, возможно, копировать каждый раз, когда он растет.

Что касается комментария GMan о find, я считаю, что оператор Python in также является линейным поиском и имеет ту же скорость.

Edit

Также я только что заметил, что вы свернули свой собственная функция pow. В этом нет необходимости, и stdlib, вероятно, быстрее.

Другие оптимизации : с использованием массивов и прямого доступа с использованием индекса цикла, а не поиска в векторе, и путем кэширования предыдущих сумм, следующий код (вдохновленный ответом доктора Асика, но, вероятно, не оптимизирован вообще) работает в 2445 раз быстрее, чем исходный код C ++, примерно в 400 раз быстрее, чем код Python.

#include <iostream>
#include <windows.h>
#include <vector>

void calcMain(int upperBound, std::vector<int>& known)
{
    int tempDigitCounter = upperBound;
    int numDigits = 0;
    while (tempDigitCounter > 0)
    {
        numDigits++;
        tempDigitCounter /= 10;
    }
    int maxSlots = numDigits * 9 * 9;
    int* history = new int[maxSlots + 1];

    int* cache = new int[upperBound+1];
    for (int jj = 0; jj <= upperBound; jj++)
    {
        cache[jj] = 0;
    }

    int current, sum, temp;
    for(int i = 0; i <= upperBound; i++)
    {
        current = i;
        while(true)
        {
            sum = 0;
            temp = current;

            bool inRange = temp <= upperBound;
            if (inRange)
            {
                int cached = cache[temp];
                if (cached)
                {
                    sum = cached;
                }
            }

            if (sum == 0)
            {
                while (temp > 0)
                {
                    int tempMod = temp % 10;
                    sum += tempMod * tempMod;
                    temp /= 10;
                }
                if (inRange)
                {
                    cache[current] = sum;
                }
            }
            current = sum;
            if(history[current] == i)
            {
                if(current == 1)
                {
                    known.push_back(i);
                }
                break;
            }
            history[current] = i;
        }
    }
}

int main()
{
    while(true)
    {
        int upperBound;
        std::vector<int> known;
        std::cout << "Pick an upper bound: ";
        std::cin >> upperBound;
        long start, end;
        start = GetTickCount();
        calcMain(upperBound, known);
        end = GetTickCount();
        for (size_t i = 0; i < known.size(); ++i) {
            std::cout << known[i] << ", ";
        }               
        double seconds = (double)(end-start) / 1000.0;
        std::cout << std::endl << seconds << " seconds." << std::endl << std::endl;
    }
    return 0;
}