为什么我的 Python 中的排序列表版本不能添加第二个数字？

Question

在下面的代码中，我可以添加第一个数字，但不能添加第二个数字。在 class 中，self 正确更新为 [1, 3]，但实例停留在 [1]。为什么会这样，我该如何解决？

from bisect import bisect
class SortedList(list):
    def __init__(self):
        self = []
    def add(self, x):
        index = bisect(self, x)
        if not self:
            self.append(x)
        else:
            self = self + [x] + self[index:] # after the second call self = [1, 3]
            pass
t = 1
for _ in range(t):
    n, a, b = 24, 3, 5
    if b == 1:
        print('yes')
    else:
        sl = SortedList() # sl = []
        st = set()
        sl.add(1) # sl = [1]
        st.add(1)
        i = 0
        while sl[i] < n: # when i == 1, there's an error because sl = [1]
            num1 = sl[i] * a # num1 = 3
            num2 = sl[i] + b
            if num1 > sl[i] and num1 not in st:
                sl.add(num1) # after this, sl = [1] still
                st.add(num1)
            if num2 > 1 and num2 not in st:
                sl.add(num2)
                st.add(num2)
            if n in st:
                break
            i += 1
        print('yes' if n in st else 'no')

Answer 1

self = []
...
self = self + [x] + self[index:]

这与您认为的不同。每当你写 a = ... （没有在左侧索引，这是特殊的）你实际上并没有改变 a 是什么。相反，你只要把右边的任何东西都给它 name a，忽略之前的 a。

示例：

>>> a = [1, 2, 3]
>>> b = a
>>> a is b
True
>>> id(a), id(b)
(140484089176136, 140484089176136)
>>> a.append(4) # Modification.
>>> b
[1, 2, 3, 4]
>>> a = a + [5] # Modification? No! We create a new object and label it 'a'.
>>> a
[1, 2, 3, 4, 5]
>>> b
[1, 2, 3, 4]
>>> a is b
False
>>> id(a), id(b)
(140484995173192, 140484089176136)

你想要的是 bisect_left 并使用 list.insert:

index = bisect_left(li, x)
li.insert(index, x)

Answer 2

不要修改 self，当您将结果列表分配给 self 时，您会在函数的本地上下文中更改其引用。但远程引用保持不变。在 Is it safe to replace a self object by another object of the same type in a method?

中有更好的解释

通过子分类 `list`:

import bisect

class SortedList(list):

    def append(self, x):
        if not self:
            super(SortedList, self).append(x)
        else:
            idx = bisect.bisect(self, x)
            self.insert(idx, x)

然后：

>>> import random
>>> l = SortedList()
>>> for i in range(10):
...     l.append(random.randint(0, 100))
>>> print(l)
[5, 31, 50, 58, 69, 69, 70, 78, 85, 99]

为了保持列表排序，您还应该覆盖一些魔术方法，例如 __add__、__iadd__ ...

通过换行 `list`:

class SortedList(object):

    def __init__(self):
        self._data = []

    def append(self, x):
        if not self:
            self._data = [x]
        else:
            idx = bisect.bisect(self, x)
            # Here you can change self._data
            # Even `insert` is better, because it don't need to copy the list
            # you can do
            self._data = self._data[:idx] + [x] + self._data[idx:]

但它非常片面，为了使 SortedList 看起来像一个列表，您必须实现 sequence protocol.

Answer 3

谢谢大家。通过如下更改 class，我能够使代码按预期工作：

class SortedList(list):
    def add(self, x):
        index = bisect(self, x)
        self.insert(index, x)

为什么我的 Python 中的排序列表版本不能添加第二个数字？

Why can't my version of a sorted list in Python add a second number?

python

class

instance

通过子分类 `list`:

通过换行 `list`:

为什么我的 Python 中的排序列表版本不能添加第二个数字？

Why can't my version of a sorted list in Python add a second number?

python

class

instance

通过子分类 list:

通过换行 list:

通过子分类 `list`:

通过换行 `list`: