字符串上的单个交换
字符串上的单个交换
提问于 2016-12-02 17:49:22
我需要找到一种更快的方法，以下面的方式找到8-11字符串中的交换：
给定一个字符串'STDILGNLYE'，查找所有用于字母的单个字母交换：
list_AA = ['A', 'R', 'N', 'D', 'C', 'Q', 'E', 'G', 'H', 'I', 'L', 'K', 'M',
'F', 'P', 'S', 'T', 'W', 'Y', 'V']也就是说，对于字符串中的每个字母，将原始字符串中的每个字母替换为list_aa中的一个。产出如下：
ATDILGNLYE
RTDILGNLYE
NTDILGNLYE
...
SADILGNLYE
SRDILGNLYE
SNDILGNLYE
...
...
STDILGNLYV总共有200个新字符串(每个字符串中的每个位置有20个交换)。到目前为止我所拥有的是：
def _create_swaps(original_str):
list_peps = []
for i in range(len(original_str)):
for k in range(len(list_AA)):
list_peps.append(_insert_aa(original_str, i, list_aa[k]))
#remove original string
return [i for i in list_peps if i != original_str]
def _insert_aa(string, index, aa):
list_string_elements = list(string)
del list_string_elements[index]
hash_string.insert(index, aa)
return "".join(hash_string)由于这需要重复10**6次，这是一个较大的项目中最慢的一步。有没有一种方法可以更快地找到这样的掉期(通过消除"".join、插入、步骤/动态寻找交换)？
供参考：
ncalls tottime percall cumtime percall filename:lineno(function)
185275200 330.286 0.000 429.295 0.000 models.py:233(_insert_aa)
975240 147.322 0.000 616.979 0.001 models.py:225(_create_swaps)
185280201/185280197 59.137 0.000 59.138 0.000 {method 'join' of 'str' objects}
185275208 39.875 0.000 39.875 0.000 {method 'insert' of 'list' objects}
975240 21.027 0.000 21.027 0.000 models.py:231(<listcomp>)
186746064 18.516 0.000 18.516 0.000 {method 'append' of 'list' objects}回答 2
Stack Overflow用户
回答已采纳
发布于 2016-12-02 18:27:30
这是一个更干净的版本，你正在寻找的东西，即使你已经选择了一个答案(它不是最仿生的)。
您不应该使用range来获取可迭代的索引，如果您想要在其中使用pythonic，则应该使用枚举。
>>> def swaps(s, lst):
... for index, _ in enumerate(s):
... for letter in lst:
... temp = list(s)
... temp[index] = letter
... yield ''.join(temp)
...
>>> list_AA = ['A', 'R', 'N', 'D', 'C', 'Q', 'E', 'G', 'H', 'I', 'L', 'K', 'M', 'F', 'P', 'S', 'T', 'W', 'Y', 'V']
>>> s = 'STDILGNLYE'
>>>
>>> for _ in swaps(s, list_AA):
... print _
...
ATDILGNLYE
RTDILGNLYE
NTDILGNLYE
..........
GTDILGNLYE
HTDILGNLYE
ITDILGNLYE此外，python3中的一种简化方法是：
>>> def swaps(s, lst):
... for i, _ in enumerate(s):
... yield from ['%s%s%s' % (s[:i], x, s[i+1:]) for x in lst]
...
>>> swaps(s,list_AA)
<generator object swaps at 0x10c9205c8>
>>> a=_
>>> next(a)
'ATDILGNLYE'
>>> next(a)
'RTDILGNLYE'
>>> next(a)
'NTDILGNLYE'
>>> next(a)
'DTDILGNLYE'编辑:速度/可读性的折衷解决方案
def swap3(s, lst):
for i, _ in enumerate(s):
head, tail = s[:i], s[i+1:]
yield from ['%s%s%s'%(head,c,tail) for c in lst]以下是这三项指标的基准测试：
s='STDILGNLYE'
list_AA=['A', 'R', 'N', 'D', 'C', 'Q', 'E', 'G', 'H', 'I', 'L', 'K', 'M', 'F',
'P', 'S', 'T', 'W', 'Y', 'V']
# the correct sample size
list_new = list_AA * (10**6 // len(list_AA))
def swaps0(string, replacements):
for i in range(len(string)):
head = string[:i]
tail = string[i+1:]
for letter in replacements:
yield head + letter + tail
def swaps1(s, lst):
for i, _ in enumerate(s):
yield from ['%s%s%s' % (s[:i], x, s[i+1:]) for x in lst]
def swaps2(s, lst):
for index, _ in enumerate(s):
for letter in lst:
temp = list(s)
temp[index] = letter
yield ''.join(temp)
timeit [_ for _ in swaps0(s, list_new)]
timeit [_ for _ in swaps1(s, list_new)]
timeit [_ for _ in swaps2(s, list_new)]
In [9]: timeit [_ for _ in swaps0(s, list_new)]
1 loop, best of 3: 2.61 s per loop
In [10]: timeit [_ for _ in swaps1(s, list_new)]
1 loop, best of 3: 6.57 s per loop
In [11]: timeit [_ for _ in swaps2(s, list_new)]
1 loop, best of 3: 8.61 s per loop值得吗？我想说的是，这取决于您期望这个样本大小增长多大，以及您将运行代码的频率。
如果代码不会频繁地运行(例如，每小时数百次)，并且样本大小不会以指数方式增长(大约是1050或10100)，那么我会说是为了提高可读性。
如果这将是非常经常地计算随着样本数量的增加，考虑性能。
最后，我们有一个折衷的解决方案，将枚举和头/尾拆分结合在一起：
def swap3(s, lst):
for i, _ in enumerate(s):
head, tail = s[:i], s[i+1:]
yield from ['%s%s%s'%(head,c,tail) for c in lst]
In [16]: timeit [_ for _ in swap3(s, list_new)]
1 loop, best of 3: 3.99 s per loopStack Overflow用户
发布于 2016-12-02 17:58:21
这应该更快：
def _insert_aa(string, index, aa):
return string[0:index] + aa + string[index+1:]编辑:您只可以分割头尾一次，然后像这样重复使用：
def generate_all_variants(string, replacements):
for i in range(len(string)):
head = string[:i]
tail = string[i+1:]
for letter in replacements:
yield head + letter + tail
for variant in generate_all_variants("abcd", ['1', '2', '3']):
print(variant)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40938158
复制相关文章
相似问题
腾讯云开发者
