Каков самый быстрый способ фильтрации таблицы целых чисел в Python?

Question

У меня есть набор данных, состоящий из 7 столбцов и ~ 900 тыс. Строк. Все столбцы не уникальны, и все значения являются целыми числами.

Два важное условие для фильтрации:

• Я строго хочу видеть, какие значения находятся в одном столбце, когда я применяю условие на отдыхе.
• Для вывода меня интересуют только отдельные значения.

В качестве примера здесь является запрос SQL используется для сопоставительного анализа производительности:

SELECT DISTINCT 
col_2 
FROM dataset 
WHERE 
c_1 in (1,9,5,6,8,18,14,7,15) AND 
c_3 in (1) AND 
c_4 in (61) AND 
c_5 in (3) AND 
c_6 in (0) AND 
c_7 in (0) 

Первый подход, который я попробовал, был SQL с индексами с использованием SQLite, которые не делали слишком плохо, но как фильтры вернуть много строк, производительность снизилась.

Я тогда попробовал простые списки ванильных списков в Python. Производительность была немного хуже, чем в случае SQL.

Есть ли лучшие способы сделать это? Я думал в направлении numpy, возможно, используя более эффективную структуру данных, чем списки и таблицы SQL?

Я очень заинтересован в скорости и производительности здесь, а также в меньшей эффективности.

Любые предложения приветствуются!

Answer 1

После того, как вы сказали около 20 значений для каждого столбца, кроме одного с 400. Если память и время загрузки не беспокоиться, я бы предложил создать наборы для каждого столбца.

Вот что-то, чтобы сгенерировать образец данных.

#!/usr/bin/python 
from random import sample, choice 
from cPickle import dump 

# Generate sample dataset 
value_ceiling = 1000 
dataset_size = 900000 
dataset_filename = 'dataset.pkl' 

# number of distinct values per column 
col_distrib = [400,20,20,20,20,20,20] 

col_values = [ sample(xrange(value_ceiling),x) for x in col_distrib ] 

dataset = [] 
for _ in xrange(dataset_size): 
    dataset.append(tuple([ choice(x) for x in col_values ])) 

dump(dataset,open(dataset_filename,'wb')) 

Вот что-то, чтобы загрузить набор данных и создавать наборы подстановок на значение в колонке, метод поиска и создания запросов выборки.

#/usr/bin/python 

from random import sample, choice 
from cPickle import load 

dataset_filename = 'dataset.pkl' 

class DataSearch(object): 
    def __init__(self,filename): 
    self.data = load(open(filename,'rb')) 
    self.col_sets = [ dict() for x in self.data[0] ] 
    self.process_data() 
    def process_data(self): 
    for row in self.data: 
     for i,v in enumerate(row): 
     self.col_sets[i].setdefault(v,set()).add(row) 
    def search(self,*args): 
    # args are integers, sequences of integers, or None in related column positions. 
    results = [] 
    for i,v in enumerate(args): 
     if v is None: 
     continue 
     elif isinstance(v,int): 
     results.append(self.col_sets[i].get(v,set())) 
     else: # sequence 
     r = [ self.col_sets[i].get(x,set()) for x in v ] 
     r = reduce(set.union,r[1:],r[0]) 
     results.append(r) 
    # 
    results.sort(key=len) 
    results = reduce(set.intersection,results[1:],results[0]) 
    return results 
    def sample_search(self,*args): 
    search = [] 
    for i,v in enumerate(args): 
     if v is None: 
     search.append(None) 
     else: 
     search.append(sample(self.col_sets[i].keys(),v)) 
    return search 

d = DataSearch(dataset_filename) 

И использовать его:

>>> d.search(*d.sample_search(1,1,1,5)) 
set([(117, 557, 273, 437, 639, 981, 587), (117, 557, 273, 170, 53, 640, 467), (117, 557, 273, 584, 459, 127, 649)]) 
>>> d.search(*d.sample_search(1,1,1,1)) 
set([]) 
>>> d.search(*d.sample_search(10,None,1,1,1,1)) 
set([(801, 334, 414, 283, 107, 990, 221)]) 
>>> d.search(*d.sample_search(10,None,1,1,1,1)) 
set([]) 
>>> d.search(*d.sample_search(10,None,1,1,1,1)) 
set([(193, 307, 547, 549, 901, 940, 343)]) 
>>> import timeit 
>>> timeit.Timer('d.search(*d.sample_search(10,None,1,1,1,1))','from __main__ import d').timeit(100) 
1.787431001663208 

1,8 секунды, чтобы сделать 100 запросов достаточно быстро?

Answer 2

Вот что я придумал:

513 $ cat filtarray.py 
#!/usr/bin/python2 
# 
import numpy 
import itertools 

a = numpy.fromiter(xrange(7*900000), int) 
a.shape = (900000,7) 
# stuff a known match 
a[33][0] = 18 
a[33][2] = 1 
a[33][3] = 61 
# filter it, and make list, but that is not strictly necessary. 
res = list(itertools.ifilter(lambda r: r[0] in (1,9,5,6,8,18,14,7,15) and r[2] == 1 and r[3] == 61, a)) 
print res 

запустить на Intel E8400:

512 $ time python filtarray.py 
[array([ 18, 232, 1, 61, 235, 236, 237])] 
python filtarray.py 5.36s user 0.05s system 99% cpu 5.418 total 

Это быстрее?

Answer 3

Вот несколько вариантов, это занимает около 1 секунды.

x = numpy.random.randint(0, 100, (7, 900000)) 

def filter(data, filters): 
    indices = [] 
    for i, filter in enumerate(filters): 
     indices.append(numpy.any([data[i] == x for x in filter], 0)) 

    indices = numpy.all(indices, 0) 
    return data[indices] 

# Usage: 
filter(x, [(1,9,5,6,8,18,14,7,15), (1,), (61,), (3,), (0,), (0,)]) 

%timeit filter(x, [(1,9,5,6,8,18,14,7,15), (1,), (61,), (3,), (0,), (0,)]) 
1 loops, best of 3: 903 ms per loop