Limiti computazionali per un'enorme permutazione k-esima?

0

Sarebbe possibile calcolare direttamente una permutazione k come k = 10 ^ 200000000?

Se no, Quale sarebbe il limite computazionale per calcolare l'enorme k-esima permutazione in un computer di oggi? Come posso stimarlo?

Come, qual è la più grande permutazione k-th che potrei calcolare in meno di un giorno?

* Nota, il processo di permutatio sarebbe qualcosa del tipo: link (se ce n'è una migliore, per favore indicatemi)

Cercherò di chiarire. Genererò un file con un numero davvero enorme composto da cifre che si riempiono da 200 Mb di spazio su numeri assurdi come 300000 !. (200 x 10 ^ 6 cifre a 300k! O 1M!)

Voglio calcolare direttamente la permutazione che quel numero rappresenta. È possibile calcolare in poche ore? Ho un algoritmo di tempo quasi lineare, se necessario, per il lavoro che voglio che faccia.

Ma ho letto circa 9! le permutazioni richiedono 10 minuti. Quindi probabilmente una permutazione sul limite superiore di questo non può essere calcolata in un tempo ragionevole (meno di un giorno). Quale sarebbe il limite superiore, quali permutazioni più di x! non è stato possibile calcolare direttamente nel mio ragionevole momento? Come stimare questo? Cosa posso aspettarmi di calcolare, solo fino a 10k! 100k! ? 300000!?

    
posta Cristo 11.09.2016 - 21:34
fonte

1 risposta

2

L'algoritmo descritto nel Q & A di riferimento ha una dipendenza temporale peggiore di O (n ^ 2). Calcolare un fattoriale è peggio di O (n) (da Wikipedia ), e devi calcolare tutti i fattoriali fino a n per ogni permutazione, in ordine decrescente.

Per evitare questa dipendenza temporale, puoi calcolare tutti questi fattoriali in ordine crescente e memorizzarli.

Ho scritto un semplice programma per ottenere delle cifre reali e, sul mio laptop per sviluppatori con .NET BigInteger, ho ricevuto:

  • Calcolare 1 000 000 fattoriali richiede ~ 22 minuti;
  • La memoria richiesta per mantenerli tutti sarebbe ~ 1.12 TB;
  • Calcolare la permutazione effettiva richiederebbe circa 52 minuti (estrapolati da 100 passaggi distribuiti nell'intero intervallo fattoriale).

Il modo più veloce per scrivere e rileggere questi fattoriali dal disco sarebbe probabilmente lasciare che il meccanismo di paging lo faccia (secondo Limiti di memoria per versioni di Windows e Windows Server , dovresti essere in grado di andare fino a 15.5 TB). Quindi, se è possibile ottenere una macchina con un disco SSD da 2 TB per il file di paging:

  • La scrittura di 1.12 TB di fattoriali richiederebbe circa 19 minuti a 1 GB / sec;
  • La sua lettura potrebbe richiedere ~ 9,5 minuti a 2 GB / sec.

Quindi, ~ 100 minuti consentirebbe di calcolare una permutazione fino a k ~ 10 ^ 5 565 709 da un insieme di 1 000 000 simboli ( 1000000! ~ 8.263e5565708 ).

La RAM necessaria all'algoritmo sarebbe abbastanza ragionevole (principalmente 2 fattoriali in memoria allo stesso tempo, ~ 5 MB).

Quindi potresti probabilmente calcolare in un giorno una permutazione da un insieme di pochi milioni di simboli, o più con una macchina più veloce e una libreria aritmetica di precisione arbitraria migliore,

    
risposta data 18.09.2016 - 19:06
fonte

Leggi altre domande sui tag