双向链表与单链表交换元素的速度
Speed of swapping elements in a doubly linked list Vs a singly list
我写了两个函数：
swapsingle(): swaps elements in a singly linked list
swapdouble(): swaps elements in a doubly linked list
但是我正在阅读的书（Python 中的数据结构和算法 - Michael H. Goldwasser、Michael T. Goodrich 和 Roberto Tamassia）说双向链表中的交换应该比单链表中的那个。但是当我计时两个函数 swapdouble() 时速度较慢
下面是我的两个单链和双链类:
class SingleLL:
""" Singly Linked List Class """
# Nested _Node class
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, next):
self._element = element
self._next = next
def __init__(self):
""" Create an empty Stack"""
self._head = None # Reference to the Head node
self._size = 0
def __len__(self):
""" Returns the number of elements in the stack"""
return self._size
def push(self, e):
""" Add element e to the top of the stack"""
self._head = self._Node(e, self._head)
self._size += 1
def __str__(self):
""" Printing a Linked List"""
# defining a blank result variable
result = ""
# initialising the printer to head
printer = self._head
# traversing and adding it to result
while printer:
result += str(printer._element) + ", "
printer = printer._next
# removing the trailing comma
result = result.strip(', ')
# before printing we check if the list is empty or not
if len(result):
return "[" + result + "]"
else:
return "[]"
class DoubleLL:
"""A base class providing a doubly linked list representation"""
class _Node:
"""Lighweight, non-public class for storing a doubly linked node."""
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, next):
self._element = element
self._prev = prev
self._next = next
def __init__(self):
""" Create an empty list"""
self._header = self._Node(None,None,None)
self._trailer = self._Node(None, None, None)
self._header._next = self._trailer
self._trailer._prev = self._header
self._size = 0
def __len__(self):
return self._size
def _insert_between(self,e, predecessor, successor):
""" Add element e between two existing nodes and return new node."""
newest = self._Node(e,predecessor,successor)
predecessor._next = newest
successor._prev = newest
self._size += 1
#return newest
def push(self, e):
""" Add element e to the front of the list"""
self._insert_between(e,self._header, self._header._next)
def __str__(self):
""" Printing a Linked List"""
# defining a blank result variable
result = ""
# initialising the printer to head
printer = self._header
# traversing and adding it to result
while printer:
result += str(printer._element) + ", "
printer = printer._next
# removing the trailing comma
result = result.strip(', ')
# before printing we check if the list is empty or not
if len(result):
return "[" + result + "]"
else:
return "[]"
这里是我的两个函数的代码，带有测试用例和时间：
def swapsingle(L,a,b):
if a == b:
return
else:
# let's look for the node with 'a' as an element
preva = None
loca = L._head
while loca._next != None and loca._element != a:
preva = loca
loca = loca._next
# let's look for the node with 'b' as an element
prevb = None
locb = L._head
while locb._next != None and locb._element != b:
prevb = locb
locb = locb._next
# if either 'a' or 'b' is not on the linked list, do nothing
if loca == None or locb == None:
return
# if 'a' is not the head of the list
if preva != None:
preva._next = locb
else:
L._head = locb
# if 'b' is not the head of the list
if prevb != None:
prevb._next = loca
else:
L._head = loca
# swap next pointers
temp = loca._next
loca._next = locb._next
locb._next = temp
def swapdouble(L,a,b):
if a == b:
return
else:
# let's look for 'a'
loca = L._header
while loca._next != None and loca._element != a:
loca = loca._next
# let's look for 'b'
locb = L._header
while locb._next != None and locb._element != b:
locb = locb._next
# if either 'a' or 'b' are not on the list, do nothing
if loca == None or locb == None:
return
# change prev
temp = loca._prev
loca._prev = locb._prev
locb._prev._next = loca
locb._prev = temp
temp._next = locb
# change next
temp = loca._next
loca._next = locb._next
locb._next._prev = loca
locb._next = temp
temp._prev = loca
L = SingleLL()
for i in range(1,5):
L.push(i)
print(L)
%timeit swapsingle(L,1,3)
print(L)
D = DoubleLL()
for i in range(1,5):
D.push(i)
print(D)
%timeit swapdouble(D,1,3)
print(D)
这是我的输出：
[4, 3, 2, 1]
844 ns ± 10.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
[4, 1, 2, 3]
[None, 4, 3, 2, 1, None]
1.12 µs ± 2.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
[None, 4, 1, 2, 3, None]
你能解释一下为什么我的双交换比单交换慢，为什么它应该更快？
我认为该声明是关于交换两个节点，仅给出对节点的引用，而不是它们的值（甚至可能不是唯一的）。然后很明显：在 doubly-linked 列表的情况下，您有指向交换节点的前身和后继节点的指针，因此您可以只交换它们。在 singly-linked 列表的情况下，您首先必须遍历列表以找到前任。
我写了两个函数：
swapsingle(): swaps elements in a singly linked list
swapdouble(): swaps elements in a doubly linked list
但是我正在阅读的书（Python 中的数据结构和算法 - Michael H. Goldwasser、Michael T. Goodrich 和 Roberto Tamassia）说双向链表中的交换应该比单链表中的那个。但是当我计时两个函数 swapdouble() 时速度较慢
下面是我的两个单链和双链类:
class SingleLL:
""" Singly Linked List Class """
# Nested _Node class
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, next):
self._element = element
self._next = next
def __init__(self):
""" Create an empty Stack"""
self._head = None # Reference to the Head node
self._size = 0
def __len__(self):
""" Returns the number of elements in the stack"""
return self._size
def push(self, e):
""" Add element e to the top of the stack"""
self._head = self._Node(e, self._head)
self._size += 1
def __str__(self):
""" Printing a Linked List"""
# defining a blank result variable
result = ""
# initialising the printer to head
printer = self._head
# traversing and adding it to result
while printer:
result += str(printer._element) + ", "
printer = printer._next
# removing the trailing comma
result = result.strip(', ')
# before printing we check if the list is empty or not
if len(result):
return "[" + result + "]"
else:
return "[]"
class DoubleLL:
"""A base class providing a doubly linked list representation"""
class _Node:
"""Lighweight, non-public class for storing a doubly linked node."""
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, next):
self._element = element
self._prev = prev
self._next = next
def __init__(self):
""" Create an empty list"""
self._header = self._Node(None,None,None)
self._trailer = self._Node(None, None, None)
self._header._next = self._trailer
self._trailer._prev = self._header
self._size = 0
def __len__(self):
return self._size
def _insert_between(self,e, predecessor, successor):
""" Add element e between two existing nodes and return new node."""
newest = self._Node(e,predecessor,successor)
predecessor._next = newest
successor._prev = newest
self._size += 1
#return newest
def push(self, e):
""" Add element e to the front of the list"""
self._insert_between(e,self._header, self._header._next)
def __str__(self):
""" Printing a Linked List"""
# defining a blank result variable
result = ""
# initialising the printer to head
printer = self._header
# traversing and adding it to result
while printer:
result += str(printer._element) + ", "
printer = printer._next
# removing the trailing comma
result = result.strip(', ')
# before printing we check if the list is empty or not
if len(result):
return "[" + result + "]"
else:
return "[]"
这里是我的两个函数的代码，带有测试用例和时间：
def swapsingle(L,a,b):
if a == b:
return
else:
# let's look for the node with 'a' as an element
preva = None
loca = L._head
while loca._next != None and loca._element != a:
preva = loca
loca = loca._next
# let's look for the node with 'b' as an element
prevb = None
locb = L._head
while locb._next != None and locb._element != b:
prevb = locb
locb = locb._next
# if either 'a' or 'b' is not on the linked list, do nothing
if loca == None or locb == None:
return
# if 'a' is not the head of the list
if preva != None:
preva._next = locb
else:
L._head = locb
# if 'b' is not the head of the list
if prevb != None:
prevb._next = loca
else:
L._head = loca
# swap next pointers
temp = loca._next
loca._next = locb._next
locb._next = temp
def swapdouble(L,a,b):
if a == b:
return
else:
# let's look for 'a'
loca = L._header
while loca._next != None and loca._element != a:
loca = loca._next
# let's look for 'b'
locb = L._header
while locb._next != None and locb._element != b:
locb = locb._next
# if either 'a' or 'b' are not on the list, do nothing
if loca == None or locb == None:
return
# change prev
temp = loca._prev
loca._prev = locb._prev
locb._prev._next = loca
locb._prev = temp
temp._next = locb
# change next
temp = loca._next
loca._next = locb._next
locb._next._prev = loca
locb._next = temp
temp._prev = loca
L = SingleLL()
for i in range(1,5):
L.push(i)
print(L)
%timeit swapsingle(L,1,3)
print(L)
D = DoubleLL()
for i in range(1,5):
D.push(i)
print(D)
%timeit swapdouble(D,1,3)
print(D)
这是我的输出：
[4, 3, 2, 1]
844 ns ± 10.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
[4, 1, 2, 3]
[None, 4, 3, 2, 1, None]
1.12 µs ± 2.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
[None, 4, 1, 2, 3, None]
你能解释一下为什么我的双交换比单交换慢，为什么它应该更快？
我认为该声明是关于交换两个节点，仅给出对节点的引用，而不是它们的值（甚至可能不是唯一的）。然后很明显：在 doubly-linked 列表的情况下，您有指向交换节点的前身和后继节点的指针，因此您可以只交换它们。在 singly-linked 列表的情况下，您首先必须遍历列表以找到前任。