在不使用内置函数的情况下反转列表

I'm using Python 3.5.

我使用Python 3.5。

As part of a problem, I'm trying to design a function that takes a list as input and reverts it. So if x = [a, b, c] the function would make x = [c, b, a].

作为问题的一部分，我尝试设计一个函数，它以列表作为输入，并返回它。如果x = [a, b, c]函数会令x = [c, b, a]

The problem is, I'm not allowed to use any built-in functions, and it has got me stuck. My initial thought was the following loop inside a function:

问题是，我不允许使用任何内置函数，这让我陷入了困境。我最初的想法是在一个函数内循环如下:

for revert in range(1, len(x) + 1):
    y.append(x[-revert])

And it works. But the problem is I'm using len(x), which I believe is a built-in function, correct?

和它的工作原理。但问题是，我使用的是len(x)，我认为它是一个内置函数，对吧?

So I searched around and have made the following very simple code:

所以我四处搜索，做了如下简单的代码:

y = x[::-1]

Which does exactly what I wanted, but it just seems almost too simple/easy and I'm not sure whether "::" counts as a function.

它做的正是我想要的，但它似乎太简单/太简单了，我不确定是否“:”作为一个函数。

So I was wondering if anyone had any hints/ideas how to manually design said function? It just seems really hard when you can't use any built-in functions and it has me stuck for quite some time now.

所以我想知道有没有人知道如何手动设计这个功能?当你不能使用任何内置函数时，它看起来真的很困难，它让我陷入了很长一段时间。

8 个解决方案

#1

range and len are both built-in functions. Since list methods are accepted, you could do this with insert. It is reeaallyy slow^* but it does the job for small lists without using any built-ins:

range和len都是内置函数。由于列表方法是可接受的，您可以使用insert来实现这一点。它确实很慢*但是它在小列表中没有使用任何内置列表:

def rev(l):
    r = []
    for i in l:
        r.insert(0, i)
    return r

By continuously inserting at the zero-th position you end up with a reversed version of the input list:

通过在第0位连续插入，您最终得到的是输入列表的反向版本:

>>> print(rev([1, 2, 3, 4]))
[4, 3, 2, 1]

Doing:

做的事情:

def rev(l): 
    return l[::-1]

could also be considered a solution. ::-1 (:: has a different result) isn't a function (it's a slice) and [] is, again, a list method. Also, contrasting insert, it is faster and way more readable; just make sure you're able to understand and explain it. A nice explanation of how it works can be found in this S.O answer.

也可以被认为是一种解决方案。::-1(:有不同的结果)不是函数(它是一个片)，而[]又是一个列表方法。另外，对比插入，它更快，可读性更强;确保你能理解并解释它。关于它是如何工作的一个很好的解释可以在这里找到。O回答。

^{*Reeaaalllyyyy slow, see juanpa.arrivillaga's answer for cool plot and append with pop and take a look at in-place reverse on lists as done in Yoav Glazner's answer.}

* Reeaaalllyyyy缓慢,看到juanpa。arrivillaga对《cool plot》的回答，加上流行音乐，并看一下列表上的反向，就像Yoav Glazner的回答一样。

#2

:: is not a function, it's a python literal. as well as []

:不是函数，而是python的文字。以及[]

How to check if ::, [] are functions or not. Simple,

如何检查:，[]是否为函数。简单,

    import dis
    a = [1,2]
    dis.dis(compile('a[::-1]', '', 'eval'))
      1           0 LOAD_NAME                0 (a)
                  3 LOAD_CONST               0 (None)
                  6 LOAD_CONST               0 (None)
                  9 LOAD_CONST               2 (-1)
                 12 BUILD_SLICE              3
                 15 BINARY_SUBSCR
                 16 RETURN_VALUE

If ::,[] were functions, you should find a label CALL_FUNCTION among python instructions executed by a[::-1] statement. So, they aren't.

如果::[]是函数，那么您应该在由[:-1]语句执行的python指令中找到一个label CALL_FUNCTION。所以,他们不是。

Look how python instructions looks like when you call a function, lets say list() function

当您调用一个函数时，让我们说list()函数，看看python指令是什么样子的

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE

So, basically

所以,基本上

def rev(f):
    return f[::-1]

works fine. But, I think you should do something like Jim suggested in his answer if your question is a homework or sent by you teacher. But, you can add this quickest way as a side note.

工作很好。但是，我认为你应该做一些像吉姆在他的回答中提出的问题，如果你的问题是家庭作业或者是老师送的。但是，您可以添加这个最快的方法作为补充说明。

If you teacher complains about [::-1] notation, show him the example I gave you.

如果你的老师抱怨[:::-1]符号，给他看我给你的例子。

#3

Another way ( just for completeness :) )

另一种方式(只是为了完整性:)

def another_reverse(lst):
    new_lst = lst.copy() # make a copy if you don't want to ruin lst...
    new_lst.reverse() # notice! this will reverse it in place
    return new_lst

#4

Here's a solution that doesn't use built-in functions but relies on list methods. It reverse in-place, as implied by your specification:

这里有一个解决方案，它不使用内置函数，而是依赖于列表方法。如你的说明所暗示的，它会反向运行:

>>> x = [1,2,3,4]
>>> def reverse(seq):
...   temp = []
...   while seq:
...     temp.append(seq.pop())
...   seq[:] = temp
... 
>>> reverse(x)
>>> x
[4, 3, 2, 1]
>>>

ETA

Jim, your answer using insert at position 0 was driving me nuts! That solution is quadratic time! You can use append and pop with a temporary list to achieve linear time using simple list methods. See (reverse is in blue, rev is green):

吉姆，你在0点插入的答案让我抓狂!这个解是二次时间!您可以使用append和pop的临时列表来实现线性时间，使用简单的列表方法。见(反向为蓝色，rev为绿色):

If it feels a little bit like "cheating" using seq[:] = temp, we could always loop over temp and append every item into seq and the time complexity would still be linear but probably slower since it isn't using the C-based internals.

如果它感觉有点像使用seq[:] = temp的“作弊”，那么我们可以对temp进行循环，并将每一项添加到seq中，并且时间复杂度仍然是线性的，但可能会更慢，因为它不使用基于c的内部元素。

#5

Your example that works:

你的工作的例子:

y = x[::-1]

uses Python slices notation which is not a function in the sense that I assume you're requesting. Essentially :: acts as a separator. A more verbose version of your code would be:

使用Python切片表示法，它不是我假设你要求的函数。本质上::充当分隔符。更详细的代码版本是:

y = x[len(x):None:-1]

或

y = x[start:end:step]

I probably wouldn't be complaining that python makes your life really, really easily.

我可能不会抱怨python让你的生活变得非常非常简单。

Edit to be super pedantic. Someone could argue that calling [] at all is using an inbuilt python function because it's really syntactical sugar for the method __getitem__().

编辑成超级书呆子。有人可能会说，调用[]是使用内置的python函数，因为它实际上是方法__getitem__()的语法糖。

x.__getitem__(0) == x[0]

And using :: does make use of the slice() object.

并使用::确实使用了slice()对象。

x.__getitem__(slice(len(x), None, -1) == x[::-1]

But... if you were to argue this, anything you write in python would be using inbuilt python functions.

但是…如果您对此有异议，您在python中编写的任何内容都将使用内置的python函数。

#6

Another way for completeness, range() takes an optional step parameter that will allow you to step backwards through the list:

为了完整性，range()采用了一个可选的步骤参数，允许您在列表中后退一步:

def reverse_list(l):
    return [l[i] for i in range(len(l)-1, -1, -1)]

#7

The most pythonic and efficient way to achieve this is by list slicing. And, since you mentioned you do not need any inbuilt function, it completely suffice your requirement. For example:

实现这一点的最python化和有效的方法是列表切片。而且，由于您提到您不需要任何内置函数，因此它完全满足您的需求。例如:

>>> def reverse_list(list_obj):
...     return list_obj[::-1]
...
>>> reverse_list([1, 3, 5 , 3, 7])
[7, 3, 5, 3, 1]

#8

Just iterate the list from right to left to get the items..

只需从右到左迭代列表以获取项。

a = [1,2,3,4]

def reverse_the_list(a):
   reversed_list = []
   for i in range(0, len(a)):
     reversed_list.append(a[len(a) - i - 1])
   return reversed_list

new_list = reverse_the_list(a)
print new_list

#1