python - 恒定时间内的字符串比较

Question

我正在考虑比较两个字符串的更快方法。检查 Python 集合（哈希表）中是否存在值具有恒定的时间。这是否意味着在集合中查找字符串也具有恒定的时间？

print('tya' == 'tya') #O(n)
mySet = set()
mySet.add('tya')
if 'tya' in mySet: #O(1) <-- ???
    print('True')

在更一般的情况下，这是否意味着我可以在线性时间内找到字符串中的子字符串？？？

def NaiveFind(largeString, subString):
    mySet = set()
    mySet.add(subString)
    index = -1
    start = 0
    end = len(subString)

    while(end < len(largeString)): #O(n-m)
        windowFromLarge = largeString[start:end]
        if(windowFromLarge in mySet): #O(1) <------- LINEAR ???
        #if(windowFromLarge == subString): #O(m)
            return start
        start += 1
        end += 1

    return index

标签： pythonpython-3.xstring-comparison

Answer 1

你说

检查 Python 集合（哈希表）中是否存在值具有恒定的时间。

但这是一种常见的过度简化，因为人们没有意识到他们正在这样做，或者因为每次说出实际行为需要更长的时间。

检查一个值是否存在于 Python 集中需要平均情况下的常量数量的散列操作和相等比较，假设散列冲突不会失控。它不会自动使散列操作和相等比较时间恒定。

您的NaiveFind算法不是线性时间，因为您忽略了哈希计算的成本（也因为字符串切片需要 CPython 中的副本）。Rabin-Karp 算法使用您的想法的改进版本，其中哈希是滚动哈希以避免此问题。Rabin-Karp 算法是平均情况线性时间，只要哈希冲突不会失控。还有像Knuth-Morris-Pratt这样的算法可以保证线性时间，而像Boyer-Moore这样的算法在通常情况下可以做得比线性时间更好。