for - Come ottenere Python REALMENTE veloce su un semplice loop



python numba (4)

Ehi, l'ho capito entro il limite di tempo. Ho usato il seguente:

  • Psyco with Python 2.5.
  • un ciclo semplice con una variabile per contare
  • il mio codice era tutto in una funzione main () (tranne l'importazione di psyco) che ho chiamato.

L'ultimo è quello che ha fatto la differenza. Credo che abbia a che fare con la visibilità variabile, ma non ne sono completamente sicuro. Il mio tempo era 10,81 secondi. Si potrebbe ottenere per essere più veloce con una comprensione di lista.

Modificare:

L'utilizzo di una comprensione delle liste ha portato il mio tempo a 8,23 secondi. Portando la riga from sys import stdin, stdout all'interno della funzione si è un po 'attenuato per ridurre il tempo a 8.12 secondi.

https://src-bin.com

Sto lavorando a un problema INTEST , INTEST . L'obiettivo è specificare il numero di casi di test (n) e un divisore (k), quindi inserire i numeri del programma n. Il programma accetterà ogni numero su una nuova riga di stdin e dopo aver ricevuto l'ennesimo numero, ti dirà quanti sono stati divisibili per k.

L'unica sfida in questo problema è ottenere che il tuo codice sia VELOCE perché k può essere qualsiasi cosa fino a 10 ^ 7 e n può essere alto come 10 ^ 9.

Sto provando a scriverlo in Python e ho problemi a velocizzarlo. Qualche idea?

Modifica 2: finalmente l'ho fatto passare a 10,54 secondi. Ho usato quasi tutte le tue risposte per arrivarci, e quindi era difficile sceglierne una come 'corretta', ma credo che quella che ho scelto la riassuma al meglio. Grazie a tutti voi. Il codice di passaggio finale è sotto.

Modifica: ho incluso alcuni degli aggiornamenti suggeriti nel codice incluso.

Le estensioni e i moduli di terze parti non sono consentiti. Il codice è anche gestito dalla macchina giudice SPOJ, quindi non ho la possibilità di cambiare interpreti.

import sys
import psyco
psyco.full()

def main():
    from sys import stdin, stdout
    first_in = stdin.readline()
    thing = first_in.split()
    n = int(thing[0])
    k = int(thing[1])
    total = 0

    list = stdin.readlines()
    for item in list:
        if int(item) % k == 0:
            total += 1

    stdout.write(str(total) + "\n")

if __name__ == "__main__":
    main()

Answer #1

Per altri lettori, INTEST . È destinato a essere un test del throughput I / O.

Sul mio sistema, sono stato in grado di ridurre del 15% il tempo di esecuzione sostituendo il ciclo con il seguente:

print sum(1 for line in sys.stdin if int(line) % k == 0)

Answer #2

Usa psyco , farà JIT il tuo codice, molto efficace quando c'è un grosso loop e calcoli.

Modifica : sembra che i moduli di terze parti non siano consentiti,

Quindi, puoi provare a convertire il tuo loop in list comprehensions, dovrebbe essere eseguito a livello C, quindi dovrebbe essere più veloce un po '.

sum(1 if int(line) % k == 0 else 0 for line in sys.stdin)

Answer #3

Usare le list comprehensions con psyco è controproducente.

Questo codice:

 count = 0
 for l in sys.stdin:
     count += not int(l)%k

funziona due volte più veloce di

count = sum(not int(l)%k for l in sys.stdin)

quando si usa psyco.





optimization