0
532
ViewsComprensión de lo que sucede en el Algoritmo Kadane (Python)
Tengo dificultades para entender lo que sucede en estos dos ejemplos que encontré del Algoritmo de Kadane. Soy nuevo en Python y espero que comprender este algoritmo complejo me ayude a ver/leer mejor los programas.
¿Por qué un ejemplo sería mejor que el otro, es solo List vs Range ? ¿Hay algo más que haga que uno de los ejemplos sea más eficiente? Además, algunas preguntas sobre lo que está sucediendo en los cálculos. (preguntas dentro de los ejemplos)
He usado PythonTutor para ayudarme a obtener una imagen de lo que sucede exactamente paso a paso.
Ejemplo 1:
En PythonTuter, cuando selecciona el siguiente paso en la captura de pantalla provista, el valor de so_far cambia a 1. ¿Cómo es esto? Dando la suma, pensé que estaba sumando -2 + 1, que es -1, así que cuando so_far se convierte en 1, ¿cómo es esto?
def max_sub(nums): max_sum = 0 so_far = nums[0] for x in nums[1:]: so_far = max(x, x + so_far) max_sum = max(so_far, max_sum) return max_sum nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] max_sub(nums) 6 
Ejemplo 2:
Pregunta similar para esta, cuando selecciono el paso SIGUIENTE, max_sum cambia de -2 a 4 ... pero cómo es eso si está agregando el elemento en el 2 (que es 4). Para mí, eso sería -2 + 4 = 2?
def maxSubArraySum(a,size): max_so_far =a[0] curr_max = a[0] for i in range(1,size): curr_max = max(a[i], curr_max + a[i]) max_so_far = max(max_so_far,curr_max) return max_so_far a = [-2, -3, 4, -1, -2, 1, 5, -3] print("Maximum contiguous sum is" , maxSubArraySum(a,len(a))) Maximum contiguous sum is 7 
Entonces, esta sería una pregunta de 2 partes que:
[1]Based on understandings, why would one be more pythonic and more efficient than the other? [2]How can I better understand the calculations happening in the examples?2 answers
Answer question0
Simplemente mire cada paso y podrá resolver este problema: [Notas] ¿Este programa parece funcionar basándose en la suposición de números enteros mixtos? solo positivos y negativos.
# starting so_far = -2 # init. to nums[0] max_sum = 0 # in the for-loop: x = 1 # starting with nums[1:] so_far = max(1, -1) -> 1 (x is 1, -2 + 1) max_sum = max(0, 1) -> 1 ..... continue .... each step is to find the max accumulated numbers sum, as it's evident in the max( ) statement. *There is no `sum` involved, except it tried to determine the current x is good (not negative) then so add it to the so_far.0
Más puntos de datos de medición de rendimiento para comparar estos dos enfoques diferentes muestran que el primer ejemplo es definitivamente más rápido ~ 22-24% más rápido que el segundo con un tamaño de entrada de 2k.
if __name__ == '__main__': L = list(range(-1_000, 1_000, 1)) random.shuffle(L) baseTestCase = partial(max_sub, nums=L) print(timeit.timeit(baseTestCase, number=100_000)) # 86.0588067 rangeTestCase = partial(max_SubArraySum, a=L, size=len(L)) print(timeit.timeit(rangeTestCase, number=100_000)) # 105.415955