Duda planteamiento del programa

[neodani]

Buenas,

Tengo una duda a la hora de enfocar como llevar a cabo el programa.

Dispones de un fichero1 de entrada txt con 100.000 lineas o más.
Estas lineas contienen 6 números separados por un espacio
Los números de una misma linea nunca se repiten y están ordenador de menor a mayor.


Quiero hacer dos cosas:

1) Quiero a partir de otro fichero2 con X lineas del mismo estilo que el fichero1 saber si alguna de estas coincide con alguna del fichero1


2) Saber si en el fichero1 contiene alguna linea repetida

Mi pregunta es como lo plantearíais para hacerlo de una forma eficiente recorriendo el fichero las menos veces posibles

Muchas gracias de antemano!!

[AlvaroG]

Se me ocurre una forma en la que el código sería sencillo.
Utilizar "for x in" para recorrer el archivo, ir guardando cada línea en una lista, utilizar "for x in" en esa lista para ver si la línea que lees pertenece ya a la lista y por lo tanto es repetida.

El segundo caso es similar, podrías leer uno de los archivos hacia una lista (de líneas) y luego recorrer el otro, preguntando en cada línea si pertenece a la lista o no.

El problema es que, aunque se trate de código muy sencillo y solamente leas cada archivo una vez, en el "peor caso" (aquel en el que no hay líneas repetidas) estarías recorriendo la lista de líneas (sumatoria de 1 hasta 100000) veces, o lo que es lo mismo n(n+1)/2 veces, con n=100000.

Este número es nada más ni nada menos que 5000050000 :


Saludos.

[neodani]

Iniciado por alvlin

Se me ocurre una forma en la que el código sería sencillo.
Utilizar "for x in" para recorrer el archivo, ir guardando cada línea en una lista, utilizar "for x in" en esa lista para ver si la línea que lees pertenece ya a la lista y por lo tanto es repetida.

El segundo caso es similar, podrías leer uno de los archivos hacia una lista (de líneas) y luego recorrer el otro, preguntando en cada línea si pertenece a la lista o no.

El problema es que, aunque se trate de código muy sencillo y solamente leas cada archivo una vez, en el "peor caso" (aquel en el que no hay líneas repetidas) estarías recorriendo la lista de líneas (sumatoria de 1 hasta 100000) veces, o lo que es lo mismo n(n+1)/2 veces, con n=100000.

Este número es nada más ni nada menos que 5000050000 :


Saludos.

Gracias Alvin.

Creo que con el primer caso te referias a mi segundo caso y viceversa.

Tengo el segundo caso, cuando una linea esta repetida en la lista, sería esto

Código python:

import sys
         
entrada=sys.argv[1]
file = open(entrada,'r')
combinaciones=[]
 
for linea in file:
    if linea in combinaciones:
        print "repetida: " + linea,
    else:
        combinaciones.append(linea)
 

Esta es como bien dices una manera.

Sobre el primer caso... podría tener en una lista todas las combinaciones 100.000 o más y en otra lista las que quiero buscar, pero para cada combinación que quiero comparar con el fichero debe recorselo entero.

En python no existe metodos de ordenación para buscar más rapido? tipo burbuja (el que mas me suena por el nombre) etc... ?

[AlvaroG]

Iniciado por neodani

Creo que con el primer caso te referias a mi segundo caso y viceversa.

Perdón por eso

Iniciado por neodani

Sobre el primer caso... podría tener en una lista todas las combinaciones 100.000 o más y en otra lista las que quiero buscar, pero para cada combinación que quiero comparar con el fichero debe recorselo entero.

No tiene por qué recorrerlo entero si primero guardas su contenido en una lista o tupla. Sería más rápido.

Iniciado por neodani

En python no existe metodos de ordenación para buscar más rapido? tipo burbuja (el que mas me suena por el nombre) etc... ?

Existe la operación sort() para listas (lista.sort()), que cambia la lista original (no devuelve una lista modificada)
Por aquí se describen algunas otras formas más complejas, aunque en inglés

http://xahlee.org/perl-python/sort_list.html
http://wiki.python.org/moin/HowTo/Sorting



Saludos.

[neodani]

Iniciado por alvlin

Perdón por eso


No tiene por qué recorrerlo entero si primero guardas su contenido en una lista o tupla. Sería más rápido.



Existe la operación sort() para listas (lista.sort()), que cambia la lista original (no devuelve una lista modificada)
Por aquí se describen algunas otras formas más complejas, aunque en inglés

http://xahlee.org/perl-python/sort_list.html
http://wiki.python.org/moin/HowTo/Sorting



Saludos.

He estado mirando ambas páginas pero no he visto una ordenación de varias listas a la vez. Me explico, esto funciona

>>> li=[1,9,2,3];
>>> li.sort();
>>> print li;
[1, 2, 3, 9]

El problema es que yo quiero ordenar las listas, no los elementos de ellas, porque ya estan ordenados.

>>> li=[13,15,20,22],[1,2,3,9],[1,3,5,6];
>>> li.sort();
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'tuple' object has no attribute 'sort'

[AlvaroG]

Iniciado por neodani

El problema es que yo quiero ordenar las listas, no los elementos de ellas, porque ya estan ordenados.

Código:

>>> li=[13,15,20,22],[1,2,3,9],[1,3,5,6];
>>> li.sort();
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'tuple' object has no attribute 'sort'

Ese código falla por otro motivo
Al asignar li de esa forma lo que haces es crear una tupla de listas. sort() modifica la lista original, pero las tuplas son inmutables => no existe el método sort para tuplas.

Tu código funcionaría si hicieras

li=[ [13,15,20,22],[1,2,3,9],[1,3,5,6] ]

(un comentario: el punto y coma al final de la línea no es requerido)


Saludos.

[neodani]

Iniciado por alvlin

Ese código falla por otro motivo
Al asignar li de esa forma lo que haces es crear una tupla de listas. sort() modifica la lista original, pero las tuplas son inmutables => no existe el método sort para tuplas.

Tu código funcionaría si hicieras

li=[ [13,15,20,22],[1,2,3,9],[1,3,5,6] ]

(un comentario: el punto y coma al final de la línea no es requerido)


Saludos.

Excelente :D

Muchisimas gracias