Come ottimizzare le operazioni su gruppi di booleani di grandi dimensioni (75.000 elementi) in Python?

Question

C'è questo script chiamato svnmerge.py che sto cercando di ottimizzare e ottimizzare un po '. Sono completamente nuovo in Python, quindi non è facile.

Il problema corrente sembra essere correlato a una classe denominata RevisionSet nello script. In sostanza, ciò che fa è creare un ampio hashtable (?) Di valori booleani con chiave intera. Nel peggiore dei casi, uno per ogni revisione nel nostro repository SVN, che ora è vicino a 75.000.

Dopodiché esegue operazioni impostate su array di grandi dimensioni: addizione, sottrazione, intersezione e così via. L'implementazione è la più semplice implementazione O (n), che, naturalmente, diventa piuttosto lenta su insiemi così grandi. L'intera struttura dei dati potrebbe essere ottimizzata perché ci sono lunghe serie di valori continui. Ad esempio, tutte le chiavi da 1 a 74.000 potrebbero contenere true. Anche lo script è scritto per Python 2.2, che è una versione piuttosto vecchia e comunque stiamo usando 2.6, quindi potrebbe esserci qualcosa da guadagnare anche lì.

Potrei provare a mettere insieme tutto questo, ma sarebbe difficile e richiedere molto tempo, senza contare che potrebbe essere già implementato da qualche parte. Anche se mi piacerebbe l'esperienza di apprendimento, il risultato è più importante adesso. Cosa suggeriresti di fare?

Answer 1

Si potrebbe provare a farlo con numpy invece di plain python. Ho trovato che fosse molto veloce per operazioni come queste.

Ad esempio:

# 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 

Dal momento che è con molta più righe, penso che 75000 non dovrebbe essere un problema neanche :)

Answer 2

Per esempio, tutti i tasti da 1 a 74.000 contengono true

Perché non lavorare su un sottoinsieme? Solo 74001 fino alla fine.

La potatura del 74/75 ° dei dati è molto più semplice rispetto al tentativo di scrivere un algoritmo più intelligente di O (n).

Answer 3

È necessario riscrivere RevisionSet per disporre di una serie di revisioni. Penso che la rappresentazione interna per una revisione dovrebbe essere un numero intero e gli intervalli di revisione dovrebbero essere creati secondo necessità.

Non c'è alcun motivo valido per utilizzare il codice che supporta python 2.3 e precedenti.

Answer 4

Solo un pensiero. Ero solito fare questo genere di cose usando la codifica runica nella manipolazione di immagini binarie. Vale a dire, memorizza ogni serie come una serie di numeri: numero di bit disattivati, numero di bit attivati, numero di bit disattivati, ecc.

Quindi è possibile eseguire tutti i tipi di operazioni booleane su di essi come decorazioni su una semplice unione. algoritmo.

Answer 5

Ecco una rapida sostituzione di RevisionSet che lo rende un set. Dovrebbe essere molto più veloce. Non l'ho provato completamente, ma ha funzionato con tutti i test che ho fatto. Ci sono indubbiamente altri modi per velocizzare le cose, ma penso che ciò sarà di grande aiuto perché in realtà sfrutta la rapida implementazione degli insiemi piuttosto che fare loop in Python che il codice originale stava facendo in funzioni come __sub__ e __and__. L'unico problema è che l'iteratore non è ordinato.Potrebbe essere necessario modificare un po 'il codice per tener conto di ciò. Sono sicuro che ci sono altri modi per migliorare questo, ma spero che ti dia un buon inizio.

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) 

Aggiunta: A proposito, ho confrontato facendo sindacati, incroci e sottrazioni della RevisionSet originale e la mia RevisionSet sopra, e il codice di cui sopra è da 3x a 7x più veloce per le operazioni quando si opera su due RevisionSet che hanno 75000 elementi. So che altre persone stanno dicendo che Numpy è la strada da percorrere, ma se non hai molta esperienza con Python, come indica il tuo commento, allora potresti non voler seguire quella strada perché questo comporterà molte più modifiche. Consiglierei di provare il mio codice, vedendo se funziona e se lo fa, quindi vedere se è abbastanza veloce per te. Se non lo è, proverei a profilare per vedere cosa deve essere migliorato. Solo allora dovrei considerare l'uso di numpy (che è un ottimo pacchetto che uso abbastanza spesso).