Miglioramento della forza bruta rispetto alla generazione delle permutazioni?

0

Sto cercando di migliorare un algoritmo di forza bruta per le lettere dell'alfabeto inglese [a-z] [A-Z] e dei numeri [0-9]. La lunghezza delle permutazioni generate dovrebbe essere 8. Finora, ho costruito una semplice iterazione della forza bruta con Ruby e più tardi ho suddiviso l'iterazione master in più piccole di 100.000 elementi ciascuna. Inoltre, sto creando un Thread per ognuno e uso jruby per supportare il threading O / S nativo. Per favore non mi consiglia di lavorare con C o altre lingue, voglio solo portare il Rubino ai suoi limiti per ora.

Le mie statistiche finora sono:

  • ==== > Verranno generati 218.340.105.584.896 articoli
  • ~ 867.080 permutazioni / sec
  • richiederà circa 2914 giorni per il completamento.

Può sembrare sciocco, ma sto cercando di migliorare la forza bruta. Sto pensando alle seguenti cose:

  • La forza bruta genera molti di quelli invertiti. Ad esempio: [abcdefgh < = > hgfedcba]. Come posso elaborare questi?
  • Ci sono anche "parti" ripetute all'interno di una permutazione. Esempio: "abababab" è "ab" * lunghezza / 2 o "a1e4a1e4" è "a1e4" * lunghezza / 4.

Cercando in rete non sono riuscito a trovare alcun "miglioramento" della forza bruta. C'è qualche speranza?

    
posta Chris V. 31.05.2016 - 09:17
fonte

1 risposta

3

No, non c'è speranza. La cosa più veloce che puoi fare è sostituire i caratteri in una matrice invece di generare un nuovo oggetto stringa ad ogni iterazione. Ma qualunque elaborazione tu intenda fare con ogni permutazione richiederà presumibilmente molto più tempo di quanto necessario per generare la permutazione in primo luogo.

    
risposta data 31.05.2016 - 09:33
fonte

Leggi altre domande sui tag