0

estoy tratando de realizar un programa que reciba una lista de numeros ej: 100 435 200 3432 42423 1221 9999 -1223 e imprimia "SI" si algun numero de esta secuencia con otro de como resultado 1000 en caso contrario imprimir "NO". El programa trabaja muy bien pero con listas extensas me tira time out.

El código:

`
tupla = tuple([int(x) for x in input().split()])
for i in range(len(tupla)-1):
    for j in range(i+1,len(tupla)):
        if tupla[i]+tupla[j] == 1000:
            print('SI')
            exit()
print('NO')

`

5
  • al probar tu codigo me funciona perfectamente con listas bastante largas tanto en win10 como en linux
    – Mir cea
    Commented el 16 nov. 2019 a las 21:23
  • intenta probar con 999999 numeros Commented el 16 nov. 2019 a las 21:42
  • ¿Cómo es eso de que te da timeout? El programa puede tardar lo que sea, poco o mucho. Mientras no haya "nadie" midiendo si tarda demasiado, el concepto de timeout no se aplica. ¿Dónde lo estás ejecutando? ¿Es algún sistema de verificación automatizada que pone un tiempo límite para que el programa termine?
    – abulafia
    Commented el 16 nov. 2019 a las 23:56
  • Por otro lado, ya que tienes un bucle dentro de otro, meter 999999 números implica aproximadamente 999999**2 iteraciones, que son bastantes... (999998000001 para ser exactos). Aún si logras hacer un millón de iteraciones por segundo, tardarías en completarlas todas 999998 segundos, que son unos once días!
    – abulafia
    Commented el 17 nov. 2019 a las 0:00
  • ¿es un haiku? si lo es me interesa resolverlo
    – Durgeoble
    Commented el 17 nov. 2019 a las 9:52

1 respuesta 1

1

Del modo que lo has puesto realizas len(lista)^2 operaciones para comprobar los números

en lugar de eso es mucho mas practico y eficiente ver que número es necesario para alcanzar 1000 y ver si este se encuentra en la lista, adicionalmente se puede eliminar los números duplicados reduciendo así la lista y mirar si hay mas de un 500

from random import randrange
from time import time
start = time()
lista = list()
for i in range(9999999):
    if i in range(0, 999999999, 1000000):
        print(f"voy por {i}")
    lista.append(randrange(-9999999, 9999999))
print(f'lista lista en {int(time() - start)} segundos')
def hasta_mil(valor):
    result = 0
    if valor > 1000:
        result = -(valor - 1000)
    elif valor < 0:
        result = 1000 + valor
    elif valor < 1000:
        result = 1000 - valor
    return result
da_mil = False
start2 = time()
cuenta500 = lista.count(500)
if cuenta500 > 1:
    print(f"Se han encontrado {cuenta500} valores de 500, su suma da 1000")
    da_mil = True
else:
    largo = len(lista)
    print(f"Eliminando duplicados de la lista tiene {largo} elementos")
    lista2 = set(lista)
    print(f"Duplicados eliminados en {int(time() - start2)} segundos, eliminados {largo - len(lista2)} elementos, "
          f"quedan {len(lista2)} se ha reducido un {int(100*(len(lista) - len(lista2))/len(lista))}%")

    for i in lista2:
        if hasta_mil(i) in lista2:
            da_mil = True
            break

print(f"alguno da mil {'SI' if da_mil else 'NO'} realizado en {int(time() - start)} segundos")

con este código le cuesta mas generar la lista que comprobarla una lista de 10 millones de elementos la genera en unos 15 segundos y la resuelve en menos de 5, he hecho una comprobación y recorrer todos los elementos le ha llevado apenas 20 segundos

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.