更新字典和检查键的最快方法

Question

我正在建立一个字典，里面存的是一个非常长的字符串（大约1G），字典的键是固定长度的k-mer，而值则是所有出现的位置。当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) 

最耗时的步骤是查找一个键是否出现过（在我们遍历字符串时），也就是判断这个键是新键还是已经存在的键。我想知道，最快的查找方法是什么？

我现在正在测试一种两次遍历的策略，避免了这个步骤（对于大序列来说，这种方法要快得多）。我首先通过简单地覆盖重复的键来建立一个键的列表。然后我就不需要检查键是否存在了——我用这些键来初始化我的字典，然后在第二次遍历时，只需在遇到它们时直接添加。

不过我还是想知道，总结一下，在Python中查找字典键的最快方法是什么，因为这是一个常见的模式：

如果键存在，就添加新的条目；否则，创建键并添加第一个元素。

这个模式的最快实现方式是什么？

Answer 1

字典有一个叫做 detdefault 的方法，它可以实现你想要的功能，不过我不太确定它会快多少。

所以你可以尝试新的写法：

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

Answer 2

一般来说，使用的方法会根据你的数据而有所不同。我做了一些简单的测试，使用不同类型的数据来说明时间是如何变化的。

使用的字符串有：

1. 问题中的字符串。
2. 一个更大的伪随机字符串（据说在哈希中有更多不同的mers/keys）。
3. 一个在哈希中只有很少不同的mers/keys的字符串。

这里有一些快速的代码来测试各种方法（我给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

我会使用 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 的性能。