guia - Diferencia de velocidad inusual entre Python y C++
qgis manual (17)
Aquí hay algo de reflexión: si se le da 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 sus funciones de "ayuda".
Recientemente escribí un algoritmo corto para calcular números felices en Python. El programa 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 exactas entre los tiempos de ejecución para descubrir los primeros 10,000 números felices indican que el programa python se ejecuta en promedio en 0.59 segundos y la versión de c ++ se ejecuta en promedio en 8.5 segundos.
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 de C ++ que ya estaban incorporadas 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 (como debería ser, en mi opinión).
Las dos piezas de código, con la prueba de velocidad están aquí: Versión de Python , Versión de C ++ . Gracias por la ayuda.
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <windows.h>
using namespace std;
bool inVector(int inQuestion, vector<int> known);
int sum(vector<int> given);
int pow(int given, int power);
void calcMain(int upperBound);
int main()
{
while(true)
{
int upperBound;
cout << "Pick an upper bound: ";
cin >> 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<int> known;
for(int i = 0; i <= upperBound; i++)
{
bool next = false;
int current = i;
vector<int> history;
while(!next)
{
char* buffer = new char[10];
itoa(current, buffer, 10);
string digits = buffer;
delete buffer;
vector<int> 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<int> known)
{
for(vector<int>::iterator it = known.begin(); it != known.end(); it++)
if(*it == inQuestion)
return true;
return false;
}
int sum(vector<int> given)
{
int sum = 0;
for(vector<int>::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"
No soy un experto en la optimización de C ++, pero creo que la diferencia de velocidad puede deberse al hecho de que las listas de Python han asignado más espacio al principio, mientras que los vectores de C ++ deben reasignarse y posiblemente copiar cada vez que crece.
En cuanto al comentario de GMan sobre find, creo que el operador "in" de Python también es una búsqueda lineal y tiene la misma velocidad.
Editar
También me di cuenta de que habías rodado tu propia función de pow. No hay necesidad de hacer eso y el stdlib es probablemente más rápido.
Parece que estás pasando vectores por valor a otras funciones. Esta será una desaceleración significativa porque el programa 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. Entonces, en lugar de:
int sum(vector<int> given)
Utilizar:
int sum(const vector<int>& given)
Cuando haga esto, ya no podrá usar el vector :: iterator porque no es constante. Deberás reemplazarlo por vector :: const_iterator.
También puede pasar referencias no constantes, pero en este caso, no necesita modificar el parámetro en absoluto.
Con optimizaciones similares a PotatoSwatter Tengo tiempo para 10000 números por debajo de los 1.063 segundos a 0.062 segundos (excepto Substituí itoa con sprintf estándar en el original).
Con todas las optimizaciones de memoria (no pase contenedores por valor - en C ++ que tiene que decidir de forma explícita si desea una copia o una referencia; operaciones de movimiento que asignar memoria de bucles internos; si ya tiene el número en un char buffer , ¿cuál es el punto de copiarlo a std :: string, etc.) lo tengo hasta 0,532.
El resto del tiempo vino de usar% a 10 dígitos de acceso, en lugar de convertir los números de secuencia.
Supongo que podría haber otro nivel de optimización algorítmica (números que pueda haber tenido al mismo tiempo encontrar un número feliz mismos son también números felices?), Pero no sé cuánto que las ganancias (no hay que muchos números felices en el primer lugar) y esta optimización no está en la versión de Python tampoco.
Por cierto, al no utilizar la conversión de cadenas y una lista de números cuadrados, tengo la versión de Python desde 0,825 segundos a 0,33 también.
Hay un buen número de optimizaciones posibles:
(1) Utilizar referencias const
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) Usar la cuenta atrás bucles
int pow(int given, int power)
{
int current = 1;
while(power--)
current *= given;
return current;
}
O, como otros han dicho, utilice el código de la biblioteca estándar.
(3) No asignar memorias intermedias en las que no requieren
vector<int> squares;
for (int temp = current; temp != 0; temp /= 10)
{
squares.push_back(pow(temp % 10, 2));
}
Aquí hay otra manera que se basa en memorizar 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 el caché fuera más eficiente cuanto más números estuviéramos explorando. De lo contrario, se aplica el mismo tipo de optimizaciones clásicas. Por cierto, si el compilador acepta NRVO (/ RNVO? Nunca recuerdo el término exacto) o las referencias rvalue, no necesitaríamos pasar el vector como un parámetro de salida .
NB: las micro-optimizaciones todavía son posibles en mi humilde opinión, 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 << "]<-"<<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);
}
}
}
Bueno, también le di una vez más. Sin embargo, no probé ni compilé.
Reglas generales para programas numéricos:
Nunca procese números como texto. Eso es lo que hace que los lenguajes menores que Python sean lentos, así que si lo haces en C, el programa será más lento que Python.
No use estructuras de datos si puede evitarlas. Estabas construyendo una matriz solo para agregar los números. Mejor mantener un total acumulado.
Mantenga una copia de la referencia de STL abierta para que pueda usarla en lugar de escribir sus propias funciones.
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";
}
Esta es mi segunda respuesta; que almacena en caché cosas como la suma 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 precalculada se usa para obtener la suma de cuadrados para ambas partes
- estos dos resultados se agregan
- la tabla precalculada 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 (vale, si se descarta la versión anterior, eso es try: encima, es un 10% más rápido).
Creo que esta es una excelente pregunta que muestra que, de hecho,
- las cosas que deben ser rápidas deben escribirse en C
- sin embargo, generalmente no necesita que las cosas sean rápidas (incluso si necesita que el programa se ejecute durante un día, sería menos que el tiempo combinado de los programadores que lo optimizan)
- es más fácil y rápido escribir programas en Python
- pero para algunos problemas, especialmente los computacionales, una solución C ++, como las anteriores, en realidad es más legible y más hermosa que un intento de optimizar el programa 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!'')
Veo que tiene bastantes asignaciones de montón 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 preasignada y usarla dentro de su ciclo. Esta es una técnica básica de optimización que es fácil de detectar y hacer. También podría convertirse en un desastre, así que ten cuidado con eso.
También está utilizando la función atoi (), que realmente no sé si está realmente optimizada. Quizás hacer un módulo 10 y obtener el dígito podría ser mejor (tienes que medirlo, no lo he probado).
El hecho de tener una búsqueda lineal (inVector) puede ser malo. Reemplazar la estructura de datos vectoriales con un std :: set puede 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. Primero probaría en esos lugares.
Solo para obtener un poco más de cierre sobre este tema al ver qué tan rápido pude encontrar realmente estos números, escribí una implementación multiproceso de C ++ del algoritmo de Dr_Asik. Hay dos cosas que es importante darse cuenta sobre el hecho de que esta implementación es multiproceso.
Más hilos no conducen necesariamente a mejores tiempos de ejecución, hay un medio feliz para cada situación dependiendo del volumen de números que desee calcular.
Si compara los tiempos entre esta versión que se ejecuta con un hilo y la versión original, los únicos factores que podrían causar una diferencia en el tiempo son la sobrecarga del inicio del hilo 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 para el algoritmo va a Dr_Asik) está aquí . Además, escribí algunas pruebas de velocidad con un doble control para 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 Tema - 39.000 / 39.079
2 hilos - 19.750 / 19.890
10 hilos - 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 aproximadamente 50 hilos, más o menos diez o más.
Otras optimizaciones : mediante el uso de matrices y acceso directo utilizando el índice de bucle en lugar de buscar en un vector y almacenando sumas previas, el siguiente código (inspirado en la respuesta del Dr. Asik pero probablemente no optimizado) es 2445 veces más rápido que el C ++ original. código, aproximadamente 400 veces más rápido que el código de 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;
}
#!/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"
Hice un par de cambios menores en su ejemplo de código original de Python que hacen una mejora 16x mejor que el rendimiento del código. Los cambios que hice llevaron el caso a partir de 100.000 aproximadamente 9,64 segundos a aproximadamente 3,38 segundos.
El cambio principal era hacer que los mod 10 y el acumulador cambios para ejecutarse en un bucle while. Hice un par de otros cambios que mejoraron el tiempo de ejecución en sólo fracciones de centésimas de segundo. El primer cambio menor estaba cambiando el principal de bucle desde una lista por comprensión gama a un iterador xrange. El segundo cambio menor estaba sustituyendo la clase conjunto de la clase lista para ambas las variables conocidas y de historia. También he experimentado con comprensiones iterador puede calcular previamente y las plazas, pero ambos tenían efectos negativos sobre la eficiencia. Me parece estar ejecutando una versión más lenta de pitón o en un procesador más lento que algunos de los otros contribuidores. Estaría interés en los resultados de la comparación de tiempo de otra persona de mi código Python contra una de las versiones optimizadas C ++ del mismo algoritmo.También he intentado usar las -O -OO y optimizaciones pitón pero tenían el efecto contrario al deseado.
¿Por qué todos utilizando un vector en la versión c ++? tiempo de búsqueda es O (N).
A pesar de que no es tan eficiente como el conjunto pitón, utilizar std :: set. tiempo de búsqueda es O (log (N)).
Tropecé con esta página mientras estaba aburrido y pensé que jugaría en js. El algoritmo es mío, y no lo he examinado a fondo contra nada más que mis propios cálculos (por lo que podría ser incorrecto). Calcula los primeros 1e7 números felices y los almacena en h. Si desea cambiarlo, cambie los 7s.
m=1e7,C=7*81,h=[1],t=true,U=[,,,,t],n=w=2;
while(n<m){
z=w,s=0;while(z)y=z%10,s+=y*y,z=0|z/10;w=s;
if(U[w]){if(n<C)U[n]=t;w=++n;}else if(w<n)h.push(n),w=++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 programa python original en mi sistema cuando ejecuta el tiempo d8 happygolf.js o js -a - j -p happygolf.js en spidermonkey).
Estaré maravillado de las habilidades analíticas de cualquiera que pueda entender por qué este algoritmo funciona tan bien sin hacer referencia a la versión fortran más larga, comentada.
Estaba intrigado por lo rápido que era, así que aprendí fortran para obtener una comparación del mismo algoritmo, sé amable si hay errores notorios para novatos, es mi primer programa fortran. http://pastebin.com/q9WFaP5C Es una memoria estática sabia, así que para ser justo con los demás, está en un guión de compilación de auto compilación, si no tienes gcc / bash / etc, quita el preprocesador y bash todo en la parte superior, establece las macros manualmente y compila como fortran95.
Incluso si incluye el tiempo de compilación, supera a la mayoría de los demás aquí. Si no lo hace, 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 programas C ++).
Sorprendentemente, muchas de las optimizaciones que probé en la versión fortran (incluyendo algunas como desenrollar bucles que dejé fuera de la versión pegada debido a su pequeño efecto y legibilidad) fueron perjudiciales para la versión js. Este ejercicio muestra que los compiladores de trazas modernos son extremadamente buenos (dentro de un factor de 7-10 de fortán de memoria estática cuidadosamente optimizado) si se quita de su camino y no intente ningún truco. salga de su camino y trate de hacer cosas complicadas. Finalmente, aquí hay una versión js mucho más agradable 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, a pesar de que es bastante alto, lo hizo casi tan bien como el algoritmo imperativo en spidermonkey (con optimizaciones activadas) y cercano (1.2 veces más largo) en v8.
Moraleja de la historia, supongo que 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 sus propios trucos para reducirlos), por lo que a veces hacer algo más directo o utilizar sus funciones de alto nivel es igual de rápido. También la micro-optimización no siempre ayuda.
* A menos que mi instalación de Python sea inusualmente lenta, los tiempos directos son algo sin sentido ya que es una eee de primera generación. 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 en disco.
8-12s para ambas versiones js. 1e7 números felices, sin salida con la optimización completa 10-100s para ambas versiones js 1e7 con menos / sin optimización (dependiendo de la definición de no optimización, el 100 fue con eval ()) sin salida
Me interesaría ver los horarios de estos programas en una computadora real.
Aquí hay una versión de 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;
}
}
}
He comparado contra el código C ++ de Dr_Asik. Para un límite superior de 100.000 versión el C ++ corrió en alrededor de 2,9 segundos y la versión C # en 0,35 segundos. Ambos fueron compilados utilizando Dev Studio 2005 utilizando opciones de generación de liberación predeterminado y ambos fueron ejecutados desde un símbolo del sistema.
Para 100000 elementos, el código Python tomó 6.9 segundos mientras que C ++ originalmente tardó 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 C ++ original.
Lo más importante es compilar en modo Release, con todas las optimizaciones. Este código es, literalmente, órdenes de magnitud más lentas en el modo de depuración.
A continuación, explicaré las optimizaciones que hice.
- Movió todas las declaraciones de vectores fuera del ciclo; los reemplazó 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: value * value.
- En lugar de tener un vector de cuadrados y llamar a suma sobre él, sumo los valores en el lugar usando solo un número entero.
- Evitó todas las operaciones de cadena, que son muy lentas en comparación con las operaciones enteras. 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 volver a int.
- Evitó todas las copias vectoriales, primero reemplazando pasar por valor con pasar por referencia, y finalmente eliminando por completo las funciones auxiliares.
- Eliminado algunas variables temporales.
- Y probablemente muchos pequeños detalles que olvidé. Compare su código y el mío uno al lado del otro para ver exactamente lo que hice.
Puede ser posible optimizar el código aún más mediante el uso de matrices preasignadas en lugar de vectores, pero esto sería un poco más de trabajo y lo dejo como un ejercicio para el lector. :PAG
Aquí está el código optimizado:
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <algorithm>
#include <windows.h>
using namespace std;
void calcMain(int upperBound, vector<int>& known);
int main()
{
while(true)
{
vector<int> 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<int>& known)
{
vector<int> 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 respuesta separada , por lo que esta respuesta está en desuso.
Reescribí tu algoritmo haciéndolo caché cada vez que encuentra el número para ser feliz o infeliz. También traté de hacerlo lo más pitónico posible, por ejemplo, creando funciones separadas digits() y happy() . Perdón por usar Python 3, pero también puedo mostrar un par de cosas útiles.
Esta versión es mucho más rápida . Funciona a 1.7s, que es 10 veces más rápido que tu programa original que toma 18s (bueno, mi MacBook es bastante vieja y lenta :))
#!/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))