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

Question

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

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

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

В качестве примера приведем 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

Вот версия numpy, она занимает около 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

Answer 3

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

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

Это быстрее?