6

给定一个字符串，我想创建一个包含字符串中所有 n 个字符子字符串的字典，其中字典键是子字符串，值是列表。列表的第一个元素是子字符串的出现次数，列表的第二个元素是这些出现的起始位置的列表。

例如，使用n=3时，字符串'abcdabcxdabc'会出现在这个字典中：

{'abc': [3, [0, 4, 9]], 
 'cda': [1, [2]], 
 'dab': [2, [3, 8]], 
 'bcd': [1, [1]], 
 'cxd': [1, [6]], 
 'bcx': [1, [5]], 
 'xda': [1, [7]]}

下面的代码有效且高效，因为它只遍历字符串一次，但我想知道是否有更优雅和/或更pythonic的方式来做到这一点，也许使用字典理解。我对 python 还是很陌生，仍然试图弄清楚何时使用理解等有意义（甚至可能）。 

text = 'abcdabcxdabc'
n = 3
d = {}
for i in range(len(text) - n + 1):
    sub = text[i:i + n]
    if sub in d:
        d[sub][0] += 1
        d[sub][1].append(i)
    else:
        d[sub] = [1, [i]]
print(d)

更新：感谢所有回复。他们通常证实了我的怀疑，即这太复杂而无法在单一的理解中有效地实现（但感谢火山表明如果效率不是问题，这是可能的）。感谢 RemcoGerlich 和 Ignacio Vazquez-Abrams 将我指向 defaultdict。我将不得不深入研究。我的计时结果表明，与 dict 相比，初始化 defaultdict 的开销要多一些，但运行时间可能会稍微快一些，至少对于这个例子来说是这样。（计时结果发布在下面的单独评论中。）现在我想知道是否有任何情况下 dict 比 defaultdict 更受欢迎。另外，感谢 Narcolei 向我指出 timeit 功能。

4

5 回答 5

4

问题在于，这v[0]取决于长度 or v[1]，这意味着要生成的操作v[1]必须执行两次，或者必须迭代字典才能填充v[0]以替换第一次包含的虚拟值。

另一个问题是 dict 推导期望整个键和值立即可用，这意味着您必须运行列表推导来获取字符的所有索引，这意味着整个操作变为 O(n 2 )。

我要做的唯一优化是替换创建，d这样您就不需要检查密钥包含。

d = collections.defaultdict(lambda: [0, []])
于 2013-12-04T12:41:54.133 回答
2

这很可怕，但是（我只添加了偏移量，您可能从偏移量列表中获得的出现次数）。是的，可以做到

In [83]: my_str = 'abcdabcxdabc'

In [84]: n=3

In [85]: {substr: [my_str.replace(substr, ' '*n, c).index(substr) 
                   for c in xrange(my_str.count(substr))]
   ....: for substr in set(my_str[idx:idx+n] for idx in xrange(len(my_str)-n))}
Out[85]: 
{'abc': [0, 4, 9],
 'bcd': [1],
 'bcx': [5],
 'cda': [2],
 'cxd': [6],
 'dab': [3, 8],
 'xda': [7]}
于 2013-12-04T12:56:45.017 回答
1

正如@Ignacio 所说，任何试图解决此问题的理解都将具有二次运行时性能，如@volcano 的回答所示。解决问题的最干净的方法是这样的：

def substrings(text, n):
    d = collections.defaultdict(list)
    for i in xrange(len(text)-n+1):
        d[text[i:i+n]].append(i)
    return d

请注意，您不需要存储子字符串的数量，因为您只需len(d['abc'])获取abc.

以下是这种方法与理解的一些时间安排：

>>> import collections
>>> 
>>> def substrings(text, n):
>>>     d = collections.defaultdict(list)
>>>     for i in xrange(len(text)-n+1):
>>>         d[text[i:i+n]].append(i)
>>>     return d
>>> 
>>> def substrings2(text, n):
>>>     return {substr: [my_str.replace(substr, ' '*n, c).index(substr) for c in xrange(my_str.count(substr))] for substr in set(my_str[idx:idx+n] for idx in xrange(len(my_str)-n))}
>>> 
>>> text = 'abcdabcxdabc'
>>> 
>>> %timeit substrings(text, 3)
100000 loops, best of 3: 9.51 µs per loop
>>> %timeit substrings2(text, 3)
10000 loops, best of 3: 26.3 µs per loop
>>> text = text * 100
>>> %timeit substrings(text, 3)
1000 loops, best of 3: 440 µs per loop
>>> %timeit substrings2(text, 3)
100 loops, best of 3: 8.68 ms per loop

请注意，当输入的大小增加 100 倍时，理解时间如何增加 1000 倍。

