Usé una función en Python/Numpy para resolver un problema en la teoría de juegos combinatorios .
import numpy as np from time import time def problem(c): start = time() N = np.array([0, 0]) U = np.arange(c) for _ in U: bits = np.bitwise_xor(N[:-1], N[-2::-1]) N = np.append(N, np.setdiff1d(U, bits).min()) return len(*np.where(N==0)), time()-start problem(10000)Luego lo escribí en Julia porque pensé que sería más rápido debido a que Julia usaba la compilación justo a tiempo.
function problem(c) N = [0] U = Vector(0:c) for _ in U elems = N[1:length(N)-1] bits = elems .⊻ reverse(elems) push!(N, minimum(setdiff(U, bits))) end return sum(N .== 0) end @time problem(10000)Pero la segunda versión era mucho más lenta. Para c = 10000, la versión de Python tarda 2,5 segundos. en un procesador Core i5 y la versión de Julia tarda 4,5 segundos. Dado que las operaciones Numpy se implementan en C, me pregunto si Python es realmente más rápido o si estoy escribiendo una función con una complejidad de pérdida de tiempo.
La implementación en Julia asigna mucha memoria. ¿Cómo reducir el número de asignaciones para mejorar su rendimiento?
El código original se puede reescribir de la siguiente manera:
function problem2(c) N = zeros(Int, c+2) notseen = falses(c+1) for lN in 1:c+1 notseen .= true @inbounds for i in 1:lN-1 b = N[i] ⊻ N[lN-i] b <= c && (notseen[b+1] = false) end idx = findfirst(notseen) isnothing(idx) || (N[lN+1] = idx-1) end return count(==(0), N) endPrimero verifique si las funciones producen los mismos resultados:
julia> problem(10000), problem2(10000) (1475, 1475) (También he comprobado que el vector N generado es idéntico)
Ahora vamos a comparar ambas funciones:
julia> using BenchmarkTools julia> @btime problem(10000) 4.938 s (163884 allocations: 3.25 GiB) 1475 julia> @btime problem2(10000) 76.275 ms (4 allocations: 79.59 KiB) 1475Así que resulta ser más de 60 veces más rápido.
Lo que hago para mejorar el rendimiento es evitar asignaciones. En Julia es fácil y eficiente. Si alguna parte del código no está clara, por favor comente. Tenga en cuenta que me concentré en mostrar cómo mejorar el rendimiento del código de Julia (y no intentar simplemente replicar el código de Python, ya que, como se comentó en la publicación original, hacer comparaciones de rendimiento del lenguaje es muy complicado). Creo que es mejor concentrarse en esta discusión sobre cómo hacer que el código de Julia sea rápido.
De hecho, cambiar a Vector{Bool} y eliminar la condición en la relación b y c (que matemáticamente se cumple para estos valores de c ) da una mejor velocidad:
julia> function problem3(c) N = zeros(Int, c+2) notseen = Vector{Bool}(undef, c+1) for lN in 1:c+1 notseen .= true @inbounds for i in 1:lN-1 b = N[i] ⊻ N[lN-i] notseen[b+1] = false end idx = findfirst(notseen) isnothing(idx) || (N[lN+1] = idx-1) end return count(==(0), N) end problem3 (generic function with 1 method) julia> @btime problem3(10000) 20.714 ms (3 allocations: 88.17 KiB) 1475