Оптимизация операций объединения больших чисел для очень больших наборов данных - PullRequest
Новая
       38

Оптимизация операций объединения больших чисел для очень больших наборов данных

0 голосов
/ 27 октября 2019

У меня есть словарь с очень большим количеством ключей ( ~ 300k и растущий) и в качестве значений он имеет наборы, которые также имеют большое количество элементов ( ~ 20k ). 

dictionary = {
    1: {1, 2, 3},
    2: {3, 4},
    3: {5, 6},
    4: {1, 5, 12, 13},
    5: set()
}

Я хочу создать два массива: 

keys  = [1 1 1 2 2 3 3 4 4 4  4]
items = [1 2 3 3 4 5 6 1 5 12 13]

, которые в основном представляют собой сопоставление каждого элемента в каждом наборе вместе с соответствующим ключом.

Я пытался использовать numpy для этой работы, но это все еще занимает очень много времени, и я хочу знать, можно ли его оптимизировать.

numpy код: 

keys = np.concatenate(list(map(lambda x: np.repeat(x[0], len(x[1])), dictionary.items())))
items = np.concatenate(list(map(lambda x: list(x), dictionary.values())))

keys = np.array(keys, dtype=np.uint32)
items = np.array(items, dtype=np.uint16)

return keys, items

Вторая часть - попытка уменьшить объем памяти этих переменных для учета их соответствующих типов данных. Но я знаю, что они будут по умолчанию использовать 64-битные переменные в первых двух операциях (до применения изменения dtype), поэтому память будет выделена, и у меня может закончиться ОЗУ.

Ответы [ 3 ]

0 голосов
/ 27 октября 2019

Для этого небольшого примера версия с чистым списком значительно быстрее, чем просто с нуля: 

In [14]: timeit list(itertools.chain.from_iterable([[item[0]]*len(item[1]) for item in dictionary.items()]))                                           
2.71 µs ± 18.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [15]: timeit np.concatenate(list(map(lambda x: np.repeat(x[0], len(x[1])), dictionary.items())))                                                    
52.2 µs ± 284 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

и 

In [24]: list(itertools.chain.from_iterable(dictionary.values()))               
Out[24]: [1, 2, 3, 3, 4, 5, 6, 1, 13, 12, 5]
In [25]: timeit list(itertools.chain.from_iterable(dictionary.values()))        
876 ns ± 10.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [26]: timeit np.concatenate(list(map(lambda x: list(x), dictionary.values())))                                                                      
13.8 µs ± 32.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

И версия Пола Панцера: 

In [41]: timeit np.fromiter(itertools.chain.from_iterable(dictionary.values()),'int32')                                                                
3.69 µs ± 9.07 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
0 голосов
/ 27 октября 2019

не уверен, будет ли он работать намного лучше, но прямой способ сделать это так: 

import numpy as np

keys = np.array(list(dictionary.keys()), dtype=np.uint32).repeat([len(s) for s in dictionary.values()])

values = np.concatenate([np.array(list(s), np.uint16) for s in dictionary.values()])

display(keys)
display(values)
0 голосов
/ 27 октября 2019

Вероятно, лучше использовать np.fromiter здесь. Это, конечно, легче в памяти, поскольку позволяет избежать создания всех этих временных.

Время:

enter image description here

import numpy as np
import itertools as it
from simple_benchmark import BenchmarkBuilder

B = BenchmarkBuilder()

@B.add_function()
def pp(a):
    szs = np.fromiter(map(len,a.values()),int,len(a))
    ks = np.fromiter(a.keys(),np.uint32,len(a)).repeat(szs)
    vls = np.fromiter(it.chain.from_iterable(a.values()),np.uint16,ks.size)
    return ks,vls

@B.add_function()
def OP(a):
    keys = np.concatenate(list(map(lambda x: np.repeat(x[0], len(x[1])), a.items())))
    items = np.concatenate(list(map(list, a.values())))
    return keys, items

@B.add_function()
def DevKhadka(a):
    keys = np.array(list(a.keys()), dtype=np.uint32).repeat([len(s) for s in a.values()])
    values = np.concatenate([np.array(list(s), np.uint16) for s in a.values()])
    return keys,values

@B.add_function()
def hpaulj(a):
    ks = list(it.chain.from_iterable([[item[0]]*len(item[1]) for item in a.items()]))                                           
    vls = list(it.chain.from_iterable(a.values()))
    return ks,vls


@B.add_arguments('total no items')
def argument_provider():
    for exp in range(1,12):
        sz = 2**exp
        a = {j:set(np.random.randint(1,2**16,np.random.randint(1,sz)).tolist())
     for j in range(1,10*sz)}
        yield sum(map(len,a.values())),a

r = B.run()
r.plot()

import pylab
pylab.savefig('dct2np.png')
...