python__getitem__()方法中LinkedList的实现
Implementation of LinkedList in python __getitem__() method
我正在 python(3.7.4) 中实现一个 LinkedList，模块代码如下：-
LinkedList.py
class Node:
def __init__(self,value):
self.value = value
self.ref = None
class LinkedList(Node):
def __init__(self):
self.__head = None
self.__cur = None
self.__count = 0
def add(self,value):
if self.__head is None:
self.__cur = Node(value)
self.__head = self.__cur
else:
self.__cur.ref = Node(value)
self.__cur = self.__cur.ref
self.__count += 1
def getList(self):
temp = self.__head
while temp!=None:
yield temp.value
temp = temp.ref
def delete(self,value):
temp = self.__head
while temp!=None:
if temp.value == value and temp == self.__head:
self.__head = temp.ref
del temp
self.__count -= 1
break
elif temp.ref != None and temp.ref.value == value:
temp_ref = temp.ref.ref
del temp.ref
self.__count -= 1
temp.ref = temp_ref
break
temp = temp.ref
def __getitem__(self,index):
i = 0
temp = self.__head
if type(index) is int:
while temp!=None:
if i == index:
return temp.value
temp = temp.ref
i += 1
elif type(index) is slice:
if index.start is None:
start = 0
else: start = index.start
if index.stop is None:
stop = self.__count
else: stop = index.stop
if index.step is None:
step = 1
else: step = index.step
returningList = list()
while temp!=None:
if start <= i < stop:
returningList.append(temp.value)
if i==0:
i = start
for _ in range(start):
if temp != None:
temp = temp.ref
else:
i+=step
for _ in range(step):
if temp != None:
temp = temp.ref
return returningList
def __len__(self):
return self.__count
以上功能都运行良好，本模块没有任何错误。
但我的问题是 __getitem__() 方法。我无法为此做出确切的逻辑，而且它变得太大了。
它也不适用于像 obj[-1] 这样的负指数，什么都不返回（ len(obj) 这里不是 0）。
任何人都可以为 __getitem__() 代码优化和降低复杂性的方法提供或建议我正确的逻辑。
您可以这样做，例如：
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = len(self) + index
# check if `index` is valid
# search for the element as you're currently doing.
elif isinstance(index, slice):
return [self[i] for i in range(len(self))[index]]
else:
raise ValueError(f'Linked list cannot be indexed with values of type {type(index)}')
更新： 上面的代码非常简洁，但速度也非常慢。如果我没记错的话，它比 O(n**2) 好一点，而下面的代码 至少快 71.58 倍（做linkedListWith500Elements[::-1]), 应该是 O(n)!
这应该会更快，因为它不会每次都遍历列表来检索切片的下一个元素：
class LinkedList:
...
def __iter__(self):
temp = self.__head
while temp is not None:
yield temp.value
temp = temp.ref
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = len(self) + index
for i, value in enumerate(self):
if i == index:
return value
raise IndexError(f'{type(self).__name__} index {index} out of range(0, {len(self)})')
elif isinstance(index, slice):
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0
rangeOfIndices = iter(rangeOfIndices) if isRangeIncreasing else reversed(rangeOfIndices)
retval = [] # you can preallocate this...
updateRetval = retval.append if isRangeIncreasing else (lambda value: retval.insert(0, value)) # ...and change this accordingly, although I haven't tested whether it'll be faster
try:
searchingForIndex = next(rangeOfIndices)
except StopIteration:
return retval
temp = self.__head
for i, element in enumerate(self):
if temp is None:
break
if i == searchingForIndex:
updateRetval(temp.value)
try:
searchingForIndex = next(rangeOfIndices)
except StopIteration:
return retval
temp = temp.ref
return retval
raise ValueError(f'{type(self).__name__} can only be indexed with integers or slices (not {type(index)})')
预分配列表应该快 22% 左右：
...
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0
# preallocate the list...
retval = [None] * len(rangeOfIndices)
if isRangeIncreasing:
retvalIndex = 0
rangeOfIndices = iter(rangeOfIndices)
# ...and use a different update function
def updateRetval(value):
nonlocal retvalIndex
retval[retvalIndex] = value
retvalIndex += 1
else:
retvalIndex = len(retval) - 1
rangeOfIndices = reversed(rangeOfIndices)
def updateRetval(value):
nonlocal retvalIndex
retval[retvalIndex] = value
retvalIndex -= 1
try:
...
为了用最少的代码解决这个问题，您可以先将链表转换为 python list，然后将 python 列表切片。
但首先您必须将方法 getList(self) 重命名为 __iter__(self)。反正那是规范名称。
现在__getitem__变成一行：
def __getitem__(self, index):
return list(self)[index]
这不是很 space 有效，因为它重复了您的列表。
编辑:
这是一个更有效的解决方案。我再次假设 getList(self) 重命名为 __iter__.
def __getitem__(self, index):
# creates all requested indices or just one int
indices = range(len(self))[index] # constant time and space
if isinstance(indices, int):
return next(value for i, value in enumerate(self) if i == indices) # takes time proportional to the index but constant space
else:
# the double reversing is needed if the step is negative
reverse = -1 if index.step < 0 else 1 # constant time
return [value for i,value in enumerate(self) if i in indices[::reverse]][::reverse] # O(n) time and O(len(indices)) space
这是高效的，因为测试 int 是否在 range 中并且切片 range 需要常数时间。
我已经实现了一个递归函数来解决这个问题，它有一个额外的功能参数，它将显示当前光标的位置，以节省每次调用递归时从第一个节点开始跟踪的时间。
我不是说其他答案是错误的，而是我曾经在我的代码中实现了KISS的原理，其他答案很难理解。
我为 __getitem__() 编辑的代码如下：
class LinkedList(Node):
...
def __getitem__(self,index,fromNode=None):
global i,temp
if fromNode is None:
i,temp = 0,self.__head
if isinstance(index, int):
if index<0: index+=len(self)
while temp!=None:
if i == index:
return temp.value
temp = temp.ref
i += 1
elif isinstance(index, slice):
step = 1 if index.step is None else index.step
start = 0 if index.start is None else index.start
stop=len(self) if index.stop is None else index.stop
if start < 0: start += len(self)
elif step> 0 >stop: stop += len(self)
reverseFlag = True if step<0 else False
if reverseFlag:
trace = iter(reversed(range(len(self))[start:stop:step]))
else:
trace = iter(range(len(self))[start:stop:step])
returningList = [self.__getitem__(indice,temp) for indice in trace]
return list(reversed(returningList)) if reverseFlag else returningList
...
我可以进一步减少这段代码，还是可以从中减少更多的复杂性？如果是，请通过您的回答或评论向我推荐。
我正在 python(3.7.4) 中实现一个 LinkedList，模块代码如下：-
LinkedList.py
class Node:
def __init__(self,value):
self.value = value
self.ref = None
class LinkedList(Node):
def __init__(self):
self.__head = None
self.__cur = None
self.__count = 0
def add(self,value):
if self.__head is None:
self.__cur = Node(value)
self.__head = self.__cur
else:
self.__cur.ref = Node(value)
self.__cur = self.__cur.ref
self.__count += 1
def getList(self):
temp = self.__head
while temp!=None:
yield temp.value
temp = temp.ref
def delete(self,value):
temp = self.__head
while temp!=None:
if temp.value == value and temp == self.__head:
self.__head = temp.ref
del temp
self.__count -= 1
break
elif temp.ref != None and temp.ref.value == value:
temp_ref = temp.ref.ref
del temp.ref
self.__count -= 1
temp.ref = temp_ref
break
temp = temp.ref
def __getitem__(self,index):
i = 0
temp = self.__head
if type(index) is int:
while temp!=None:
if i == index:
return temp.value
temp = temp.ref
i += 1
elif type(index) is slice:
if index.start is None:
start = 0
else: start = index.start
if index.stop is None:
stop = self.__count
else: stop = index.stop
if index.step is None:
step = 1
else: step = index.step
returningList = list()
while temp!=None:
if start <= i < stop:
returningList.append(temp.value)
if i==0:
i = start
for _ in range(start):
if temp != None:
temp = temp.ref
else:
i+=step
for _ in range(step):
if temp != None:
temp = temp.ref
return returningList
def __len__(self):
return self.__count
以上功能都运行良好，本模块没有任何错误。
但我的问题是 __getitem__() 方法。我无法为此做出确切的逻辑，而且它变得太大了。
它也不适用于像 obj[-1] 这样的负指数，什么都不返回（ len(obj) 这里不是 0）。
任何人都可以为 __getitem__() 代码优化和降低复杂性的方法提供或建议我正确的逻辑。
您可以这样做，例如：
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = len(self) + index
# check if `index` is valid
# search for the element as you're currently doing.
elif isinstance(index, slice):
return [self[i] for i in range(len(self))[index]]
else:
raise ValueError(f'Linked list cannot be indexed with values of type {type(index)}')
更新： 上面的代码非常简洁，但速度也非常慢。如果我没记错的话，它比 O(n**2) 好一点，而下面的代码 至少快 71.58 倍（做linkedListWith500Elements[::-1]), 应该是 O(n)!
这应该会更快，因为它不会每次都遍历列表来检索切片的下一个元素：
class LinkedList:
...
def __iter__(self):
temp = self.__head
while temp is not None:
yield temp.value
temp = temp.ref
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = len(self) + index
for i, value in enumerate(self):
if i == index:
return value
raise IndexError(f'{type(self).__name__} index {index} out of range(0, {len(self)})')
elif isinstance(index, slice):
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0
rangeOfIndices = iter(rangeOfIndices) if isRangeIncreasing else reversed(rangeOfIndices)
retval = [] # you can preallocate this...
updateRetval = retval.append if isRangeIncreasing else (lambda value: retval.insert(0, value)) # ...and change this accordingly, although I haven't tested whether it'll be faster
try:
searchingForIndex = next(rangeOfIndices)
except StopIteration:
return retval
temp = self.__head
for i, element in enumerate(self):
if temp is None:
break
if i == searchingForIndex:
updateRetval(temp.value)
try:
searchingForIndex = next(rangeOfIndices)
except StopIteration:
return retval
temp = temp.ref
return retval
raise ValueError(f'{type(self).__name__} can only be indexed with integers or slices (not {type(index)})')
预分配列表应该快 22% 左右：
...
rangeOfIndices = range(len(self))[index]
isRangeIncreasing = rangeOfIndices.start <= rangeOfIndices.stop + 1 and rangeOfIndices.step > 0
# preallocate the list...
retval = [None] * len(rangeOfIndices)
if isRangeIncreasing:
retvalIndex = 0
rangeOfIndices = iter(rangeOfIndices)
# ...and use a different update function
def updateRetval(value):
nonlocal retvalIndex
retval[retvalIndex] = value
retvalIndex += 1
else:
retvalIndex = len(retval) - 1
rangeOfIndices = reversed(rangeOfIndices)
def updateRetval(value):
nonlocal retvalIndex
retval[retvalIndex] = value
retvalIndex -= 1
try:
...
为了用最少的代码解决这个问题，您可以先将链表转换为 python list，然后将 python 列表切片。
但首先您必须将方法 getList(self) 重命名为 __iter__(self)。反正那是规范名称。
现在__getitem__变成一行：
def __getitem__(self, index):
return list(self)[index]
这不是很 space 有效，因为它重复了您的列表。
编辑:
这是一个更有效的解决方案。我再次假设 getList(self) 重命名为 __iter__.
def __getitem__(self, index):
# creates all requested indices or just one int
indices = range(len(self))[index] # constant time and space
if isinstance(indices, int):
return next(value for i, value in enumerate(self) if i == indices) # takes time proportional to the index but constant space
else:
# the double reversing is needed if the step is negative
reverse = -1 if index.step < 0 else 1 # constant time
return [value for i,value in enumerate(self) if i in indices[::reverse]][::reverse] # O(n) time and O(len(indices)) space
这是高效的，因为测试 int 是否在 range 中并且切片 range 需要常数时间。
我已经实现了一个递归函数来解决这个问题，它有一个额外的功能参数，它将显示当前光标的位置，以节省每次调用递归时从第一个节点开始跟踪的时间。
我不是说其他答案是错误的，而是我曾经在我的代码中实现了KISS的原理，其他答案很难理解。
我为 __getitem__() 编辑的代码如下：
class LinkedList(Node):
...
def __getitem__(self,index,fromNode=None):
global i,temp
if fromNode is None:
i,temp = 0,self.__head
if isinstance(index, int):
if index<0: index+=len(self)
while temp!=None:
if i == index:
return temp.value
temp = temp.ref
i += 1
elif isinstance(index, slice):
step = 1 if index.step is None else index.step
start = 0 if index.start is None else index.start
stop=len(self) if index.stop is None else index.stop
if start < 0: start += len(self)
elif step> 0 >stop: stop += len(self)
reverseFlag = True if step<0 else False
if reverseFlag:
trace = iter(reversed(range(len(self))[start:stop:step]))
else:
trace = iter(range(len(self))[start:stop:step])
returningList = [self.__getitem__(indice,temp) for indice in trace]
return list(reversed(returningList)) if reverseFlag else returningList
...
我可以进一步减少这段代码，还是可以从中减少更多的复杂性？如果是，请通过您的回答或评论向我推荐。