Forma eficiente de iterar una lista comparando cosas

Nucklear #1 May '13 BugHunter

Buenas, estoy haciendo un script que parsea un log enorme y me divide cada línea de log en campos quedando una lista de listas con una estructura similar a esta:

[(timestamp, date, errorcode,description)(timestamp, date, errorcode,description)(timestamp, date, errorcode,description)]

Parseo varios logs por cada iteración y cada archivo tiene miles de líneas y necesito hacer dos cosas:

Descartar los errores informativos
Destacar los errores conocidos almacenados en un XML

El problema viene a la hora de iterar toda la lista de errores para compararla con los errores conocidos del XML ya que hace que 1000 lineas se conviertan en 1000*100, lo que es tremendamente ineficiente.

¿Como podría extraer los errores conocidos de una forma mas eficiente?

LOc0 #2 May '13

Me temo que tiene mal arreglo. Es el clásico CPU vs memoria... Si vas sobrado de la segunda, créate una caché con un sistema de direccionamiento lo más directo posible (en caso de errorcodes un simple array booleano). Con la caché podrás acelerar la parte de "descartar los errores conocidos de XML", pero no te emociones porque el log tendrás que procesarlo sí o sí.

pseudocódigo guarro

function skip_error(error_code)
   begin
       if(errorcode == INF_ERROR)
           return true;
       else if(cache[errorcode])
           return true;
       else if(errorcode in KNOWN_ERRORS)
           cache[errorcode] = true
           return true;
       else
           return false
   end

Salu2

PD: la lista de errores conocidos ordenada para poder hacer búsqueda binaria...
PD2: tb puedes cargarte la lista de errores conocidos en memoria nada más empezar...

1 1 respuesta

Nucklear #3 May '13 BugHunter

#2 Al final lo he solucionado cagando la lista de errores sacada del xml en una lista e iterando la lista pricipal para buscar el contenido directamente:

#Cargar lista del XML
xml = [child.attrib['code'] for child in root.iter('error')]

#Comparar errores conocidos con log

for err in error_list:
    if err[4] in xml:
        print err

1

JuAn4k4 #4 May '13

Si los errores tienen código, busca el código del error en un HashTable con los códigos de error que tengas en el xml (precargados)

1 respuesta

Nucklear #5 May '13 BugHunter

#4 Si, lo de la lista fue una prueba, al final voy a implementarlo como tu dices porque necesito mostrar la descripción del error en base a su código.

allmy #6 May '13 CSI

No se si aumentaría la eficiencia realmente, pero puedes:

Ordenar la lista en base al código de error.
Quitar repetidos.
Cruzar con el XML como hacías.

En el caso de haber muchos códigos repetidos harías la lista notablemente más corta. El orden por código te puede permitir no tener que iterar el archivo entero utilizando indices.

1 respuesta

JuAn4k4 #7 May '13

#6 No conoces los hash ?

1 respuesta

allmy #8 May '13 CSI

#7 2 de los 4 componentes de la lista van a ser siempre diferentes, el cuarto va junto con el tercero. Los hashtable en este caso no son mejores que ordenar la lista por errcode. Y bueno, aun en el caso de que fueran lo más eficiente, tener menos elementos siempre lo va a hacer más rápido, utilices el método que utilices.

JuAn4k4 #9 May '13

A ver, en el XML no va a haber repetidos, en la lista de errores si, pero orderar la lista entera ya te cuesta lo suyo, ya que son muchos logs de bastantes errores. Buscar si la linea de error (code) esta o no en el hasthable es O(1), ordenar la lista de errores te va a costar más, si o si.

Tienes el XML en un hashtable, y recorres la lista de errores buscando si estan o no en el hashtable y si no estan los añades a donde sea. O(n)

Ordenar la lista de errores : O(nlogn), Eliminar repetidos una vez ordenado O(n), recorrer los no repetidos O(n)

La unica opcion es que haya pocos tipos de errores y hagas la ordenación por buckets, para que sea O(n), y aun así, recorres la lista más veces.

Forma eficiente de iterar una lista comparando cosas

Usuarios habituales

Tags