Самый быстрый способ обновить словарь и проверить ключи

Question

Я строю словарь из очень длинной строки (~ 1G), где ключ - это k-мер фиксированной длины, а значение - все позиции вхождения.Когда k большое (> 9), нет смысла предварительно собирать словарь k-mer, так как не все значения появятся, и это приведет к раздуванию таблицы.

В настоящее время я делаю задачу следующим образом:

def hash_string(st, mersize):

    stsize = len(st)
    hash = {}
    r = stsize-mersize+1

    for i in range(0, r):
        mer = st[i:i+mersize]
        if mer in hash:
            hash[mer].append(i)
        else:
            hash[mer] = [i]

    return hash

# test for function hash_st above        
mer3 = hash_string("ABCDABBBBBAAACCCCABCDDDD", 3) 

Самый трудоемкий шаг (я сделал cProfile) - поиск, если ключ, с которым мы столкнулись (когда мы движемся вдоль строки), это новый ключ или он уже существует.Какой самый быстрый способ сделать это?

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

Но мне все равно было бы интересно узнатьПодводя итог, самый быстрый способ поиска ключа dict в Python, так как это общий шаблон:

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

Какая самая быстрая реализация этого шаблона?

Answer 1

Я бы использовал collections.defaultdict:

import collections
...
hash = collections.defaultdict(list)
r = stsize-mersize+1

for i in range(0, r):
    mer = st[i:i+mersize]
    hash[mer].append(i)

хотя никогда не профилировал его против if ... else.

Answer 2

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

Используемые строки:

1. Строка в вопросе.
2. Увеличенная псевдослучайная строка (предположительно, с более четкими символами / ключами в хэше).
3. Строка, в хэше которой содержится очень мало разных mers / ключей.

Вот краткий код для проверки различных методов (я проголосовал за ответ defaultdict, так как он кажется самым быстрым).

import random
from timeit import Timer
from collections import defaultdict

def test_check_first(st, mersize):
    """ Look for the existance of the mer in the dict.
    """
    mer_hash = {}
    r = len(st)-mersize+1

    for i in range(0, r):
        mer = st[i:i+mersize]
        if mer in mer_hash:
            mer_hash[mer].append(i)
        else:
            mer_hash[mer] = [i]

    return mer_hash

def test_throw_exception(st, mersize):
    """ Catch the KeyError thown if a mer doesn't exist in the dict.
    """
    mer_hash = {}
    r = len(st)-mersize+1

    for i in range(0, r):
        mer = st[i:i+mersize]
        try:
            mer_hash[mer].append(i)
        except KeyError:
            mer_hash[mer] = [i]

    return mer_hash

def test_defaultdict(st, mersize):
    """ Use a defaultdict.
    """
    mer_hash = defaultdict(list)
    r = len(st)-mersize+1

    for i in range(0, r):
        mer = st[i:i+mersize]
        mer_hash[mer].append(i)

    return mer_hash

def test_dict_setdefault(st, mersize):
    """ Use dict's setdefault method
    """
    mer_hash = {}
    r = len(st)-mersize+1

    for i in range(0, r):
        mer = st[i:i+mersize]
        mer_hash.setdefault(mer, []).append(i)

    return mer_hash

def gen_pseudorandom_string(size):
    """ Generate a larger, more "random" string of data.
    """
    # only use four letters
    letters = ('A', 'B', 'C', 'D')
    return ''.join(random.choice(letters) for i in range(size))

if __name__ == '__main__':
    # test functions
    test_strings = ('ABCDABBBBBAAACCCCABCDDDD', gen_pseudorandom_string(1000), 'A'*100 + 'B'*100 + 'C'*100 + 'D'*100)
    mer_size = 3
    passes = 10000

    for string in test_strings:
        display_string = string if len(string) <= 30 else string[:30] + '...'
        print 'Testing with string: "' + display_string + '" and mer size: ' + str(mer_size) + ' and number of passes: ' + str(passes)

        t1 = Timer("test_check_first(string, mer_size)", "from __main__ import test_check_first, string, mer_size")
        print '\tResults for test_check_first: ',
        print "%.2f usec/pass" % (1000000 * t1.timeit(number=passes)/passes)

        t2 = Timer("test_throw_exception(string, mer_size)", "from __main__ import test_throw_exception, string, mer_size")
        print '\tResults for test_throw_exception: ',
        print "%.2f usec/pass" % (1000000 * t2.timeit(number=passes)/passes)

        t3 = Timer("test_defaultdict(string, mer_size)", "from __main__ import test_defaultdict, string, mer_size")    
        print '\tResults for test_defaultdict: ',
        print "%.2f usec/pass" % (1000000 * t3.timeit(number=passes)/passes)

        t4 = Timer("test_dict_setdefault(string, mer_size)", "from __main__ import test_dict_setdefault, string, mer_size")    
        print '\tResults for test_dict_setdefault: ',
        print "%.2f usec/pass" % (1000000 * t4.timeit(number=passes)/passes)

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

Testing with string: "ABCDABBBBBAAACCCCABCDDDD" and mer size: 3 and number of passes: 10000
    Results for test_check_first:  8.70 usec/pass
    Results for test_throw_exception:  22.78 usec/pass
    Results for test_defaultdict:  10.61 usec/pass
    Results for test_dict_setdefault:  8.88 usec/pass
Testing with string: "BACDDDADAAABADBDADDBBBCAAABBBC..." and mer size: 3 and number of passes: 10000
    Results for test_check_first:  305.19 usec/pass
    Results for test_throw_exception:  320.62 usec/pass
    Results for test_defaultdict:  254.56 usec/pass
    Results for test_dict_setdefault:  342.55 usec/pass
Testing with string: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA..." and mer size: 3 and number of passes: 10000
    Results for test_check_first:  114.23 usec/pass
    Results for test_throw_exception:  107.96 usec/pass
    Results for test_defaultdict:  94.11 usec/pass
    Results for test_dict_setdefault:  125.72 usec/pass

Answer 3

В словарях есть метод detdefault, который делает то, что вы хотите, но не уверен, насколько быстрее он будет.

Таким образом, ваш новый шаблон может быть:

hash.setdefault(mer, []).append(i)

Answer 4

Вы также можете попробовать метод на основе исключений:

# Python2-3 compatibility
try: xrange
except NameError: xrange= range

for i in xrange(r):
    mer = st[i:i+mersize]
    try: hash[mer].append(i)
    except KeyError: # not there
        hash[mer]= [i]

Обратите внимание, что это будет медленнее, чем ваш метод, если в большинстве случаев mer не найден, но быстрее, если в большинстве случаевнашлось.Вы знаете свои данные и можете сделать свой выбор.
Кроме того, может быть, лучше не маскировать встроенные функции, такие как hash.