Lin*_* Ma 2 python algorithm linked-list python-2.7
处理这个问题,我的想法是递归的,在每次递归期间,反向打印链表的下半部分,然后反向打印链表的上半部分.因此,额外的空间是O(log n)- 用于递归堆栈的额外空间,但它超过O(n)的时间(O(n log n) - 在递归的每个(log n)级别上的组合调用迭代整个列表将每个部分切成两半).
是否存在实现相同目标的算法 - 反向打印具有少于O(n)空间且最多为O(n)时间的不可变单链表？
源代码(Python 2.7):
class LinkedListNode:
def __init__(self, value, next_node):
self.value = value
self.next_node = next_node
@staticmethod
def reverse_print(list_head, list_tail):
if not list_head:
return
if not list_head.next_node:
print list_head.value
return
if list_head == list_tail:
print list_head.value
return
p0 = list_head
p1 = list_head
while p1.next_node != list_tail and p1.next_node.next_node != list_tail:
p1 = p1.next_node
p1 = p1.next_node
p0 = p0.next_node
LinkedListNode.reverse_print(p0.next_node, list_tail)
LinkedListNode.reverse_print(list_head, p0)
if __name__ == "__main__":
list_head = LinkedListNode(4, LinkedListNode(5, LinkedListNode(12, LinkedListNode(1, LinkedListNode(3, None)))))
LinkedListNode.reverse_print(list_head, None)
这是O(n)时间和O(sqrt(n))空间算法.在帖子的第二部分,它将扩展到线性时间和O(n ^(1/t))空间算法,用于任意正整数t.
高级想法:将列表拆分为sqrt(n)许多(几乎)相等大小的部分.使用从最后到第一个的朴素线性时间线性空间方法以相反的顺序依次打印部件.
要存储部件的起始节点,我们需要一个大小为O(sqrt(n))的数组.要恢复大小约为sqrt(n)的部分,朴素算法需要一个数组来存储对部件节点的引用.所以数组的大小为O(sqrt(n).
一个使用两个大小(lsa和ssa)的数组(k=[sqrt(n)]+1 =O(sqrt(n))
lsa ...大步长数组,ssa ...小步长数组)
阶段1 :(如果链接列表的大小未知,则找出n,其长度):从头到尾遍历列表并计算列表的元素,这需要n个步骤
阶段2: 将单个链表的每个第k个节点存储在数组中
lsa.这需要n个步骤.阶段3:
lsa以相反的顺序 处理列表.以相反的顺序打印每个部分这也需要n个步骤
因此算法的运行时间为3n = O(n),其速度约为2*sqrt(n)= O(sqrt(n)).
这是一个Python 3.5实现:
import cProfile
import math
class LinkedListNode:
def __init__(self, value, next_node):
self.value = value
self._next_node = next_node
def next_node(self):
return(self._next_node)
def reverse_print(self):
# Phase 1
n=0
node=self
while node:
n+=1
node=node.next_node()
k=int(n**.5)+1
# Phase 2
i=0
node=self
lsa=[node]
while node:
i+=1
if i==k:
lsa.append(node)
i=0
last_node=node
node=node.next_node()
if i>0:
lsa.append(last_node)
# Phase 3
start_node=lsa.pop()
print(start_node.value)
while lsa:
last_printed_node=start_node
start_node=lsa.pop()
node=start_node
ssa=[]
while node!=last_printed_node:
ssa.append(node)
node=node.next_node()
ssa.reverse()
for node in ssa:
print(node.value)
@classmethod
def create_testlist(nodeclass, n):
''' creates a list of n elements with values 1,...,n'''
first_node=nodeclass(n,None)
for i in range(n-1,0,-1):
second_node=first_node
first_node=nodeclass(i,second_node)
return(first_node)
if __name__ == "__main__":
n=1000
cProfile.run('LinkedListNode.create_testlist(n).reverse_print()')
print('estimated number of calls of next_node',3*n)
它打印以下输出(最后是分析器的输出,显示函数调用的数量):
>>>
RESTART: print_reversed_list3.py
1000
999
998
...
4
3
2
1
101996 function calls in 2.939 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 2.939 2.939 <string>:1(<module>)
2000 0.018 0.000 2.929 0.001 PyShell.py:1335(write)
1 0.003 0.003 2.938 2.938 print_reversed_list3.py:12(reverse_print)
1 0.000 0.000 0.001 0.001 print_reversed_list3.py:49(create_testlist)
1000 0.000 0.000 0.000 0.000 print_reversed_list3.py:5(__init__)
2999 0.000 0.000 0.000 0.000 print_reversed_list3.py:9(next_node)
...
estimated number of calls of next_node 3000
>>>
对next_node()的调用次数是预期的3000
不是使用朴素的O(m)空间算法以相反的顺序打印长度为m的子列表,而是可以使用该O(sqrt(m))空间算法.但我们必须在子列表的数量和子列表的长度之间找到适当的平衡:
阶段2:将简单链接列表拆分为长度为n ^(2/3)的n ^(1/3)子列表.这些子列表的起始节点存储在长度为n ^(1/3)的数组中
阶段3:使用O(sqrt(m))空间算法以相反的顺序打印长度m = n ^(2/3)的每个子列表.因为m = n ^(2/3),我们需要m ^(1/2)= n ^(1/3)空间.
我们现在有一个需要4n时间的O(n ^(1/3))空间算法,因此仍然是O(n)
我们可以通过分裂成长度m = n ^(3/4)的n ^(1/4)子列表再次重复这一点,由O(m ^(1/3))= O(n ^(1/4))需要5n = O(n)时间的空间算法.
我们可以一次又一次地重复这一点,并得出以下声明:
大小为n的不可变简单链表可以使用t*n ^(1/t)= O(n ^(1/t))空间和(t + 1)n = O(n)时间以相反顺序打印t是任意正整数
如果一个不修复t但是选择t取决于n,使得n ^(1/t))大约2,最小的有用数组大小,则这导致O(nlog(n))时间和O(log(n) ))由OP描述的空间算法.
如果选择t = 1,则导致O(n)时间和O(n)空间天真算法.
这是算法的实现
import cProfile
import math
import time
class LinkedListNode:
'''
single linked list node
a node has a value and a successor node
'''
stat_counter=0
stat_curr_space=0
stat_max_space=0
stat_max_array_length=0
stat_algorithm=0
stat_array_length=0
stat_list_length=0
stat_start_time=0
do_print=True
def __init__(self, value, next_node):
self.value = value
self._next_node = next_node
def next_node(self):
self.stat_called_next_node()
return(self._next_node)
def print(self):
if type(self).do_print:
print(self.value)
def print_tail(self):
node=self
while node:
node.print()
node=node.next_node()
def tail_info(self):
list_length=0
node=self
while node:
list_length+=1
last_node=node
node=node.next_node()
return((last_node,list_length))
def retrieve_every_n_th_node(self,step_size,list_length):
''' for a list a of size list_length retrieve a pair there the first component
is an array with the nodes
[a[0],a[k],a[2*k],...,a[r*k],a[list_length-1]]]
and the second component is list_length-1-r*k
and
'''
node=self
arr=[]
s=step_size
index=0
while index<list_length:
if s==step_size:
arr.append(node)
s=1
else:
s+=1
last_node=node
node=node.next_node()
index+=1
if s!=1:
last_s=s-1
arr.append(last_node)
else:
last_s=step_size
return(arr,last_s)
def reverse_print(self,algorithm=0):
(last_node,list_length)=self.tail_info()
assert(type(algorithm)==int)
if algorithm==1:
array_length=list_length
elif algorithm==0:
array_length=2
elif algorithm>1:
array_length=math.ceil(list_length**(1/algorithm))
if array_length<2:
array_length=2
else:
assert(False)
assert(array_length>=2)
last_node.print()
self.stat_init(list_length=list_length,algorithm=algorithm,array_length=array_length)
self._reverse_print(list_length,array_length)
assert(LinkedListNode.stat_curr_space==0)
self.print_statistic()
def _reverse_print(self,list_length,array_length):
'''
this is the core procedure of the algorithm
if the list fits into the array
store it in te array an print the array in reverse order
else
split the list in 'array_length' sublists and store
the startnodes of the sublists in he array
_reverse_print array in reverse order
'''
if list_length==3 and array_length==2: # to avoid infinite loop
array_length=3
step_size=math.ceil(list_length/array_length)
if step_size>1: # list_length>array_length:
(supporting_nodes,last_step_size)=self.retrieve_every_n_th_node(step_size,list_length)
self.stat_created_array(supporting_nodes)
supporting_nodes.reverse()
supporting_nodes[1]._reverse_print(last_step_size+1,array_length)
for node in supporting_nodes[2:]:
node._reverse_print(step_size+1,array_length)
self.stat_removed_array(supporting_nodes)
else:
assert(step_size>0)
(adjacent_nodes,last_step_size)=self.retrieve_every_n_th_node(1,list_length)
self.stat_created_array(adjacent_nodes)
adjacent_nodes.reverse()
for node in adjacent_nodes[1:]:
node.print()
self.stat_removed_array(adjacent_nodes)
# statistics functions
def stat_init(self,list_length,algorithm,array_length):
'''
initializes the counters
and starts the stop watch
'''
type(self)._stat_init(list_length,algorithm,array_length)
@classmethod
def _stat_init(cls,list_length,algorithm,array_length):
cls.stat_curr_space=0
cls.stat_max_space=0
cls.stat_counter=0
cls.stat_max_array_length=0
cls.stat_array_length=array_length
cls.stat_algorithm=algorithm
cls.stat_list_length=list_length
cls.stat_start_time=time.time()
def print_title(self):
'''
prints the legend and the caption for the statistics values
'''
type(self).print_title()
@classmethod
def print_title(cls):
print(' {0:10s} {1:s}'.format('space','maximal number of array space for'))
print(' {0:10s} {1:s}'.format('', 'pointers to the list nodes, that'))
print(' {0:10s} {1:s}'.format('', 'is needed'))
print(' {0:10s} {1:s}'.format('time', 'number of times the method next_node,'))
print(' {0:10s} {1:s}'.format('', 'that retrievs the successor of a node,'))
print(' {0:10s} {1:s}'.format('', 'was called'))
print(' {0:10s} {1:s}'.format('alg', 'algorithm that was selected:'))
print(' {0:10s} {1:s}'.format('', '0: array size is 2'))
print(' {0:10s} {1:s}'.format('', '1: array size is n, naive algorithm'))
print(' {0:10s} {1:s}'.format('', 't>1: array size is n^(1/t)'))
print(' {0:10s} {1:s}'.format('arr', 'dimension of the arrays'))
print(' {0:10s} {1:s}'.format('sz', 'actual maximal dimension of the arrays'))
print(' {0:10s} {1:s}'.format('n', 'list length'))
print(' {0:10s} {1:s}'.format('log', 'the logarithm to base 2 of n'))
print(' {0:10s} {1:s}'.format('n log n', 'n times the logarithm to base 2 of n'))
print(' {0:10s} {1:s}'.format('seconds', 'the runtime of the program in seconds'))
print()
print('{0:>10s} {1:>10s} {2:>4s} {3:>10s} {4:>10s} {5:>10s} {6:>5s} {7:>10s} {8:>10s}'
.format('space','time','alg','arr','sz','n','log', 'n log n','seconds'))
@classmethod
def print_statistic(cls):
'''
stops the stop watch and prints the statistics for the gathered counters
'''
run_time=time.time()-cls.stat_start_time
print('{0:10d} {1:10d} {2:4d} {3:10d} {4:10d} {5:10d} {6:5d} {7:10d} {8:10.2f}'.format(
cls.stat_max_space,cls.stat_counter,cls.stat_algorithm,
cls.stat_array_length,cls.stat_max_array_length,cls.stat_list_length,
int(math.log2(cls.stat_list_length)),int(cls.stat_list_length*math.log2(cls.stat_list_length)),
run_time
))
def stat_called_next_node(self):
'''
counter: should be called
if the next node funtion is called
'''
type(self)._stat_called_next_node()
@classmethod
def _stat_called_next_node(cls):
cls.stat_counter+=1
def stat_created_array(self,array):
'''
counter: should be called
after an array was created and filled
'''
type(self)._stat_created_array(array)
@classmethod
def _stat_created_array(cls,array):
cls.stat_curr_space+=len(array)
if cls.stat_curr_space> cls.stat_max_space:
cls.stat_max_space=cls.stat_curr_space
if (len(array)>cls.stat_max_array_length):
cls.stat_max_array_length=len(array)
def stat_removed_array(self,array):
'''
counter: should be called
before an array can be removed
'''
type(self)._stat_removed_array(array)
@classmethod
def _stat_removed_array(cls,array):
cls.stat_curr_space-=len(array)
@classmethod
def create_testlist(nodeclass, n):
'''
creates a single linked list of
n elements with values 1,...,n
'''
first_node=nodeclass(n,None)
for i in range(n-1,0,-1):
second_node=first_node
first_node=nodeclass(i,second_node)
return(first_node)
if __name__ == "__main__":
#cProfile.run('LinkedListNode.create_testlist(n).reverse_print()')
n=100000
ll=LinkedListNode.create_testlist(n)
LinkedListNode.do_print=False
ll.print_title()
ll.reverse_print(1)
ll.reverse_print(2)
ll.reverse_print(3)
ll.reverse_print(4)
ll.reverse_print(5)
ll.reverse_print(6)
ll.reverse_print(7)
ll.reverse_print(0)
以下是一些结果
space maximal number of array space for
pointers to the list nodes, that
is needed
time number of times the method next_node,
that retrievs the successor of a node,
was called
alg algorithm that was selected:
0: array size is 2
1: array size is n, naive algorithm
t>1: array size is n^(1/t)
arr dimension of the arrays
sz actual maximal dimension of the arrays
n list length
log the logarithm to base 2 of n
n log n n times the logarithm to base 2 of n
seconds the runtime of the program in seconds
space time alg arr sz n log n log n seconds
100000 100000 1 100000 100000 100000 16 1660964 0.17
635 200316 2 317 318 100000 16 1660964 0.30
143 302254 3 47 48 100000 16 1660964 0.44
75 546625 4 18 19 100000 16 1660964 0.99
56 515989 5 11 12 100000 16 1660964 0.78
47 752976 6 7 8 100000 16 1660964 1.33
45 747059 7 6 7 100000 16 1660964 1.23
54 1847062 0 2 3 100000 16 1660964 3.02
和
space maximal number of array space for
pointers to the list nodes, that
is needed
time number of times the method next_node,
that retrievs the successor of a node,
was called
alg algorithm that was selected:
0: array size is 2
1: array size is n, naive algorithm
t>1: array size is n^(1/t)
arr dimension of the arrays
sz actual maximal dimension of the arrays
n list length
log the logarithm to base 2 of n
n log n n times the logarithm to base 2 of n
seconds the runtime of the program in seconds
space time alg arr sz n log n log n seconds
1000000 1000000 1 1000000 1000000 1000000 19 19931568 1.73
2001 3499499 2 1000 1001 1000000 19 19931568 7.30
302 4514700 3 100 101 1000000 19 19931568 8.58
131 4033821 4 32 33 1000000 19 19931568 5.69
84 6452300 5 16 17 1000000 19 19931568 11.04
65 7623105 6 10 11 1000000 19 19931568 13.26
59 7295952 7 8 9 1000000 19 19931568 11.07
63 21776637 0 2 3 1000000 19 19931568 34.39
就该问题的空间/时间要求而言,频谱有两端:
既然你不关心O(n)空间解决方案,让我们看看另一个:
def reverse_print(LL):
length = 0
curr = LL
while curr:
length += 1
curr = curr.next
for i in range(length, 0, -1):
curr = LL
for _ in range(i):
curr = curr.next
print(curr.value)
当然,如果您选择将其转换为双向链接列表,则可以在O(n)时间和0空间中执行此操作