elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Scripting
| | |-+  ¿Como obtener una combinacion mediante su indice?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: ¿Como obtener una combinacion mediante su indice?  (Leído 4,400 veces)
Yidu

Desconectado Desconectado

Mensajes: 133


Ver Perfil
¿Como obtener una combinacion mediante su indice?
« en: 17 Julio 2015, 21:32 pm »

Pues me he estancado.

Aunque ya he realizado alguna consulta por la web, no le veo solucion a mi duda. O todavia no tengo los conocimientos para desarrollar el codigo.
Mi duda:

Escogemos 100 numeros del 1 al 100. Y acto seguido pedimos las combinaciones de 5 grupos. Total 75287520 combinaciones. Correcto. Pero,  si por ejemplo, quiero que me de la combinacion con su indice 1000000 me tarda unos 9 segundos a recorrer dichas combinaciones con un ciclo FOR (que tambien probe con un WHILE).

¿Como le puedo pedir a un script que me devuelva de forma inmediata las combinaciones a traves del indice que se le indica? Ya no hablo de arreglos (que se podria hacer para pocos vectores).

La duda me viene por que no se como los programas construyen las combinaciones o el algoritmo que usan.
 
En el ejemplo que detallo, para encontrar la combinacion que se haya en la posicion o indice 1000000 tarda unos 9 segundos ¿Se puede hacer que de forma inmediata nos la de? Con un FOR, creo, desde luego que no. Ya que debe recorrer todas ellas hasta llegar a la posicion 1000000

Código
  1. import itertools
  2. from datetime import datetime
  3.  
  4.  
  5. inicio = datetime.now()
  6. muestra = tuple(range(1, 101))
  7. for indice, x in enumerate(itertools.combinations(muestra, 5),1):
  8.    print(indice, x)
  9.    if indice == 1000000:
  10.        print('La combinacion con indice', indice, 'es', x)
  11.        break
  12.  
  13. final = datetime.now()
  14. tiempo = final - inicio
  15. print(tiempo)

Salida:

Código
  1. ...
  2. 999994 (1, 9, 18, 21, 29)
  3. 999995 (1, 9, 18, 21, 30)
  4. 999996 (1, 9, 18, 21, 31)
  5. 999997 (1, 9, 18, 21, 32)
  6. 999998 (1, 9, 18, 21, 33)
  7. 999999 (1, 9, 18, 21, 34)
  8. 1000000 (1, 9, 18, 21, 35)
  9. La combinacion con indice 1000000 es (1, 9, 18, 21, 35)
  10. 0:00:09.510784
  11.  

Si pedimos un indice mayor o jugamos con otras combinaciones, nos puede arrojar horas, dias o semanas en devolvernos la combinacion con el indice pedido ¿No?



En línea

DarK_FirefoX


Desconectado Desconectado

Mensajes: 1.263


Be the change you wanna see in te world


Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #1 en: 18 Julio 2015, 01:51 am »

¿Como le puedo pedir a un script que me devuelva de forma inmediata las combinaciones a traves del indice que se le indica? Ya no hablo de arreglos (que se podria hacer para pocos vectores).

La respuesta corta es NO se puede, ahora de una manera dinámica puedes calcular las combinaciones una vez y almacenarlas (en un array o en otra estructura de datos (preferiblemente que sea más rápido buscar que en un array)) y una vez que quieras una combinación en particular indexas ahí y la devuelves, no obstante, ten en cuenta que calcular todas las combinaciones siempre se va a demorar al menos una vez.

Si pedimos un indice mayor o jugamos con otras combinaciones, nos puede arrojar horas, dias o semanas en devolvernos la combinacion con el indice pedido ¿No?

Si, incluso se te puede acabar el espacio en la pila (si está implementado recursivamente) y darte una excepción de tipo StackOverflow

Nota: También puede que distintas maneras de obtener las combinaciones te arroje una combinación "con el indice" 1000000 y de otra forma de arroje otra combinación diferente "con el indice" 1000000.

Espero haberte aclarado algo.

Salu2s


En línea

Eleкtro
Ex-Staff
*
Desconectado Desconectado

Mensajes: 9.788



Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #2 en: 18 Julio 2015, 14:30 pm »

1. La razón de que el código de arriba demore siglos es por que estás imprimiendo cada valor en el buffer de salida de la consola (stdOut), mientras eso sea así no puedes pretender que la respuesta sea "inmediata". elimina el "print" y resuelto.

2. Puedes disminuir considerablemente el tiempo de "respuesta" omitiendo la escritura en la consola, por ejemplo añadiendo los valores a una variables, y luego, si quieres, imprimir una única vez en la consola:
Código
  1. col    = enumerate(itertools.combinations(muestra, 5),1)
  2. values = ""
  3.  
  4. for count, value in col:
  5.    values += "\n" + str((count, value))
  6.    if count == 100000:
  7.     print values
  8.        print('La combinacion con indice', count, 'es', value)
  9.        break