于 2013-12-04T13:21:29.290 回答
0

我使用 defaultdict 和部分火山的理解实现了几个变体，并运行了一些时间测试。

原始版本（test1）：

d1 = {}
for i in range(len(text) - n + 1):
    sub = text[i:i + n]
    if sub in d1:
        d1[sub][0] += 1
        d1[sub][1].append(i)
    else:
        d1[sub] = [1, [i]]

第一个变体（test2）：

d = defaultdict(lambda: [0, []])
for i in range(len(text) - n + 1):
    sub = text[i:i + n]
    d[sub][0] += 1
    d[sub][1].append(i)

第二种变体（test3）：

d = defaultdict(lambda: [0, []])
for i, sub in [(i, text[i:i + n]) for i in range (len(text) - n + 1)]:
    d[sub][0] += 1
    d[sub][1].append(i)

第三变体（test4）：

d = {sub: [text.replace(sub, ' '*n, c).index(sub) for c in range(text.count(sub))]
     for sub in set(text[i:i + n] for i in range(len(text) - n + 1))}

以下是计时结果（显示每个循环的执行时间）：

text = "abcdabcxdabc":
10000 loops, best of 3, function test1: 7.37486786334e-06
10000 loops, best of 3, function test2: 1.02725863892e-05
10000 loops, best of 3, function test3: 1.16522984082e-05
10000 loops, best of 3, function test4: 1.98546753287e-05

text = "abcdabcxdabc"*10:
10000 loops, best of 3, function test1: 7.16965834334e-05
10000 loops, best of 3, function test2: 6.8394193171e-05
10000 loops, best of 3, function test3: 7.63521044367e-05
10000 loops, best of 3, function test4: 0.00016625460554

text = "abcdabcxdabc"*100:
1000 loops, best of 3, function test1: 0.000708709217238
1000 loops, best of 3, function test2: 0.000623426932274
1000 loops, best of 3, function test3: 0.000695915822531
1000 loops, best of 3, function test4: 0.00419154787196

text = "abcdabcxdabc"*1000:
1000 loops, best of 3, function test1: 0.00700270379835
1000 loops, best of 3, function test2: 0.00615744327104
1000 loops, best of 3, function test3: 0.00712429980398
1000 loops, best of 3, function test4: 0.296075626815

原始和前两个变体似乎是 O(n)，而第三个变体更接近 O(n*n)。我想我会选择第二个变体，因为它是 O(n) 版本中最紧凑的。

于 2013-12-05T08:38:07.513 回答
0

为了记录，另一个单行：

>>> n, s = 3, 'abcdabcxdabc'
>>> L=[(s[i:i+n], i) for i in range(len(s)-n+1)]
>>> L
[('abc', 0), ('bcd', 1), ('cda', 2), ('dab', 3), ('abc', 4), ('bcx', 5), ('cxd', 6), ('xda', 7), ('dab', 8), ('abc', 9)]
>>> d={t:[i for u, i in L if u == t] for t, _ in L}
>>> d
{'abc': [0, 4, 9], 'bcd': [1], 'cda': [2], 'dab': [3, 8], 'bcx': [5], 'cxd': [6], 'xda': [7]}
>>> {k:(len(v), v) for k, v in d.items()}
{'abc': (3, [0, 4, 9]), 'bcd': (1, [1]), 'cda': (1, [2]), 'dab': (2, [3, 8]), 'bcx': (1, [5]), 'cxd': (1, [6]), 'xda': (1, [7])}

在一行中：

>>> {k:(len(v), v) for L in ([(s[i:i+n], i) for i in range(len(s)-n+1)],) for k, v in ((t, [i for u, i in L if u == t]) for t, _ in L)}
{'abc': (3, [0, 4, 9]), 'bcd': (1, [1]), 'cda': (1, [2]), 'dab': (2, [3, 8]), 'bcx': (1, [5]), 'cxd': (1, [6]), 'xda': (1, [7])}

我将如何在“现实世界”中做：

>>> def substrings(s, n):
...     d = {}
...     tis = ((s[i:i+n], i) for i in range(len(s)-n+1))
...     for t, i in tis:
...         d.setdefault(t, []).append(i)
...     return {k:(len(v), v) for k, v in d.items()}
... 
>>> substrings(s, n)
{'abc': (3, [0, 4, 9]), 'bcd': (1, [1]), 'cda': (1, [2]), 'dab': (2, [3, 8]), 'bcx': (1, [5]), 'cxd': (1, [6]), 'xda': (1, [7])}

“真实世界”版本与单行版本有一点不同：字典内置于 O(n) 与 O(n^2)

于 2019-04-01T19:15:32.440 回答