Hola NEBIRE,
quisiera saber que tan eficiente es tu algoritmo para generar diccionarios, para comparar tiempos con el mío y eso.
Me he tomado la molestia de crear un pequeño Snippet en C++11 basado en conversión a base-n donde n es la longitud del charset. Me parece infeciente tener que iterar todo el keyspace en forma de long pero bueno.
Ten en cuenta que le he añadido un hilo para escribir el buffer en el fichero, sino se quedaría esperando hasta escribir todo el contenido. Escribir en el fichero en cada iteracción es un waste de syscalls.
.....
Generar todas las palabras formadas por el alfabeto (26 chars) de longitud 6.
real 0m19.649s
user 0m18.579s
sys 0m2.722s
Donde el mio tarda entre 10s y 12s aproximadamente:
real 0m11.876s
user 0m10.819s
sys 0m2.803s
Si tienes algo de tiempo pásame un code definitivo que guarde las palabras en un fichero, lo testeare en Fedora a ver si difiere mucho del benchmark que te acabo de presentar.
P.D= Luego esta el maskprocessor que lo hace en 6-7 segs, para mí el más rápido que existe en CPU.
Un saludo!
Bueno, yo separé en efecto la parte de generar las permutaciones del hecho de escribirlo a fichero.
De hecho es ineficiente (e inútil, si el propósito no es otro que probarlo) escribirlo a fichero... siempre sería preferible escribir una API, a la que se pueda llamar y pedir generar (por ejemplo), 1millón de claves a partir de la siguiente (recibida) y que entregue el array por referencia en memoria... Hablamos de que la idea final, sería lógicamente usar las claves en algún programa. Por tanto el coste de escribir a fichero, leer de fichero y espacio ocupado es nulo. Esto sólo debería hacerse con propósitos de prueba... supongo que me tniende sperfectamente.
Tengo varias versiones, ya que me fascina idear soluciones diferentes para un mismo problema. Pero te hablaré de dos versiones básicas... bueno 3...
--------------------------------------
A - En esta la idea básica es la simplicidad del algoritmo.
Y en ella se genera cada clave por completo, simplemente convirtiendo un número decimal (base numérica 10) en la base numérica x, siendo x el tamaño del diccionario (pongamos 26, si el alfabeto fuere por ejemplo A-Z). Es decir esta es la misma que tu has descrito más arriba y que veo en el código...
--------------------------------------
B - En esta otra, la idea básica es buscar velocidad, por supuesto tampoco debe ser muy complejo, ya que sino queda reñido también con la velocidad´.
Así la complejidad subyace sólo en la dificultad de enteder el algoritmo (a pelo, si no se dieran explicaciones).
Entonces para el caso, ni se genera un array de claves. Es la forma más eficiente para usarlo en el propio programa (destinado a probar las claves 'donde fuere').
Esto es, se genera una sola clave y es esa misma la que se va modificando. Ya que en efecto, la diferencia entre una clave y la siguiente solo es (casi siempre) 1 sólo carácter es superfluo generar de nuevo el resto de caracteres de la clave. Por lo tanto generar la nueva clave, cambia casi siempre 1 sólo carácter, lo que dispara la velocidad de cálculo respecto del anterior por 6 (para un tamaño de clave de 6)... algo más al tener en cuenta que tampoco lo almacenamos en un array de claves, aunque por simplicidad en vez de tomarlo como string, es un array de bytes/chars.
-----------------------------------------------------
C - El tercer algoritmo, es más simplificado aún y más veloz que cualquiera de los otros. En realidad usa cualquiera previo, pero éste está diseñado para claves muy largas...
La idea básica es que: 4+4=8: 4+3=7; 5+4=9, o 6+6=12...
Pongamos el caso de una clave de largo 8 caracteres... Luego si generamos pongamos un array para las claves de 4 caracteres (26^4= 456.976) tan sólo algo menos de medio millón, esto se puede generar en apenas una décima de segundo...
Así el paso 1º de este algoritmo es llamar a otro algoritmo, para que genere un array de claves manejable.
El segundo paso, es doble bucle, en ambos se usa el array generado, y la clave generada no se almacena como array (26^8= unos 208mil millones), tal como pasa en el algoritmo B, es para velocidad.
Este doble bucle, simplemente concatena las dos partes actuales.
Inicio bucle Externo:
Por cada ClaveExt en ArrayClaves
Inicio bucle Interno:
Por cada claveInt en ArrayClaves
ClaveActual = claveExt concat claveInt
// Usar desde aquí la clave que se acaba de generar para lo que se precisa...
Llamada a funcionX(Claveactual)
Fin bucle
fin bucle
Como se ve en este tercer algoritmo, generar una clave, se reduce a concatenar dos medias partes. Puede optimizarse mucho, si se usan funciones de copia de memoria, también evitando la creacción y destrucción de strings, o arrays...
Así ClaveActual debería ser una instancia que se crea una sola vez en todo el algoritmo y que se reutiliza una y otra vez. De hecho podemos ver que si ArrayClaves tiene un tamaño de medio millón (500.000), entonces claramente se veque en el bucle interno, siempre estamos concatenando (copiando ClaveExt, a pesar de que sabemos que no va a variar en el próximo medio millón de veces),
Entonces una varicación mejorada del algoritmo sería:
Inicio bucle Externo:
Hacer sitio a claveActual para que sea del tamaño requerido
Por cada ClaveExt en ArrayClaves
Inicio bucle Interno:
Copiar a Izqierda de ClaveActual, ClaveExt
Por cada claveInt en ArrayClaves
Copiar a Derecha de ClaveActual, ClaveInt
// Usar desde aquí la clave que se acaba de generar para lo que se precisa...
Llamada a funcionX(Claveactual)
Fin bucle
fin bucle
Es decir ahora hacemos una concatenación diferida en dos veces...
Otra variación si hacemos una API, que debiera entregar un array de claves de tamaño 8, conllevaría generar el array de claves de solo 4 caracteres, en claves de tamaño 8, dejando así hueco 4 caracteres (a derecha por ejemplo, y que son reutilizados en cada ciclo del bucle Interno), para rellenar en este doble bucle, y donde el bucle interno, sería una adaptación del algoritmo "B" (o sea encajarlo aquí, para hacer la variación de 1 sólo carácter en cada ciclo para generar una clave, en vez de copiar en cada cuiclo los x caracteres de la derecha.
Este algoritmo "C", tien su complejidad, sólo en la forma de adaptación, para hacerlo versátil y que pueda por tanto generar claves de tamaño X, partiendo siempre de la generación de arrays de largo 2,3,4 y 5, desde 2+2, hasta 5+5 y separado si la clave es mayor de 10, para 3+4+4 hasta 5+5+5, etc....
Es decir separando si se quiere hacer doble bucle, triple, bucle, cuádruple bucle, etc...
Si tamañoClaves es menor que 11 luego
doble bucle
O si tamañoClaves es menor que 15 luego
Triple Bucle
O si Tamañoclaves es menor que 20 luego
cuadruple Bucle
en otro caso
mesanje: no se ha previsto para claves demás de 20 caracteres
fin si
----------------------------------
Ahora mismo, no puedo hacer una prueba de velocidad, ya que tengo algunas operaciones calculando y le llevarán parte de la noche (las pruebas no reflejarían el rendimiento real si el procesador está trabajando al 80%), pero mañana, hago las pruebas que me reclamas y al efecto, limpio el código y cambio nombres de variables para facilitar su entendimiento...
(si creo recordar, de memoria, que poco tiempo atrás, quizás un mes o así, probé a generar con un alfabeto de 26 caracteres (A-Z), para un tamaño de clave de 7 caracteres... lo que proporciona algo más de 8 mil millones y tardó prácticamente unos 5 minutos, es decir aprox. 1.600.000.000 claves por minuto. (en un equipo del 2008, y con una versión hecha en VB6, al caso lo reharé en VB-2010, que es lo que tengo en casa). Dado que el algoritmo anunciado como "A", es la idea básica que tu has hecho, y que el algoritmo "C", está suficientemente descrito, pondré el código del algoritmo "B"...
Saludos...