高效查找和替换 [英] Efficient Find and Replace
问题描述
给定：L =整数列表。 X和Y是整数。
问题：找到X的每个出现并替换为Y
解决方案1：
def check（ s）：
如果s == X：
返回Y
否则返回s
newL = [检查L中的s]
现在我不想创建另一个列表但只是修改它。
解决方案A：
范围内的x（len（L））：
如果L [x] == X：
L [x：x] = Y
解决方案B：
p = L.index（X）
而p> = 0：
L [p：p] = Y
p = L.index（X）
两种解决方案的问题在于效率。在最坏的情况下，两种方法都需要时间为O（N ^ 2），其中N是列表的长度。
因为L.index（）和L [x ：x]在最坏的情况下都需要O（N）时间。但是很明显，人们应该能够及时做到O（N）。至少有一个C
解决方案可以在O（N）时间内完成。
p = head（L）
while （p）{
if（p-> data == X）p-> data = Y;
}
有没有python相当于此？使用迭代器或其他东西
这将允许我有效地串行访问列表元素。
- Murali
Given: L = list of integers. X and Y are integers.
Problem: find every occurence of X and replace with Y
Solution1:
def check(s):
if s==X:
return Y
else return s
newL = [ check(s) for s in L]
Now I dont want to create another list but just modify it in place.
SolutionA:
for x in range(len(L)):
if L[x] == X:
L[x:x] = Y
SolutionB:
p = L.index(X)
while p >= 0:
L[p:p] = Y
p = L.index(X)
Problem with both solutions is the efficiency. Both methods require
time O(N^2) in the worst case, where N is the length of the list.
Because L.index() and L[x:x] both take O(N) time in the worst case. But
clearly one should be able to do it in time O(N). Atleast there is a C
solution which does it in O(N) time.
p = head(L)
while (p) {
if (p->data == X) p->data = Y;
}
Is there a python equivalent of this? using iterators or something
which will allow me efficient serial access to the list elements.
- Murali
推荐答案
Murali写道：
Murali wrote:
现在我不想创建另一个列表但只是修改它。
为什么重要？列表副本很便宜。
解决方案A：
x范围内（len（L））：
如果L [x] == X：
L [x：x] = Y
您是否运行此代码？
SolutionB：
p = L.index （X）
而p> = 0：
L [p：p] = Y
p = L.index（X）
你运行过这段代码吗？
这两种解决方案的问题在于效率。在最坏的情况下，两种方法都需要时间O（N ^ 2），其中N是列表的长度。
因为L.index（）和L [x：x]都取O（N ）在最坏的情况下的时间。
Now I dont want to create another list but just modify it in place.
Why does that matter? List copies are cheap.
SolutionA:
for x in range(len(L)):
if L[x] == X:
L[x:x] = Y
Did you run this code ?
SolutionB:
p = L.index(X)
while p >= 0:
L[p:p] = Y
p = L.index(X)
Did you run this code ?
Problem with both solutions is the efficiency. Both methods require
time O(N^2) in the worst case, where N is the length of the list.
Because L.index() and L[x:x] both take O(N) time in the worst case.
将单个项目分配给L [x：x]不起作用。
将M个项目分配给一个长度为M的切片是一个O（M）操作，所以如果你是
做L [x：x + 1] = [Y]，你得到你的O（1操作。
但这只是写L [x] = Y的一种愚蠢的方式，我认为这是你的意思
。当然，L [x] = Y也是O（1）操作。
< / F>
Assigning a single item to L[x:x] doesn''t work.
Assigning M items to a slice of length M is an O(M) operation, so if you
do L[x:x+1] = [Y], you get your O(1) operation.
But that''s just a silly way to write L[x] = Y, which I assume was what
you meant. L[x] = Y is also an O(1) operation, of course.
</F>
>因为在最坏的情况下，L.index（）和L [x：x]都需要O（N）时间。
为什么你认为L [x ：x]可以是O（N）？
这对我来说看起来是O线性的：
>Because L.index() and L[x:x] both take O(N) time in the worst case.
Why do you think L[x:x] can be O(N)?
This looks O-linear enough to me:
来自随机导入选择
L = [选择（ab）for i in xrange（10）]
L
[''b'' ，'b''，'b''，''''，''b''，''''，''b''，''''，'''''，' x'在xrange（len（L））中的'a'']：
....如果L [x] ==" a"：L [x] =" c" L
from random import choice
L = [choice("ab") for i in xrange(10)]
L [''b'', ''b'', ''b'', ''a'', ''b'', ''a'', ''b'', ''a'', ''a'', ''a''] for x in xrange(len(L)): .... if L[x] == "a": L[x] = "c" L
[''b''，''b''，'b''，''c''，''b' '，''c''，''b''，''c''，''c''，''c'']
再见，
bearophile
[''b'', ''b'', ''b'', ''c'', ''b'', ''c'', ''b'', ''c'', ''c'', ''c'']
Bye,
bearophile
我实际上没有运行代码，因此可能存在语法错误，所以
。但是L [x] = Y是一个O（1）运算。给定x找到L [x]
将需要遍历列表中的x个节点。所以找到L [x]需要
O（x）时间。一旦你找到L [x]设置它是Y是O（1）我同意。
在解B中：由L.index（X），我的意思是搜索X然后用Y替换它。
。每次搜索从
列表的开头开始。因此效率低下。
- Murali
I did not actually run the code, so there may be syntax errors and so
forth. But how is L[x] = Y an O(1) operation. Given x finding L[x]
would require to traverse x nodes in the list. So finding L[x] requires
O(x) time. Once you find L[x] setting it to Y is O(1) I agree.
In Solution B: By L.index(X), I mean search for X and then replace it
with Y. Here every time the search starts from the beginning of the
list. Hence the inefficiency.
- Murali
这篇关于高效查找和替换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
