Comment améliorer les performances de ce programme de comptage?

Question

Étant donné qu'un fichier ressemble à ceci:

1440927 1
1727557 3
1440927 2
9917156 4

Le premier champ est un identifiant qui est in range(0, 200000000). Le deuxième champ représente un type, qui est in range(1, 5). Et le type 1 et le type 2 appartiennent à une catégorie commune S1, tandis que le type 3 et le type 4 appartiennent à S2. Un seul ID peut avoir plusieurs enregistrements de type différent. Le fichier a une taille d'environ 200 Mo.

Le problème est de compter le nombre d'identifiants ayant un enregistrement de type 1 ou 2, et le nombre d'identifiants ayant un enregistrement de type 3 ou 4.

Mon code:

def gen(path):
    line_count = 0
    for line in open(path):
        tmp = line.split()
        id = int(tmp[0])
        yield id, int(tmp[1])

max_id = 200000000
S1 = bitarray.bitarray(max_id)
S2 = bitarray.bitarray(max_id)
for id, type in gen(path):
    if type != 3 and type != 4:
        S1[id] = True
    else:
        S2[id] = True

print S1.count(), S2.count()

Bien que cela donne la réponse, je pense que cela fonctionne un peu lentement. Que dois-je faire pour le rendre plus rapide?

MODIFIER: Il y a des enregistrements dupliqués dans le fichier. Et je n'ai besoin que de faire la distinction entre S1 (type 1 et type 2) et S2 (type 3 et type 4). Par exemple, 1440927 1 et 1440927 2 ne sont comptés qu'une seule fois, mais pas deux, car ils appartiennent à S1. Je dois donc stocker les identifiants.

Answer 1

S'il y a suffisamment de mémoire, vous pouvez utiliser dict au lieu de bitarray.bitarray.Cela pourrait être plus rapide:

S1, S2 = {}, {} # dicts are slightly faster than `set()`
with open(path) as f:
     for i, line in enumerate(f, 1):
         id, sep, type = line.partition(" ")
         if type == "1" or type == "2":
            S1[id] = True
         elif type == "3" or type == "4":
            S2[id] = True
         else:
            print "WARNING: unknown type: %r in line %d: %r" % (type, i, line)
print len(S1), len(S2)

Ou vous pouvez essayer de trier les lignes en premier:

def gettype(line):
    return line[-1]

S1, S2 = 0, 0
with open(path) as f:
     lines = f.read().splitlines()

lines.sort(key=gettype)
for type, group in itertools.groupby(lines, gettype):
    ids = (line.partition(" ")[0] for line in group)
    if type == "1" or type == "2":
       S1 += len(set(ids))
    elif type == "3" or type == "4":
       S2 += len(set(ids))
    else:
       assert 0, (type, list(ids))

print S1, S2

La complexité asymptotique de la deuxième approche est pire.

Vous pouvez utiliser line_profiler pour savoir où se trouve votre goulot d'étranglement.

Answer 2

Vous utilisez un itérateur sur le fichier, cela signifie que vous ne tamponnez que quelques lignes à la fois.Chaque fois que le tampon est vide, le disque doit chercher et votre programme doit attendre.

200 Mo s'intègrent facilement dans votre mémoire, donc obtenir toutes les lignes accélérera les choses:

def gen(path):
    # load all the lines, 
    lines = open(path).readlines() 
    split = (line.split() for line in lines)
    return ((int(x), int(y)) for x,y in split)

Answer 3

Êtes-vous lié à Python?

egrep -e "[12]$" filename.txt | cut -d " " -f 1 | sort -u | wc -l

egrep -e "[34]$" filename.txt | cut -d " " -f 1 | sort -u | wc -l

Ces deux commandes vous comptent le nombre d'occurrences de ("1" ou "2") et ("3" ou "4") à la fin de chaque ligne de votre filename.txt tout en ignorant les premiers champs en double.

/ p>

Probablement plus rapide que Python…