2. Con la función enumerate, gracias al iterador estás devolviendo una colección que contiene elementos sin inicializar (Lazy Initialization), es de lo mejor que puedes hacer para acelerar el tiempo de ejecución del algoritmo, y creo que lo único en Python, aunque no domino del todo el lenguaje.

3. Precisamente la ausencia de un índice en la colección enumerable (__getitem__) es lo que permite hacerla iterable, sencillamente cómo ya te han comentado no puedes utilizar un índice, por otro lado, si que puedes implementarlo, ¿pero para que?, dejaría de ser lo que es.

Saludos
En línea

Yidu

Desconectado Desconectado

Mensajes: 133


Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #3 en: 18 Julio 2015, 18:27 pm »

1. La razón de que el código de arriba demore siglos es por que estás imprimiendo cada valor en el buffer de salida de la consola (stdOut), mientras eso sea así no puedes pretender que la respuesta sea "inmediata". elimina el "print" y resuelto.



2. Puedes disminuir considerablemente el tiempo de "respuesta" omitiendo la escritura en la consola, por ejemplo añadiendo los valores a una variables, y luego, si quieres, imprimir una única vez en la consola:

Muchas gracias. Desde luego que mejora considerablemente. De hecho he probado que halle la combinacion 100.000.000 y ha tardado 18 segundos en darla.

El script del punto 2,  lo probare. Ya que aun no sabia que se podia meter la funcion enumerate en una variable.

De todas formas, creo recordar, que probe alguna vez algo parecido a lo que comentas. Osea, que no imprimiera toda la iteracion de las combinaciones por pantalla. Pero claro, como la consola se quedaba en espera no sabia si iba a tardar un minuto en darme el resultado o en un mes  :rolleyes: En cambio, al imprimir por pantalla sabes cuantas combinaciones faltan para el testeo. Pero bueno, de momento me conformo con tu idea.

Muchas Gracias!  :D

En línea

Eleкtro
Ex-Staff
*
Desconectado Desconectado

Mensajes: 9.788



Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #4 en: 18 Julio 2015, 18:44 pm »

El script del punto 2,  lo probare. Ya que aun no sabia que se podia meter la funcion enumerate en una variable.

Hombre, es una función, y cómo toda función siempre puedes asignar su valor de retorno a una variable.

Pero esa variable no tiene relevancia alguna, solo la puse ahí para tener y usar una referencia de la colección enumerable (o dicho de otro modo, para formatear el código, acortándole el nombre a "col" y usando ese nombre).



como la consola se quedaba en espera no sabia si iba a tardar un minuto en darme el resultado o en un mes  :rolleyes: En cambio, al imprimir por pantalla sabes cuantas combinaciones faltan para el testeo.

Te entiendo perfectamente, pero imprimir en la consola implica un mayor, mucho mayor tiempo de procesado.

Lo que se suele hacer en estos casos con algoritmos "pesados" es mostrar una barra o texto de progreso indeterminado (ej: "Calculating values, please wait..."), ya que, o prescindes de la información visual en pantalla, o prescindes del rendimiento del algoiritmo en general, ¡tú decides a que darle mayor prioridad!.

Saludos!
« Última modificación: 18 Julio 2015, 18:46 pm por Eleкtro » En línea

Yidu

Desconectado Desconectado

Mensajes: 133


Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #5 en: 18 Julio 2015, 19:03 pm »


Te entiendo perfectamente, pero imprimir en la consola implica un mayor, mucho mayor tiempo de procesado.

Lo que se suele hacer en estos casos con algoritmos "pesados" es mostrar una barra o texto de progreso indeterminado (ej: "Calculating values, please wait..."), ya que, o prescindes de la información visual en pantalla, o prescindes del rendimiento del algoiritmo en general, ¡tú decides a que darle mayor prioridad!.

Saludos!

Ok. Supongo,  que dependiendo del ordenador, a mi me puede tardar 18 segundos y en otro mas potente, 1 segundo o menos.

RECTIFICACION:

No puedo poner nunca que me de la combianacion 100.000.000. Por el simple hecho que 100 numeros en grupos de 5, da como maximo 75287520 combinaciones.

En todo caso, por ejemplo, ponemos:

Código
  1. if indice == 75000000:
  2.        print('La combinacion con indice', indice, 'es', x)

Y si nos arroja:

Código
  1. La combinacion con indice 75000000 es (66, 77, 86, 90, 100)
  2. 0:00:20.209156
« Última modificación: 18 Julio 2015, 19:08 pm por Yidu » En línea

Eleкtro
Ex-Staff
*
Desconectado Desconectado

Mensajes: 9.788



Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #6 en: 18 Julio 2015, 19:32 pm »

Si he entendido bien no te importa demasiado mostrar las tuplas por consola, solo pretendes mostrar un "indicador" que determine el estado de la operación, en ese caso, y según lo que he mencioando antes sobre el rendimiento, quizás esto que escribí te sirva de ayuda:

Código
  1. # -*- coding: UTF-8-*-
  2.  
  3. import sys, itertools; from datetime import datetime
  4.  
  5. muestra = tuple(range(1, 101))
  6.  
  7. print("Init: " + str(datetime.now().time()))
  8.  
  9. for count, value in enumerate(itertools.combinations(muestra, 5),1):
  10.  
  11.    if (count == 20000000):
  12.        sys.stdout.write( "\rItem with index %s has value of %s\n" % ("{:,}".format(count), str(value)) )
  13.        break
  14.  
  15.    elif (count%1000000 == 0):
  16.        sys.stdout.write( "\r{:,} indexes checked...".format(count) )
  17.        sys.stdout.flush()
  18.  
  19. print("End: " + str(datetime.now().time()))



PD: La imagen no está modificada, en realidad tarda 4 segundos, pero al detenerlo intencionadamente para abrir el grabador de video, calculó segundos de más xD.

Saludos
« Última modificación: 18 Julio 2015, 19:37 pm por Eleкtro » En línea

Yidu

Desconectado Desconectado

Mensajes: 133


Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #7 en: 18 Julio 2015, 19:55 pm »

Si, pero en esos casos el tiempo de calculo es minimo...10 segundos, 20 segundos, incluso horas.

Pero imagina si has de tratar con combinaciones que arrojan cifras como esta:

2.245100430901328e+16

Es decir, 200 numeros en combinaciones de 10 grupos. Ahi, da igual que imprimas por pantalla, que no. Seguramente tardaria años en arrojar algun resultado.

Ya que cuando subimos un poco el numero de grupos,  las combinaciones son intratables.

Por cierto, a mi me tarda unos diez segundos el calculo,  que te tarda cuatro a ti. Eso ya es cosa de ordenadores, supongo.

Tengo una duda con esta linea:
Código
  1. elif (count%1000000 == 0):

¿Que hace realmente? Esta claro que trata de hallar el resto de la operacion ¿Pero el parametro 1000000 es siempre fijo?
« Última modificación: 18 Julio 2015, 21:51 pm por Yidu » En línea

Eleкtro
Ex-Staff
*
Desconectado Desconectado

Mensajes: 9.788



Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #8 en: 19 Julio 2015, 04:45 am »

Por cierto, a mi me tarda unos diez segundos el calculo,  que te tarda cuatro a ti. Eso ya es cosa de ordenadores, supongo.

Si, a mi me tarda 4 segundos el último código que publiqué (redondeando los milisegundos).

Por supuesto que el tiempo total depende del "PC", de la capacidad/potencia actual de dicho PC para el procesado de las operaciones de computación, siendo esto que acabo de decir una explicación abierta a diferentes interpretaciones (tareas en segundo plano del sistema, CPU, RAM, I/O, fragmentación del disco, etc).



Citar
Código
  1. elif (count%1000000 == 0):

¿Que hace realmente?

Determina si el valor "count" es un múltiplo de 1.000.000

¿Por qué 1.000.000 y no 100.000?, para reducir la escritura en el buffer y así incrementar el rendimiento general.

Saludos
« Última modificación: 19 Julio 2015, 04:49 am por Eleкtro » En línea

Yidu

Desconectado Desconectado

Mensajes: 133


Ver Perfil
Re: ¿Como obtener una combinacion mediante su indice?
« Respuesta #9 en: 19 Julio 2015, 12:02 pm »

Si, a mi me tarda 4 segundos el último código que publiqué (redondeando los

Determina si el valor "count" es un múltiplo de 1.000.000

¿Por qué 1.000.000 y no 100.000?, para reducir la escritura en el buffer y así incrementar el rendimiento general.



Ah, vale. Aunque no entiendo de todo el proceso. Veo que modificando este valor, el contador va mas deprisa o despacio. Dicho linea la he modificado a:

Código
  1. elif (count%100000000 == 0):

Para un testeo de:

Código
  1. if (count == 1.481076071314056e+16):

Ahora la salida por consola va con una cuenta de 100.000.000. Igual tengo que abortar el proceso, claro. Si todo fuera bien, me tendria que mostrar la ultima combinacion de esas 1.481076071314056e+16.

Me gusta la idea que has mostrado. Ya que de esa forma, no se te inunda la pantalla de tuplas y en cambio aparece como un contador. Lo siguiente seria crear el codigo para que reste las combinaciones que van apareciendo con el total de las mismas. Asi, sabriamos lo que falta para que termine el proceso.

Por cierto, para que este numero:  1.481076071314056e+16 lo podamos dejar en entero con hacer
Código
  1. int(1.481076071314056e+16)
  2. >>> 14810760713140560
es suficiente ¿No?


Saludos!
« Última modificación: 19 Julio 2015, 12:05 pm por Yidu » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines