Liczenie bigramsów naprawdę szybko (z lub bez wieloprocesowości) - python

Question

Biorąc pod uwagę big.txt z norvig.com/big.txt, celem jest naprawdę szybkie policzenie bigramsów (Wyobraź sobie, że muszę to powtarzać 100 000 razy).

Według Fast/Optimize N-gram implementations in python, wydobywania bigrams tak byłby najbardziej optymalny:

_bigrams = zip(*[text[i:] for i in range(2)]) 

A jeśli używam Python3, generator nie będą oceniane, dopóki nie zmaterializować ją list(_bigrams) lub niektórych innych funkcji to zrobi to samo.

import io 
from collections import Counter 

import time 
with io.open('big.txt', 'r', encoding='utf8') as fin: 
    text = fin.read().lower().replace(u' ', u"\uE000") 

while True: 
    _bigrams = zip(*[text[i:] for i in range(2)]) 
    start = time.time() 
    top100 = Counter(_bigrams).most_common(100) 
    # Do some manipulation to text and repeat the counting. 
    text = manipulate(text, top100)  

Ale to trwa około 1+ sekund na iterację, a 100 000 powtórzeń będzie zbyt długich.

Próbowałem również Counterizerzy Counter-to-detectora, ale czas na wyodrębnienie, policzenie i uzyskanie top100 bigramów jest porównywalny z rodzimym pytonem.

Potem już eksperymentował z jakiegoś multiprocessing, wykorzystując niewielką modyfikację od Python multiprocessing and a shared counter i http://eli.thegreenplace.net/2012/01/04/shared-counter-with-pythons-multiprocessing:

from multiprocessing import Process, Manager, Lock 

import time 

class MultiProcCounter(object): 
    def __init__(self): 
     self.dictionary = Manager().dict() 
     self.lock = Lock() 

    def increment(self, item): 
     with self.lock: 
      self.dictionary[item] = self.dictionary.get(item, 0) + 1 

def func(counter, item): 
    counter.increment(item) 

def multiproc_count(inputs): 
    counter = MultiProcCounter() 
    procs = [Process(target=func, args=(counter,_in)) for _in in inputs] 
    for p in procs: p.start() 
    for p in procs: p.join() 
    return counter.dictionary 

inputs = [1,1,1,1,2,2,3,4,4,5,2,2,3,1,2] 

print (multiproc_count(inputs)) 

Ale używając MultiProcCounter w liczeniu dwuznaków trwa nawet dłużej niż 1+ sekund na iteracji. Nie mam pojęcia, dlaczego tak jest, przy użyciu przykładowej listy int przykład, multiproc_count działa idealnie.

Próbowałem:

import io 
from collections import Counter 

import time 
with io.open('big.txt', 'r', encoding='utf8') as fin: 
    text = fin.read().lower().replace(u' ', u"\uE000") 

while True: 
    _bigrams = zip(*[text[i:] for i in range(2)]) 
    start = time.time() 
    top100 = Counter(multiproc_count(_bigrams)).most_common(100) 

Czy istnieje jakiś sposób, aby policzyć bigrams bardzo szybko w Pythonie?

Answer 1

Moja propozycja:

Text= "The Project Gutenberg EBook of The Adventures of Sherlock Holmes" 
"by Sir Arthur Conan Doyle" 

# Counters 
Counts= [[0 for x in range(128)] for y in range(128)] 

# Perform the counting 
R= ord(Text[0]) 
for i in range(1, len(Text)): 
    L= R; R= ord(Text[i]) 
    Counts[L][R]+= 1 

# Output the results 
for i in range(ord('A'), ord('{')): 
    if i < ord('[') or i >= ord('a'): 
     for j in range(ord('A'), ord('{')): 
      if (j < ord('[') or j >= ord('a')) and Counts[i][j] > 0: 
       print chr(i) + chr(j), Counts[i][j] 


Ad 1 
Bo 1 
EB 1 
Gu 1 
Ho 1 
Pr 1 
Sh 1 
Th 2 
be 1 
ck 1 
ct 1 
dv 1 
ec 1 
en 2 
er 2 
es 2 
he 3 
je 1 
lm 1 
lo 1 
me 1 
nb 1 
nt 1 
oc 1 
of 2 
oj 1 
ok 1 
ol 1 
oo 1 
re 1 
rg 1 
rl 1 
ro 1 
te 1 
tu 1 
ur 1 
ut 1 
ve 1 

Ta wersja jest wielkość liter; prawdopodobnie lepiej najpierw pisać małymi literami cały tekst.

Answer 2

import os, thread 

text = 'I really like cheese' #just load whatever you want here, this is just an example 

CORE_NUMBER = os.cpu_count() # may not be available, just replace with how many cores you have if it crashes 

ready = [] 
bigrams = [] 

def extract_bigrams(cores): 
    global ready, bigrams 
    bigrams = [] 
    ready = [] 
    for a in xrange(cores): #xrange is best for performance 
     bigrams.append(0) 
     ready.append(0) 
    cpnt = 0#current point 
    iterator = int(len(text)/cores) 
    for a in xrange(cores-1): 
     thread.start_new(extract_bigrams2, (cpnt, cpnt+iterator+1, a)) #overlap is intentional 
     cpnt += iterator 
    thread.start_new(extract_bigrams2, (cpnt, len(text), a+1)) 
    while 0 in ready: 
     pass 

def extract_bigrams2(startpoint, endpoint, threadnum): 
    global ready, bigrams 
    ready[threadnum] = 0 
    bigrams[threadnum] = zip(*[text[startpoint+i:endpoint] for i in xrange(2)]) 
    ready[threadnum] = 1 

extract_bigrams(CORE_NUMBER) 
thebigrams = [] 
for a in bigrams: 
    thebigrams+=a 

print thebigrams 

Istnieją pewne problemy z tym programem, jak nie odfiltrowanie spacje lub znaki interpunkcyjne, ale zrobiłem ten program, aby pokazać, co powinno być dla fotografowania. Możesz łatwo edytować, aby dostosować się do twoich potrzeb.

Ten program automatycznie wykrywa liczbę rdzeni komputera i tworzy taką liczbę wątków, starając się równomiernie rozmieścić obszary, w których szuka bigrams. Byłem w stanie przetestować ten kod w przeglądarce internetowej na komputerze należącym do szkoły, więc nie mogę być pewny, że to działa całkowicie. Jeśli pojawią się jakieś problemy lub pytania, zostaw je w komentarzach.