Cómo optimizar las operaciones en grandes (75,000 elementos) conjuntos de booleanos en Python?

Question

Hay una secuencia de comandos llamada svnmerge.py que estoy tratando de modificar y optimizar un poco. Aunque soy completamente nuevo en Python, no es fácil.

El problema actual parece estar relacionado con una clase llamada RevisionSet en el script. En esencia, lo que hace es crear una gran tabla hash (?) De valores booleanos de enteros. En el peor de los casos, uno para cada revisión en nuestro repositorio SVN, que ahora está cerca de 75,000.

Después de eso, realiza operaciones de conjunto en tales matrices enormes: suma, resta, intersección, etc. La implementación es la implementación más simple de O (n), que, naturalmente, se vuelve bastante lenta en tales conjuntos grandes. Toda la estructura de datos podría optimizarse debido a que existen largos períodos de valores continuos. Por ejemplo, todas las claves de 1 a 74,000 pueden contener true. También el script está escrito para Python 2.2, que es una versión bastante antigua y estamos usando 2.6 de todos modos, por lo que también podría haber algo que ganar allí.

Podría tratar de improvisar esto, pero sería difícil y tomaría mucho tiempo, sin mencionar que ya podría estar implementado en alguna parte. Aunque me gustaría la experiencia de aprendizaje, el resultado es más importante en este momento. ¿Qué sugieres que haga?

Answer 1

Puedes intentar hacerlo con numpy en lugar de python normal. Encontré que es muy rápido para operaciones como estas.

Por ejemplo:

# Create 1000000 numbers between 0 and 1000, takes 21ms 
x = numpy.random.randint(0, 1000, 1000000) 

# Get all items that are larger than 500, takes 2.58ms 
y = x > 500 

# Add 10 to those items, takes 26.1ms 
x[y] += 10 

ya que es con mucha más filas, creo que 75.000 no debería ser un problema ya sea :)

Answer 2

Por ejemplo, todas las teclas de 1 a 74.000 contienen verdadero

¿Por qué no trabajar en un subconjunto? Solo 74001 hasta el final.

Podar 74/75 de sus datos es mucho más fácil que tratar de escribir un algoritmo más inteligente que O (n).

Answer 3

Debe volver a escribir RevisionSet para tener un conjunto de revisiones. Creo que la representación interna para una revisión debe ser un número entero y se deben crear rangos de revisión según sea necesario.

No hay ninguna razón de peso para usar código que admita Python 2.3 y versiones anteriores.

Answer 4

Sólo un pensamiento. Solía ​​hacer este tipo de cosas usando run-coding en la manipulación de imágenes binarias. Es decir, almacenar cada conjunto como una serie de números: número de bits desactivados, número de bits activados, número de bits desactivados, etc.

Luego puede hacer todo tipo de operaciones booleanas como decoraciones en una combinación simple algoritmo.

Answer 5

Aquí hay un reemplazo rápido para RevisionSet que lo convierte en un conjunto. Debería ser mucho más rápido. No lo probé por completo, pero funcionó con todas las pruebas que hice. Sin duda, hay otras formas de acelerar las cosas, pero creo que esto realmente ayudará porque en realidad aprovecha la rápida implementación de los conjuntos en lugar de hacer loops en Python que el código original estaba haciendo en funciones como __sub__ y __and__. El único problema con esto es que el iterador no está ordenado.Es posible que tenga que cambiar un poco del código para dar cuenta de esto. Estoy seguro de que hay otras formas de mejorar esto, pero espero que te dé un buen comienzo.

class RevisionSet(set): 
    """ 
    A set of revisions, held in dictionary form for easy manipulation. If we 
    were to rewrite this script for Python 2.3+, we would subclass this from 
    set (or UserSet). As this class does not include branch 
    information, it's assumed that one instance will be used per 
    branch. 
    """ 
    def __init__(self, parm): 
     """Constructs a RevisionSet from a string in property form, or from 
     a dictionary whose keys are the revisions. Raises ValueError if the 
     input string is invalid.""" 


     revision_range_split_re = re.compile('[-:]') 

     if isinstance(parm, set): 
      print "1" 
      self.update(parm.copy()) 
     elif isinstance(parm, list): 
      self.update(set(parm)) 
     else: 
      parm = parm.strip() 
      if parm: 
       for R in parm.split(","): 
        rev_or_revs = re.split(revision_range_split_re, R) 
        if len(rev_or_revs) == 1: 
         self.add(int(rev_or_revs[0])) 
        elif len(rev_or_revs) == 2: 
         self.update(set(range(int(rev_or_revs[0]), 
             int(rev_or_revs[1])+1))) 
        else: 
         raise ValueError, 'Ill formatted revision range: ' + R 

    def sorted(self): 
     return sorted(self) 

    def normalized(self): 
     """Returns a normalized version of the revision set, which is an 
     ordered list of couples (start,end), with the minimum number of 
     intervals.""" 
     revnums = sorted(self) 
     revnums.reverse() 
     ret = [] 
     while revnums: 
      s = e = revnums.pop() 
      while revnums and revnums[-1] in (e, e+1): 
       e = revnums.pop() 
      ret.append((s, e)) 
     return ret 

    def __str__(self): 
     """Convert the revision set to a string, using its normalized form.""" 
     L = [] 
     for s,e in self.normalized(): 
      if s == e: 
       L.append(str(s)) 
      else: 
       L.append(str(s) + "-" + str(e)) 
     return ",".join(L) 

Adición: Por cierto, he comparado haciendo uniones, intersecciones y restas de la RevisionSet original, y mi RevisionSet anterior, y el código de arriba es de 3x a 7x más rápido para aquellas operaciones cuando se opera en dos RevisionSets que tienen 75000 elementos. Sé que otras personas dicen que el numpy es el camino a seguir, pero si no tienes mucha experiencia con Python, como indica tu comentario, es posible que no quieras ir por esa ruta porque implicará muchos más cambios. Recomiendo probar mi código, ver si funciona y, si lo hace, ver si es lo suficientemente rápido para ti. Si no es así, entonces trataría de perfilar para ver qué se debe mejorar. Solo entonces consideraría usar numpy (que es un gran paquete que uso con bastante frecuencia).