指向python中的指针

Question

我是python的新手,我试图理解如何将Python与C/C++联系起来.考虑问题:检查给定的链接列表是否是回文.从这个来源,我发现了一个非常有效的解决方案:

// Initial parameters to this function are &head and head
bool isPalindromeUtil(struct node **left, struct  node *right)
{
   /* stop recursion when right becomes NULL */
   if (right == NULL)
      return true;

   /* If sub-list is not palindrome then no need to
       check for current left and right, return false */
   bool isp = isPalindromeUtil(left, right->next);
   if (isp == false)
      return false;

   /* Check values at current left and right */
   bool isp1 = (right->data == (*left)->data);

   /* Move left to next node */
   *left = (*left)->next;

   return isp1;
}

// A wrapper over isPalindromeUtil()
bool isPalindrome(struct node *head)
{
   isPalindromeUtil(&head, head);
}

基本上,指向指针的指针被分配给前面(左指针),指针被指定给列表的末尾(右指针).一旦指针到达各自的位置,它们就会递归并找到匹配值.这里,*left维持指向指针的状态,该指针的值在递归循环中持续存在.python中的一个解决方案是将左指针传递回布尔值.但是,如果有多个指向指针的指针,则返回元素的数量会爆炸!糟糕的设计.这样做还有其他办法吗？

编辑:

非常感谢您的回复!我忘了提到我不是想在这里解决回文问题.我试图了解是否有一个使用Pythonic等效的方法来处理指针.我想要理解的是,如果向我提出一个使用链表等数据结构的问题,我是否应该尝试将其转换为其他数据结构(如列表)或者如果我需要创造性并使用问题解决问题相同的数据结构.由于指向指针是链接列表和BST中非常重要的概念,是否有相同的解决方案或解决此概念？

编辑#2:我提出的粗略代码如下.但是,left_ptr仍然停留在相同的位置,因为它是一个指针,而不是指向指针的指针:

def palindrome_utils(self, left_ptr, right_ptr):
        if right_ptr is None:
                return True
        prev_result = self.palindrome_utils(left_ptr, right_ptr.get_link())

        cur_result = left_ptr.get_data() == right_ptr.get_data()
        left_ptr = left_ptr.get_link()
        return cur_result and prev_result

def palindrome(self):
        return self.palindrome_utils(self.head, self.head)

Answer 1

编辑:添加l == l[::-1]为is_palindrome5,这是非常快,到目前为止最可读和pythonic.

我可以检查回收的最快速度是这个单线程:

def is_palindrome1(l):
    return l[:len(l) / 2] == l[(len(l)+1) / 2:][::-1]

在您的问题中对c ++函数的python转换检查非回文是最快的:

def is_palindrome2(l):
        left = 0
        right = len(l) - 1
        for i in xrange(0,len(l) / 2):
            if l[right] != l[left]:
                return False
            left += 1
            right -= 1
        return True

这是因为在开始比较元素之前,此函数不会创建任何新列表.请注意,我使用的是第一个和最后一个元素不同的非回文,因此检查在第一次比较后立即返回(对于非回文并非总是如此).

我还测试了mistermiyagi(is_palindrome3)的答案和PM 2Ring(is_palindrome4)的答案:

import itertools

def create_palindrome(n):
    return range(1,n) + range(n,0,-1)

def is_palindrome1(l):
    return l[:len(l) / 2] == l[(len(l)+1) / 2:][::-1]

def is_palindrome2(l):
    left = 0
    right = len(l) - 1
    for i in xrange(0,len(l) / 2):
        if l[right] != l[left]:
            return False
        left += 1
        right -= 1
    return True

def is_palindrome3(seq):
    for l, r in itertools.izip(iter(seq), reversed(seq)):
        if l != r:
            return False
    return True

def is_palindrome4(seq):
    return all(l == r
               for _, l, r in itertools.izip(xrange((1 + len(seq)) // 2),
                                             iter(seq), reversed(seq)))

def is_palindrome5(l):
    return l == l[::-1]

if __name__ == '__main__':
    import timeit

    setup_palindrome = "from __main__ import create_palindrome, %s; l = create_palindrome(%i)"
    setup_non_palindrome = "from __main__ import %s; l=range(%i)"

def test(f, n):
    return (timeit.timeit("%s(l)" % f, setup=setup_palindrome % (f, n), number=100000),
            timeit.timeit("%s(l)" % f, setup=setup_non_palindrome % (f, n), number=100000))

small = 5
big = 1000

for f in is_palindrome1, is_palindrome2, is_palindrome3, is_palindrome4:
    print("%s small list: palindrome: %f non-palindrome: %f" % ((f.__name__,) + test(f.__name__, small)))
for f in is_palindrome1, is_palindrome2, is_palindrome3, is_palindrome4:
    print("%s big list: palindrome: %f non-palindrome: %f" % ((f.__name__,) + test(f.__name__, big)))

结果:

is_palindrome1 small list: palindrome: 0.093779 non-palindrome: 0.073669
is_palindrome2 small list: palindrome: 0.087658 non-palindrome: 0.048855
is_palindrome3 small list: palindrome: 0.085866 non-palindrome: 0.056385
is_palindrome4 small list: palindrome: 0.139685 non-palindrome: 0.123519
is_palindrome5 small list: palindrome: 0.021798 non-palindrome: 0.022422
is_palindrome1 big list: palindrome: 1.589591 non-palindrome: 0.432679
is_palindrome2 big list: palindrome: 9.414250 non-palindrome: 0.043481
is_palindrome3 big list: palindrome: 7.315568 non-palindrome: 0.056859
is_palindrome4 big list: palindrome: 6.655833 non-palindrome: 0.128915
is_palindrome5 big list: palindrome: 2.095099 non-palindrome: 0.283472