面试题：Python自定义数据结构索引边界处理的优化

class MyList:
    def __init__(self, initial_capacity=4):
        self.capacity = initial_capacity
        self.length = 0
        self.data = [None] * self.capacity

    def append(self, value):
        if self.length == self.capacity:
            self._resize()
        self.data[self.length] = value
        self.length += 1

    def _resize(self):
        self.capacity *= 2
        new_data = [None] * self.capacity
        for i in range(self.length):
            new_data[i] = self.data[i]
        self.data = new_data

    def __getitem__(self, index):
        if isinstance(index, slice):
            start, stop, step = index.start, index.stop, index.step
            if start is None:
                start = 0
            if stop is None:
                stop = self.length
            if step is None:
                step = 1
            if start < 0:
                start += self.length
            if stop < 0:
                stop += self.length
            return [self.data[i] for i in range(start, stop, step)]
        else:
            if index < 0:
                index += self.length
            if index < 0 or index >= self.length:
                raise IndexError('list index out of range')
            return self.data[index]

    def __setitem__(self, index, value):
        if index < 0:
            index += self.length
        if index < 0 or index >= self.length:
            raise IndexError('list index out of range')
        self.data[index] = value

    def __len__(self):
        return self.length

索引边界检查的优化策略

对于正向索引：在 __getitem__ 和 __setitem__ 方法中，当获取或设置元素时，直接检查索引是否小于0或者大于等于当前列表的长度。如果是，抛出 IndexError 异常。这种检查方式简单直接，对于大规模数据，每次索引操作的时间复杂度是O(1)，不会随着数据规模的增大而显著增加额外开销。
对于负向索引：将负向索引转换为正向索引后再进行边界检查。具体做法是将负向索引值加上列表的长度，这样就得到了对应的正向索引，然后再按照正向索引的检查方式进行检查。这种转换操作同样时间复杂度为O(1)，在处理大规模数据时不会带来过多性能负担。
切片操作：对于切片操作，首先处理切片对象中的 start、stop 和 step 参数，将 None 值替换为默认值。对于负向的 start 和 stop，同样转换为正向索引。最后通过 range 生成切片范围内的索引列表，并获取对应的值。这种处理方式虽然涉及到循环生成索引列表，但整体操作的时间复杂度是线性的，与切片的范围相关，而不是与整个数据规模相关，在大规模数据下也能保持相对较好的性能。

面试题：Python自定义数据结构索引边界处理的优化

知识考点

面试题答案

索引边界检查的优化策略