Diferencia de velocidad inusual entre Python y C ++

Recientemente escribí un algoritmo corto para calcular los números felices en Python. El progtwig te permite elegir un límite superior y determinará todos los números felices debajo de él. Para una comparación de velocidad, decidí hacer la traducción más directa del algoritmo que conocía de python a c ++.

Sorprendentemente, la versión de c ++ se ejecuta significativamente más lento que la versión de python. Las pruebas de velocidad precisas entre los tiempos de ejecución para descubrir los primeros 10,000 números felices indican que el progtwig python se ejecuta en promedio en 0.59 segundos y la versión c ++ se ejecuta en promedio en 8.5 segundos.

Yo atribuiría esta diferencia de velocidad al hecho de que tuve que escribir funciones de ayuda para partes de los cálculos (por ejemplo, determinar si un elemento está en una lista / matriz / vector) en la versión c ++ que ya estaba incorporada en el lenguaje python .

En primer lugar, ¿es esta la verdadera razón de una diferencia de velocidad tan absurda y, en segundo lugar, cómo puedo cambiar la versión de c ++ para que se ejecute más rápidamente que la versión de python (la forma en que debería ser, en mi opinión)?

Las dos piezas de código, con las pruebas de velocidad, están aquí: Versión de Python , Versión de C ++ . Gracias por la ayuda.

    #include  #include  #include  #include  #include  using namespace std; bool inVector(int inQuestion, vector known); int sum(vector given); int pow(int given, int power); void calcMain(int upperBound); int main() { while(true) { int upperBound; cout <> upperBound; long start, end; start = GetTickCount(); calcMain(upperBound); end = GetTickCount(); double seconds = (double)(end-start) / 1000.0; cout << seconds << " seconds." << endl << endl; } return 0; } void calcMain(int upperBound) { vector known; for(int i = 0; i <= upperBound; i++) { bool next = false; int current = i; vector history; while(!next) { char* buffer = new char[10]; itoa(current, buffer, 10); string digits = buffer; delete buffer; vector squares; for(int j = 0; j < digits.size(); j++) { char charDigit = digits[j]; int digit = atoi(&charDigit); int square = pow(digit, 2); squares.push_back(square); } int squaresum = sum(squares); current = squaresum; if(inVector(current, history)) { next = true; if(current == 1) { known.push_back(i); //cout << i << "\t"; } } history.push_back(current); } } //cout << "\n\n"; } bool inVector(int inQuestion, vector known) { for(vector::iterator it = known.begin(); it != known.end(); it++) if(*it == inQuestion) return true; return false; } int sum(vector given) { int sum = 0; for(vector::iterator it = given.begin(); it != given.end(); it++) sum += *it; return sum; } int pow(int given, int power) { int original = given; int current = given; for(int i = 0; i < power-1; i++) current *= original; return current; } 

     #!/usr/bin/env python import timeit upperBound = 0 def calcMain(): known = [] for i in range(0,upperBound+1): next = False current = i history = [] while not next: digits = str(current) squares = [pow(int(digit), 2) for digit in digits] squaresum = sum(squares) current = squaresum if current in history: next = True if current == 1: known.append(i) ##print i, "\t", history.append(current) ##print "\nend" while True: upperBound = input("Pick an upper bound: ") result = timeit.Timer(calcMain).timeit(1) print result, "seconds.\n" 

    Para 100000 elementos, el código de Python tomó 6.9 segundos, mientras que el C ++ originalmente tomó más de 37 segundos.

    Hice algunas optimizaciones básicas en su código y logré obtener el código C ++ por encima de 100 veces más rápido que la implementación de Python. Ahora hace 100000 elementos en 0.06 segundos. Eso es 617 veces más rápido que el código original de C ++.

    Lo más importante es comstackr en modo Release, con todas las optimizaciones. Este código es, literalmente, órdenes de magnitud más lento en el modo de depuración.

    A continuación, explicaré las optimizaciones que hice.

    • Se movieron todas las declaraciones de vectores fuera del bucle; reemplazarlos por una operación clear (), que es mucho más rápida que llamar al constructor.
    • Reemplazó la llamada a pow (valor, 2) por una multiplicación: valor * valor.
    • En lugar de tener un vector de cuadrados y una sum de llamada, sumo los valores en el lugar utilizando solo un número entero.
    • Se evitan todas las operaciones de cadena, que son muy lentas en comparación con las operaciones de enteros. Por ejemplo, es posible calcular los cuadrados de cada dígito dividiendo repetidamente por 10 y obteniendo el módulo 10 del valor resultante, en lugar de convertir el valor en una cadena y luego cada carácter de nuevo a int.
    • Evitó todas las copias vectoriales, primero reemplazando pasar por valor con pasar por referencia y, finalmente, eliminando completamente las funciones auxiliares.
    • Se eliminaron algunas variables temporales.
    • Y probablemente olvidé muchos pequeños detalles. Compara tu código y el mío de lado a lado para ver exactamente lo que hice.

    Puede ser posible optimizar el código aún más mediante el uso de arreglos preasignados en lugar de vectores, pero esto sería un poco más de trabajo y lo dejaré como un ejercicio para el lector. :PAG

    Aquí está el código optimizado:

     #include  #include  #include  #include  #include  #include  using namespace std; void calcMain(int upperBound, vector& known); int main() { while(true) { vector results; int upperBound; cout << "Pick an upper bound: "; cin >> upperBound; long start, end; start = GetTickCount(); calcMain(upperBound, results); end = GetTickCount(); for (size_t i = 0; i < results.size(); ++i) { cout << results[i] << ", "; } cout << endl; double seconds = (double)(end-start) / 1000.0; cout << seconds << " seconds." << endl << endl; } return 0; } void calcMain(int upperBound, vector& known) { vector history; for(int i = 0; i <= upperBound; i++) { int current = i; history.clear(); while(true) { int temp = current; int sum = 0; while (temp > 0) { sum += (temp % 10) * (temp % 10); temp /= 10; } current = sum; if(find(history.begin(), history.end(), current) != history.end()) { if(current == 1) { known.push_back(i); } break; } history.push_back(current); } } } 

    Hay una nueva versión, radicalmente más rápida, como una respuesta separada , por lo que esta respuesta está en desuso.


    Reescribí su algoritmo haciéndolo en caché siempre que encuentre el número como feliz o infeliz. También traté de hacerlo lo más pythonic que pude, por ejemplo, creando funciones separadas digits() y happy() . Lo siento por usar Python 3, pero también puedo mostrarle un par de cosas útiles.

    Esta versión es mucho más rápida . Funciona a 1.7 s, que es 10 veces más rápido que el progtwig original que tarda 18 s (bueno, mi MacBook es bastante viejo y lento :))

     #!/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)) 

    Parece que estás pasando vectores por valor a otras funciones. Esta será una desaceleración significativa porque el progtwig realmente hará una copia completa de su vector antes de pasarlo a su función. Para evitar esto, pase una referencia constante al vector en lugar de una copia. Así que en lugar de:

     int sum(vector given) 

    Utilizar:

     int sum(const vector& given) 

    Cuando haga esto, ya no podrá usar el vector :: iterator porque no es constante. Tendrá que reemplazarlo con vector :: const_iterator.

    También puede pasar referencias no constantes, pero en este caso, no necesita modificar el parámetro en absoluto.

    Puedo ver que tienes bastantes asignaciones de stack que son innecesarias

    Por ejemplo:

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

    Esto no se ve muy optimizado. Por lo tanto, es probable que desee tener la matriz asignada previamente y usarla dentro de su bucle. Esta es una técnica de optimización básica que es fácil de detectar y hacer. También puede convertirse en un desastre, así que ten cuidado con eso.

    También está utilizando la función atoi (), que no sé si está realmente optimizada. Tal vez hacer un módulo 10 y obtener el dígito podría ser mejor (tienes que medir tú, no probé esto).

    El hecho de que tenga una búsqueda lineal (inVector) puede ser malo. Reemplazar la estructura de datos vectoriales con un std :: set podría acelerar las cosas. Un hash_set podría hacer el truco también.

    Pero creo que el peor problema es la cadena y esta asignación de cosas en el montón dentro de ese bucle. Eso no se ve bien. Yo probaría en esos lugares primero.

    Esta es mi segunda respuesta; que guarda cosas como la sum de cuadrados para valores <= 10**6 :

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

    Es decir,

    • el número se divide en 3 dígitos + 3 dígitos
    • La tabla precomputada se usa para obtener la sum de cuadrados para ambas partes.
    • estos dos resultados son agregados
    • La tabla precomputada se consulta para obtener la felicidad del número:

    No creo que la versión de Python se pueda hacer mucho más rápido que eso (está bien, si descartas el retroceso a la versión anterior, es decir, try: gastos generales, es un 10% más rápido).

    Creo que esta es una excelente pregunta que muestra que, de hecho,

    • Las cosas que tienen que ser rápidas deben estar escritas en C
    • sin embargo, normalmente no necesita que las cosas sean rápidas (incluso si necesita que el progtwig se ejecute durante un día, sería menos que el tiempo combinado de los progtwigdores optimizándolo)
    • Es más fácil y rápido escribir progtwigs en Python
    • pero para algunos problemas, especialmente los de computación, una solución de C ++, como las anteriores, es en realidad más legible y más bella que un bash de optimizar el progtwig Python.

    Ok, aquí va (2da versión ahora ...):

     #!/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!') 

    Bueno, también le di un vistazo. Aunque no probé ni compilé.

    Reglas generales para los progtwigs numéricos:

    • Nunca proceses los números como texto. Eso es lo que hace que los idiomas inferiores a Python sean más lentos, por lo que si lo haces en C, el progtwig será más lento que Python.

    • No uses estructuras de datos si puedes evitarlas. Estabas construyendo una matriz solo para sumr los números. Mejor mantén un total acumulado.

    • Mantenga abierta una copia de la referencia de STL para que pueda usarla en lugar de escribir sus propias funciones.


     void calcMain(int upperBound) { vector known; for(int i = 0; i <= upperBound; i++) { int current = i; vector 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"; } 

    Solo para obtener un poco más de certeza sobre este problema al ver qué tan rápido podría encontrar estos números, escribí una implementación de C ++ de multiproceso del algoritmo de Dr_Asik. Hay dos cosas que es importante tener en cuenta sobre el hecho de que esta implementación es multiproceso.

    1. Más hilos no necesariamente conducen a mejores tiempos de ejecución, hay un medio feliz para cada situación, dependiendo del volumen de números que desee calcular.

    2. Si compara los tiempos entre esta versión que se ejecuta con un subproceso y la versión original, los únicos factores que podrían causar una diferencia en el tiempo son los gastos generales derivados del inicio del subproceso y los problemas de rendimiento del sistema variable. De lo contrario, el algoritmo es el mismo.

    El código para esta implementación (todo el crédito por el algoritmo va a Dr_Asik) está aquí . Además, escribí algunas pruebas de velocidad con una doble verificación de cada prueba para ayudar a respaldar esos 3 puntos.

    Cálculo de los primeros 100,000,000 números felices:

    Original – 39.061 / 39.000 (implementación original de Dr_Asik)
    1 Hilo – 39.000 / 39.079
    2 hilos de rosca – 19.750 / 19.890
    10 hilos de rosca – 11.872 / 11.888
    30 hilos – 10.764 / 10.827
    50 hilos – 10.624 / 10.561 <-
    100 hilos – 11.060 / 11.216
    500 hilos – 13.385 / 12.527

    A partir de estos resultados, parece que nuestro medio feliz es de unos 50 hilos, más o menos diez o menos.

    Otras optimizaciones : mediante el uso de matrices y el acceso directo utilizando el índice de bucle en lugar de buscar en un vector, y almacenando sums anteriores, el siguiente código (inspirado en la respuesta del Dr. Asik pero probablemente no está optimizado en absoluto) se ejecuta 2445 veces más rápido que el C ++ original Código, unas 400 veces más rápido que el código Python.

     #include  #include  #include  void calcMain(int upperBound, std::vector& 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 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; } 

    No soy un experto en optimización de C ++, pero creo que la diferencia de velocidad puede deberse al hecho de que las listas de Python han preasignado más espacio al principio, mientras que los vectores de C ++ deben reasignarse y posiblemente copiarse cada vez que crezca.

    En cuanto al comentario del hallazgo de GMan, creo que el operador “en” de Python también es una búsqueda lineal y tiene la misma velocidad.

    Editar

    También me di cuenta de que hiciste tu propia función pow. No hay necesidad de hacer eso y el stdlib es probablemente más rápido.

    Esta es otra forma que se basa en la memorización de todos los números ya explorados. Obtengo un factor x4-5, que es extrañamente estable contra el código de DrAsik para 1000 y 1000000, esperaba que la memoria caché fuera más eficiente cuanto más números explorábamos. De lo contrario, se han aplicado las mismas optimizaciones clásicas. Por cierto, si el comstackdor acepta NRVO (/ RNVO? Nunca recuerdo el término exacto) o las referencias de valor, no tendríamos que pasar el vector como un parámetro de salida .

    NB: las micro-optimizaciones son todavía IMHO, y además el almacenamiento en caché es ingenuo, ya que asigna mucha más memoria de la que realmente se necesita.

     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 << "]<-"< m_cache; }; void search_happy_lh(size_t upper_bound, std::vector & happy_numbers) { happy_numbers.clear(); happy_numbers.reserve(upper_bound); // it doesn't improve much the performances Cache cache(upper_bound+1); std::vector 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); } } } 

    Tropezé con esta página mientras estaba aburrido y pensé que lo haría en js. El algoritmo es mío, y no lo he comprobado a fondo con nada que no sean mis propios cálculos (por lo que podría estar equivocado). Calcula los primeros 1e7 números felices y los almacena en h. Si quieres cambiarlo, cambia ambos 7s.

     m=1e7,C=7*81,h=[1],t=true,U=[,,,,t],n=w=2; while(n 

    Esto imprimirá los primeros 1000 elementos para usted en la consola o en un navegador:

     o=h.slice(0,m>1e3?1e3:m); (!this.document?print(o):document.load=document.write(o.join('\n'))); 

    155 caracteres para la parte funcional y parece ser tan rápido * como la oferta del Dr. Asik en firefox o v8 (350-400 veces más rápido que el progtwig python original en mi sistema cuando ejecuto el tiempo d8 happygolf.js o js -a - j -p happygolf.js en spidermonkey).
    Me sorprenderán las habilidades analíticas de cualquiera que pueda entender por qué este algoritmo está funcionando tan bien sin hacer referencia a la versión más larga y comentada de Fortran.

    Estaba intrigado por lo rápido que era, así que aprendí a Fortran a obtener una comparación del mismo algoritmo, sé amable si hay errores de principiante, es mi primer progtwig Fortran. http://pastebin.com/q9WFaP5C En cuanto a la memoria estática, para ser justos con los demás, está en un script de shell de autocomstackción, si no tiene gcc / bash / etc, elimine el preprocesador y bash en la parte superior, configura las macros manualmente y compílalas como fortran95.

    Incluso si incluyes el tiempo de comstackción, supera a la mayoría de los demás aquí. Si no lo haces, es aproximadamente ~ 3000-3500 veces más rápido que la versión original de Python (y, por extensión,> 40,000 veces más rápido que C ++ *, aunque no ejecuté ninguno de los progtwigs de C ++).

    Sorprendentemente, muchas de las optimizaciones que probé en la versión fortran (incluido el desenrollado de un bucle similar que dejé fuera de la versión pegada debido al pequeño efecto y la legibilidad) fueron perjudiciales para la versión js. Este ejercicio muestra que los comstackdores de trazas modernos son extremadamente buenos (dentro de un factor de 7 a 10 de Fortran de memoria estática cuidadosamente optimizada) si te apartas de ellos y no intentas nada complicado. salga de su camino y trate de hacer cosas difíciles Finalmente, aquí hay una versión de js mucho más bonita y recursiva.

     // to s, then integer divides x by 10. // Repeats until x is 0. function sumsq(x) { var y,s=0; while(x) { y = x % 10; s += y * y; x = 0| x / 10; } return s; } // A boolean cache for happy(). // The terminating happy number and an unhappy number in // the terminating sequence. var H=[]; H[1] = true; H[4] = false; // Test if a number is happy. // First check the cache, if that's empty // Perform one round of sumsq, then check the cache // For that. If that's empty, recurse. function happy(x) { // If it already exists. if(H[x] !== undefined) { // Return whatever is already in cache. return H[x]; } else { // Else calc sumsq, set and return cached val, or if undefined, recurse. var w = sumsq(x); return (H[x] = H[w] !== undefined? H[w]: happy(w)); } } //Main program loop. var i, hN = []; for(i = 1; i < 1e7; i++) { if(happy(i)) { hN.push(i); } } 

    Sorprendentemente, aunque es un nivel bastante alto, funcionó casi exactamente igual que el algoritmo imperativo en spidermonkey (con optimizaciones activadas), y se cerró (1.2 veces más) en v8.

    Moraleja de la historia, supongo, dedique un poco de tiempo a pensar en su algoritmo si es importante. Además, los lenguajes de alto nivel ya tienen muchos gastos generales (y algunas veces tienen trucos propios para reducirlos), por lo que a veces es tan rápido hacer algo más sencillo o utilizar sus funciones de alto nivel. También la micro-optimización no siempre ayuda.

    * A menos que la instalación de mi Python sea inusualmente lenta, los tiempos directos no tienen sentido, ya que esta es una primera generación eee. Los tiempos son:
    12s para la versión fortran, sin salida, 1e8 números felices.
    40s para la versión fortran, salida de tubería a través de gzip al disco.
    8-12s para ambas versiones js. 1e7 números felices, sin salida con optimización completa 10-100s para ambas versiones js 1e7 con menos / sin optimización (según la definición de sin optimización, los 100 estaban con eval ()) sin salida

    Me interesaría ver los horarios de estos progtwigs en una computadora real.

    Aquí hay algo para pensar: si tuviera la opción de ejecutar un algoritmo de 1979 para encontrar números primos en una computadora de 2009 o un algoritmo de 2009 en una computadora de 1979, ¿cuál elegiría?

    El nuevo algoritmo en hardware antiguo sería la mejor opción por un gran margen. Eche un vistazo a las funciones de su “ayudante”.

    There are quite a few optimizations possible:

    (1) Use const references

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

    (2) Use counting down loops

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

    Or, as others have said, use the standard library code.

    (3) Don’t allocate buffers where not required

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

    With similar optimizations as PotatoSwatter I got time for 10000 numbers down from 1.063 seconds to 0.062 seconds (except I replaced itoa with standard sprintf in the original).

    With all the memory optimizations (don’t pass containers by value – in C++ you have to explicitly decide whether you want a copy or a reference; move operations that allocate memory out of inner loops; if you already have the number in a char buffer, what’s the point of copying it to std::string etc) I got it down to 0.532.

    The rest of the time came from using %10 to access digits, rather than converting numbers to string.

    I suppose there might be another algorithmic level optimization (numbers that you have encountered while finding a happy number are themselves also happy numbers?) but I don’t know how much that gains (there is not that many happy numbers in the first place) and this optimization is not in the Python version either.

    By the way, by not using string conversion and a list to square digits, I got the Python version from 0.825 seconds down to 0.33 too.

     #!/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" 

    I made a couple of minor changes to your original python code example that make a better than 16x improvement to the performance of the code. The changes I made took the 100,000 case from about 9.64 seconds to about 3.38 seconds.

    The major change was to make the mod 10 and accumulator changes to run in a while loop. I made a couple of other changes that improved execution time in only fractions of hundredths of seconds. The first minor change was changing the main for loop from a range list comprehension to an xrange iterator. The second minor change was substituting the set class for the list class for both the known and history variables. I also experimented with iterator comprehensions and precalculating the squares but they both had negative effects on the efficiency. I seem to be running a slower version of python or on a slower processor than some of the other contributers. I would be interest in the results of someone else’s timing comparison of my python code against one of the optimized C++ versions of the same algorithm. I also tried using the python -O and -OO optimizations but they had the reverse of the intended effect.

    Here’s a C# version:

     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 happy = new SortedDictionary (); SortedDictionary happy_numbers = new SortedDictionary (); 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 pair in happy_numbers) //{ // Console.Write (pair.Key.ToString () + ", "); //} //Console.WriteLine (""); } static State FindState (ref SortedDictionary happy, ref SortedDictionary 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; } } } 

    I compared it against Dr_Asik’s C++ code. For an upper bound of 100000 the C++ version ran in about 2.9 seconds and the C# version in 0.35 seconds. Both were compiled using Dev Studio 2005 using default release build options and both were executed from a command prompt.

    Why is everyone using a vector in the c++ version? Lookup time is O(N).

    Even though it’s not as efficient as the python set, use std::set. Lookup time is O(log(N)).