Quanto dovrebbe essere veloce uno script di factoring Python?

Question

Quanto dovrebbe essere veloce uno script di factoring Python?

#1 da (3 voti)
#2 da (1 voti)

0

Quanto è efficiente "abbastanza buono" a tutti gli effetti? Ho scritto una sceneggiatura per elencare semplicemente tutti i numeri che dividono in un input, x, come coppie (i, n // i) ed ero solo curioso di sapere quanto sarebbe stato efficiente andare? qual è il tasso accettabile con cui lo script inizia a perdere la sua efficienza? Questo è il mio codice (anche se i consigli sono apprezzati, voglio solo dare un'idea di come funzioni).

import time
print('''This program determines all basic factors of a given number, x, as ordered            pairs, (a, b) where ab=x.
Type "quit" to exit.''')

timer = input('Would you like a timer? (y/n) ')
while  1:
    try:
        x =(input('x = '))                                               
        T0 = time.time()
        b = []
        n = int(x)**0.5
        ran = list(range(1, int(n)+1))
        if int(x) % 2 == 1:                                          
            ran = ran[::2]
        for i in ran:
            if int(x) % i == 0:
                m = (i, int(x)//i)
                b.append(m)
        else:
            pass
    except ValueError as error_1:
        if x == 'quit':
            break
        else:
            print(error_1)
    except EOFError as error_2:
        print(error_2)
    except OverflowError as error_3:
        print(error_3)
    except MemoryError as error_4:
        print(error_4)
    T1 = time.time()
    total = T1-T0
    print(b)
    print(str(len(b)) + ' pairs.')
    if timer == 'y':
    print("%.5f" % total + ' seconds.')

alcuni risultati sono:

x = 9
[(1, 9), (3, 3)]
2 pairs.
0.00000 seconds.

x = 8234324543
[(1, 8234324543)]
1 pairs.
0.07404 seconds.

x = 438756349875
[(1, 438756349875), (3, 146252116625), (5, 87751269975), (15, 29250423325), (25,         17550253995), (75, 5850084665), (125, 3510050799), (375, 1170016933), (557, 787713375),   (1671, 262571125), (2785, 157542675), (8355, 52514225), (13925, 31508535), (41775,   10502845), (69625, 6301707), (208875, 2100569)]
16 pairs.
0.88859 seconds.

Quindi questo programma può essere piuttosto veloce, ma poi la velocità diminuisce piuttosto rapidamente una volta che si arriva a numeri più alti. Ad ogni modo, mi stavo chiedendo cosa è considerato accettabile dagli standard di oggi?

performance python algorithms math

posta Plopperzz 18.08.2013 - 23:00

fonte

2 risposte

Leggi altre domande sui tag performance python algorithms math

Distribuzione del software per PC senza un sito web [chiuso] Tale modifica è consentita dalla GPL? Quali licenze consentono ciò che no?

score 3 · Answer 1

So this program can be pretty quick, but then the speed drops rather rapidly once you get up to higher numbers

Questo è normale. Fare la fattorizzazione di un numero elevato è un'attività che richiede molto tempo. Infatti molti algoritmi di crittografia (come l'RSA ampiamente utilizzato) si basano sulla difficoltà di fattorizzare interi di grandi dimensioni.

score 1 · Answer 2

Non esiste una risposta assoluta - le prestazioni sono relative. In definitiva, la risposta dipende dalle esigenze degli utenti.

Se si calcola sempre solo numeri piccoli, e supponendo che non si stia tentando di farlo milioni di volte al secondo, la velocità non deve essere molto buona, specialmente se stanno digitando numeri in una console. Tutto sotto un secondo è accettabile. Se usano una GUI, i tempi di risposta dovrebbero generalmente essere inferiori a 100ms per dare la sensazione che i risultati siano "immediati".

Se stai usando il codice per scricchiolare milioni di numeri o numeri con centinaia di cifre, le prestazioni sono, ovviamente, più importanti. Tuttavia, se stai facendo questo scricchiolio durante la notte, la velocità diventa meno importante, assumendo che il lavoro venga svolto prima che le persone ne abbiano bisogno.