python - 反向打印一个空间小于 O(n) 的不可变链表

Question

处理这个问题，我的想法是递归，在每次递归期间，反向打印链表的第二半，然后反向打印链表的第一半。所以额外的空间是 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)

Answer 1

这是一个 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 ..小步阵)

Phase 1: (if the size of the linked list is not known find out n, its length): move through the list from start to end and count the elements of the list, this needs n steps

Phase 2: Store each k-th node of the single linked list in the array lsa. This needs n steps.

Phase 3: Process the lsalist in reverse order. Print each part in reverse order This takes also n steps

因此该算法的运行时间为 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(sqrt(m)) 空间算法，而不是使用简单的 O(m) 空间算法以相反的顺序打印长度为 m 的子列表。但是我们必须在子列表的数量和子列表的长度之间找到合适的平衡:

第 2 阶段:将简单链表拆分为 n^(1/3) 个长度为 n^(2/3) 的子列表。这些子列表的起始节点存储在一个长度为n^(1/3)的数组中

阶段 3:使用 O(sqrt(m)) 空间算法以相反的顺序打印每个长度为 m=n^(2/3) 的子列表。因为 m=n^(2/3) 我们需要 m^(1/2)=n^(1/3) 空间。

我们现在有一个 O(n^(1/3)) 空间算法，它需要 4n 时间，所以仍然是 O(n)

我们可以通过拆分为 n^(1/4) 个长度为 m=n^(3/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 而是根据 n 选择 t 使得 n^(1/t)) 大约为 2，这是最小的有用数组大小​​，那么这将导致 O(nlog(n)) 时间和 O( OP 描述的 log(n)) 空间算法。

如果选择 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