Estoy creando un diccionario de la siguiente manera:
y=[(1,2),(2,3),(1,2),(5,6)]
dict={}
for tup in y:
tup=tuple(sorted(tup))
if tup in dict.keys():
dict[tup]=dict[tup]+1
else:
dict[tup]=1
Sin embargo, mi y
real contiene aproximadamente 40 millones de tuplas, ¿hay alguna forma de usar el multiprocesamiento para acelerar este proceso?
Gracias
5 respuestas
Si desea obtener los recuentos ignorando el orden, use un frozenset
con Counter:
from collections import Counter
print(Counter(map(frozenset, y)))
Usando el tuples
de otra respuesta:
In [9]: len(tuples)
Out[9]: 500000
In [10]: timeit Counter(map(frozenset, tuples))
1 loops, best of 3: 582 ms per loop
Usar un conjunto congelado significará que (1, 2)
y (2,1)
se considerarán lo mismo:
In [12]: y = [(1, 2), (2, 3), (1, 2), (5, 6),(2, 1),(6,5)]
In [13]: from collections import Counter
In [14]:
In [14]: print(Counter(map(frozenset, y)))
Counter({frozenset({1, 2}): 3, frozenset({5, 6}): 2, frozenset({2, 3}): 1})
Si aplica la misma lógica utilizando multiprocesamiento, obviamente será considerablemente más rápido, incluso sin que supere lo que se ha proporcionado mediante multiprocesamiento.
Debido a que desea aumentar los recuentos (no solo crear nuevos pares clave / valor), el diccionario no es seguro para usar con hilos a menos que adquiera un semáforo alrededor de cada actualización y lo libere después, por lo que no creo que obtenga una velocidad general ganancia, de hecho puede ser más lento.
Si va a enhebrar esto, probablemente sea mejor que cada hilo actualice su propio diccionario y luego combine los resultados a medida que finaliza cada hilo, de esa manera no hay duda sobre la seguridad del hilo. Sin embargo, debido a que es probable que esté vinculado a la CPU, debe usar multiprocesamiento en lugar de subprocesos; el multiprocesamiento puede hacer uso de todos los núcleos de su CPU.
Además, si usa colecciones.Counter, hará el recuento por usted, y admite la fusión, y tiene un método útil most_common (n) para devolver las claves con n recuentos más altos.
Puede seguir un enfoque MapReduce.
from collections import Counter
from multiprocessing import Pool
NUM_PROCESSES = 8
y = [(1,2),(2,3),(1,2),(5,6)] * 10
## http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks-in-python
def chunks(l, n):
"""Yield successive n-sized chunks from l."""
for i in xrange(0, len(l), n):
yield l[i:i+n]
## map
partial_counters = Pool(NUM_PROCESSES).map(Counter, chunks(y, NUM_PROCESSES))
## reduce
reduced_counter = reduce(Counter.__add__, partial_counters)
## Result is:
## Counter({(1, 2): 20, (5, 6): 10, (2, 3): 10})
La idea es:
- divide tu lista de entrada en trozos
- alimentar cada fragmento a un proceso separado que calculará de forma independiente los recuentos
- fusionó todos los recuentos parciales mediante una operación de reducción.
EDITAR: use chunks(map(frozenset, y), NUM_PROCESSES)
para tener en cuenta los pares desordenados.
En primer lugar, en lugar de verificar la membresía de tup
en dict.keys
en cada iteración, lo cual es una muy mala idea, puede usar collections.defaultdict()
para este objetivo, que es más pitónico:
from collections import defaultdict
test_dict = defaultdict(lambda:1)
for tup in y:
tup=tuple(sorted(tup))
test_dict[tup]=+1
En segundo lugar, si desea utilizar la simultaneidad, es posible que desee usar multiprocesamiento o multiprocesamiento, pero sobre multiprocesamiento, debido a GIL varios subprocesos no pueden ejecutar un bytecode a la vez, y no puede atravesar sus tuplas de ambos lados como un algoritmo BDS.
Pero para el procesamiento múltiple tendrá otro problema: acceder a una memoria compartida desde cada núcleo y trabajar en él de inmediato para obtener más información, lea esta respuesta https://stackoverflow.com/a/30132673/2867928.
Entonces, ¿cuál sería el truco?
Una forma es dividir su lista en piezas pequeñas y usar subprocesos múltiples para aplicar su función en una parte específica.
Otra forma es usar coroutinas y subrutinas que, como se mencionó en esa respuesta, Greg Ewing tiene un gran demostración de cómo usar el rendimiento de usar corutinas para construir cosas como planificadores o simulaciones de muchos actores.
Editar: Respuesta editada para ser segura para subprocesos
El multiprocessing
lo hace fácil.
Simplemente refactorice su código para que el procesamiento se realice en una función:
def process_tuple(tuples):
count_dict = {}
for tuple_ in tuples:
tuple_=tuple(sorted(tuple_))
if tuple_ in count_dict:
count_dict[tuple_] += 1
else:
count_dict[tuple_] = 1
return count_dict
Divida la lista de tuplas en un grupo pequeño y luego use {{X0 }} para procesar todos tus grupos.
## http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks-in-python
def chunks(l, n):
"""Yield successive n-sized chunks from l."""
for i in xrange(0, len(l), n):
yield l[i:i+n]
# cut tuples list into 5 chunks
tuples_groups = chunks(tuples, 5)
pool = Pool(5)
count_dict = {}
# processes chunks in parallel
results = pool.map(process_tuple, tuples_groups)
# collect results
for result in results:
count_dict.update(result)
multiprocessing.Pool
manejará la distribución entre hilos.
Ejemplo completo + puntos de referencia:
import time
import random
start_time = time.time()
tuples = []
x,y = (100000, 10)
for i in range(x):
tuple_ = []
for j in range(y):
tuple_.append(random.randint(0, 9))
tuples.append(tuple(tuple_))
print("--- %s data generated in %s seconds ---" % (x*y, time.time() - start_time))
def process_tuple(tuples):
count_dict = {}
for tuple_ in tuples:
tuple_=tuple(sorted(tuple_))
if tuple_ in count_dict:
count_dict[tuple_] += 1
else:
count_dict[tuple_] = 1
return count_dict
from multiprocessing import Pool
start_time = time.time()
## http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks-in-python
def chunks(l, n):
"""Yield successive n-sized chunks from l."""
for i in xrange(0, len(l), n):
yield l[i:i+n]
# cut tuples list into 5 chunks
tuples_groups = chunks(tuples, 5)
pool = Pool(5)
count_dict = {}
# processes chunks in parallel
results = pool.map(process_tuple, tuples_groups)
# collect results
for result in results:
count_dict.update(result)
print("--- Multithread processed in %s seconds ---" % (time.time() - start_time))
start_time = time.time()
count_dict = {}
for tuple_ in tuples:
tuple_=tuple(sorted(tuple_))
if tuple_ in count_dict:
count_dict[tuple_] += 1
else:
count_dict[tuple_] = 1
print("--- Single thread processed in %s seconds ---" % (time.time() - start_time))
--- 10000000 datos generados en 32.7803010941 segundos ---
--- Hilo múltiple procesado en 1.79116892815 segundos ---
--- Hilo único procesado en 2.65010404587 segundos ---
Preguntas relacionadas
Preguntas vinculadas
Nuevas preguntas
python
Python es un lenguaje de programación multipropósito, de tipificación dinámica y de múltiples paradigmas. Está diseñado para ser rápido de aprender, comprender y usar, y hacer cumplir una sintaxis limpia y uniforme. Tenga en cuenta que Python 2 está oficialmente fuera de soporte a partir del 01-01-2020. Aún así, para preguntas de Python específicas de la versión, agregue la etiqueta [python-2.7] o [python-3.x]. Cuando utilice una variante de Python (por ejemplo, Jython, PyPy) o una biblioteca (por ejemplo, Pandas y NumPy), inclúyala en las etiquetas.