cython: уменьшает размер класса, уменьшает использование памяти, улучшает скорость

Question

У меня есть относительно простая проблема: учитывая положение в геноме, верните имя гена в этот момент.

Путь, я решить эту проблему прямо сейчас, используя следующий класс в Cython ::

class BedFile(): 
    """ A Lookup Object """ 
    def __init__(self, bedfile): 
     self.dict = {} 
     cdef int start, end 
     with open(bedfile) as infile: 
      for line in infile: 
       f = line.rstrip().split('\t') 
       if len(f) < 4: 
        continue 
       chr = f[0] 
       start = int(f[1]) 
       end = int(f[2]) 
       gene = f[3] 
       if chr not in self.dict: 
        self.dict[chr] = {} 
       self.dict[chr][gene] = (start, end) 

    def lookup(self, chromosome, location): 
     """ Lookup your gene. Returns the gene name """ 
     cdef int l 
     l = int(location) 
     answer = '' 
     for k, v in self.dict[chromosome].items(): 
      if v[0] < l < v[1]: 
       answer = k 
       break 
     if answer: 
      return answer 
     else: 
      return None 

Полный проект находится здесь: https://github.com/MikeDacre/python_bed_lookup, хотя весь соответствующий класс выше.

Проблема с кодом как есть в том, что полученный класс/словарь занимает очень большой объем памяти для генома человека, с 110 миллионами генов (это текстовый файл длиной 110 миллионов строк). Я убил функцию init в процессе построения словаря примерно через две минуты, когда он достиг 16 ГБ памяти. Все, что использует большую память, в основном бесполезно.

Я уверен, что мне нужно более эффективный способ сделать это, но я не программист на C, и я очень новичок в cython. Я предполагаю, что я мог бы построить чистую C-структуру какого-либо типа, чтобы сохранить имя гена и начальные и конечные значения. Затем я мог преобразовать lookup() в функцию, которая вызывает другую функцию cdef, называемую _lookup(), и использовать эту функцию cdef для выполнения этого фактического запроса.

В идеальном мире вся структура может жить в памяти и занимать менее 2 ГБ памяти для ~ 2 000 000 записей (каждая запись с двумя целыми и строками).

Edit: я понял, как сделать это эффективно с SQLite для больших файлов, чтобы увидеть полный код с SQLite смотрите здесь: https://github.com/MikeDacre/python_bed_lookup

Однако, я все еще думаю, что выше класс может быть оптимизирован с Cython чтобы сделать словарь меньше в памяти и быстрее искать, любые предложения оценены.

Спасибо!

Answer 1

В моем ограниченном опыте с cython и numpy, наиболее выгодно использовать cython для «внутренних» вычислений, которые не требуют использования кода Python/numpy. Это итерации, которые можно использовать для компактного и быстрого кода C.

Вот переписывание кода, разделив из двух классов можно сформулировать в качестве Cython/C структур:

# cython candidate, like DavidW's StartEnd 
class Gene(object): 
    def __init__(self, values): 
     self.chr = values[0] 
     self.start = int(values[1]) 
     self.end = int(values[2]) 
     self.gene = values[3] 
    def find(self, i): 
     return self.start<=i<self.end 
    def __repr__(self): 
     return "%s(%s, %d:%d)"%(self.chr,self.gene,self.start,self.end) 

# cython candidate 
class Chrom(list): 
    def add(self, aGene): 
     self.append(aGene) 
    def find(self, loc): 
     # find - analogous to string find? 
     i = int(loc) 
     for gene in self: 
      if gene.find(i): 
       return gene # gene.gene 
     return None 
    def __repr__(self): 
     astr = [] 
     for gene in self: 
      astr += [repr(gene)] 
     return '; '.join(astr) 

Они будут импортированы и использованы функции Python высокого уровня (или класса), которые не должны быть в Cython .pdx файле:

from collections import defaultdict 
def load(anIterable): 
    data = defaultdict(Chrom) 
    for line in anIterable: 
     f = line.rstrip().split(',') 
     if len(f)<4: 
      continue 
     aGene = Gene(f) 
     data[aGene.chr].add(aGene) 
    return data 

использования с файлом или текстового моделирования:

# befile = 'filename' 
# with open(bedfile) as infile: 
# data = load(infile) 

txt = """\ 
A, 1,4,a 
A, 4,8,b 
B, 3,5,a 
B, 5,10,c 
""" 
data = load(txt.splitlines()) 
print data 
# defaultdict(<class '__main__.Chrom'>, { 
# 'A': A(a, 1:4); A(b, 4:8), 
# 'B': B(a, 3:5); B(c, 5:10)}) 

print 3, data['A'].find(3) # a gene 
print 9, data['B'].find(9) # c gene 
print 11,data['B'].find(11) # none 

Я мог бы определить функцию find, которая отдает предпочтение методу, если он доступен, в противном случае использует его собственный. Это аналогично Numpy функций, делегированных к методам:

def find(chrdata, loc): 
    # find - analogous to string find? 
    fn = getattr(chrdata, 'find',None) 
    if fn is None: 
     #raise AttributeError(chrdata,'does not have find method') 
     def fn(loc): 
      i = int(loc) 
      for gene in chrdata: 
       if gene.find(i): 
        return gene # gene.gene 
      return None 
    return fn(loc) 

print 3, find(data['A'],3) 

Протестируйте find с обычной структурой данных списка:

def loadlist(anIterable): 
    # collect data in ordinary list 
    data = defaultdict(list) 
    for line in anIterable: 
     f = line.rstrip().split(',') 
     if len(f)<4: 
      continue 
     aGene = Gene(f) 
     data[aGene.chr].append(aGene) 
    return data 

data = loadlist(txt.splitlines()) 
print 3, find(data['A'],3) 

Answer 2

Чтобы расширить мое предложение в комментариях немного, вместо того, чтобы хранить (start,end) как кортеж, хранить его в качестве простого Cython определенного класса:

cdef class StartEnd: 
    cdef public int start, end 

    def __init__(self, start, end): 
     self.start = start 
     self.end = end 

(вы также можете играть с изменением типа целое для большей экономии сбережений). Я не рекомендую избавляться от словарей Python, потому что они просты в использовании и, как я полагаю, оптимизированы для того, чтобы быть достаточно эффективными для случая (общего в Python) строковых ключей.

Мы можем оценить экономию размеров с помощью sys.getsizeof. (Имейте в виду, что это будет хорошо работать для встроенных классов и классов Cython, но не так хорошо для классов Python, поэтому не слишком доверяйте ему. Также имейте в виду, что результаты зависят от платформы, поэтому ваши могут немного отличаться).

>>> sys.getsizeof((1,2)) # tuple 
64 
>>> sys.getsizeof(1) # Python int 
28 

(Поэтому каждый кортеж содержит 64 + 28 + 28 = 120 байт)

>>> sys.getsizeof(StartEnd(1,2)) # my custom class 
24 

(24 имеет смысл: это PyObject_Head (16 байт: 64-битное целое и указатель) +-32 -битные целые числа).

Таким образом, в 5 раз меньше, что является хорошим началом, я думаю.