Hướng dẫn reverse list python stack overflow - đảo ngược danh sách ngăn xếp python tràn

Tóm tắt các phương pháp đảo ngược

Có ba cách tích hợp khác nhau để đảo ngược một danh sách. Phương pháp nào là tốt nhất phụ thuộc vào việc bạn cần:

1. Đảo ngược một danh sách hiện có tại chỗ (thay đổi biến danh sách ban đầu)
   • Giải pháp tốt nhất là phương pháp object.reverse()
2. Tạo một trình lặp của danh sách đảo ngược (vì bạn sẽ đưa nó vào một vòng lặp, một máy phát, v.v.)
   • Giải pháp tốt nhất là

     def rev_in_place(mylist):
         mylist.reverse()
         return mylist
     
     def rev_copy_reverse(mylist):
         a = copy(mylist)
         a.reverse()
         return a
     

     0 tạo ra trình lặp
3. Tạo một bản sao của danh sách, chỉ theo thứ tự ngược lại (để bảo tồn danh sách ban đầu)
   • Giải pháp tốt nhất là sử dụng các lát có kích thước -1 bước:

     def rev_in_place(mylist):
         mylist.reverse()
         return mylist
     
     def rev_copy_reverse(mylist):
         a = copy(mylist)
         a.reverse()
         return a
     

     1

Từ góc độ tốc độ, tốt nhất là sử dụng các chức năng tích hợp ở trên để đảo ngược danh sách. Để đảo ngược, chúng nhanh hơn 2 đến 8 lần trong các danh sách ngắn (10 mục) và nhanh hơn tới ~ 300 lần trong các danh sách dài so với vòng lặp hoặc máy phát điện được tạo bằng tay. Điều này có ý nghĩa - chúng được viết bằng ngôn ngữ bản địa (tức là C), có các chuyên gia tạo ra chúng, xem xét kỹ lưỡng và tối ưu hóa. Họ cũng ít bị lỗi và có nhiều khả năng xử lý các trường hợp cạnh và góc.

Kịch bản kiểm tra

Đặt tất cả các đoạn mã vào câu trả lời này lại với nhau để tạo một tập lệnh sẽ chạy các cách khác nhau để đảo ngược một danh sách được mô tả dưới đây. Nó sẽ có thời gian mỗi phương pháp trong khi chạy nó 100.000 lần. Các kết quả được hiển thị trong phần cuối cùng cho danh sách các mục dài 2, 10 và 1000.

from timeit import timeit
from copy import copy

def time_str_ms(t):
    return '{0:8.2f} ms'.format(t * 1000)

Phương pháp 1: Đảo ngược tại chỗ với obj.reverse ()

Nếu mục tiêu chỉ là đảo ngược thứ tự của các mục trong một danh sách hiện có, mà không cần lặp lại chúng hoặc nhận bản sao để làm việc, hãy sử dụng hàm

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

2. Chạy trực tiếp này trên một đối tượng danh sách và thứ tự của tất cả các mục sẽ được đảo ngược:

Lưu ý rằng những điều sau đây sẽ đảo ngược biến ban đầu được đưa ra, mặc dù nó cũng trả lại danh sách đảo ngược trở lại. tức là bạn có thể tạo một bản sao bằng cách sử dụng đầu ra chức năng này. Thông thường, bạn sẽ không tạo ra một chức năng cho việc này, nhưng tập lệnh thời gian yêu cầu nó.

Chúng tôi kiểm tra hiệu suất của hai cách này - trước tiên chỉ cần đảo ngược danh sách tại chỗ (thay đổi danh sách ban đầu), sau đó sao chép danh sách và đảo ngược nó sau đó để xem đó có phải là cách nhanh nhất để tạo bản sao đảo ngược so với cách khác Phương pháp.

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

Phương pháp 2: Đảo ngược danh sách bằng cách sử dụng các lát def rev_in_place(mylist): mylist.reverse() return mylist def rev_copy_reverse(mylist): a = copy(mylist) a.reverse() return a 3

Phương pháp cắt chỉ mục tích hợp cho phép bạn tạo một bản sao của một phần của bất kỳ đối tượng được lập chỉ mục nào.

• Nó không ảnh hưởng đến đối tượng ban đầu
• Nó xây dựng một danh sách đầy đủ, không phải là một trình lặp

Cú pháp chung là:

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

4. Để khai thác cắt để tạo một danh sách đảo ngược đơn giản, hãy sử dụng:

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

5. Khi để lại một tùy chọn trống, nó sẽ đặt chúng theo mặc định của phần tử đầu tiên và cuối cùng của đối tượng (đảo ngược nếu kích thước bước là âm).

Lập chỉ mục cho phép người ta sử dụng các số âm, được tính từ phần cuối của chỉ mục của đối tượng (tức là -2 là mục thứ hai đến cuối cùng). Khi kích thước bước âm, nó sẽ bắt đầu với mục cuối cùng và chỉ mục ngược bởi số tiền đó.

def rev_slice(mylist):
    a = mylist[::-1]
    return a

Phương pháp 3: Đảo ngược danh sách với hàm def rev_in_place(mylist): mylist.reverse() return mylist def rev_copy_reverse(mylist): a = copy(mylist) a.reverse() return a 6

Có chức năng

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

7:

• Điều này tạo ra một trình lặp chỉ số ngược, không phải là một danh sách. Tuyệt vời nếu bạn đang cho nó ăn vào một vòng lặp để có hiệu suất tốt hơn trong danh sách lớn
• Điều này tạo ra một bản sao và không ảnh hưởng đến đối tượng gốc

Kiểm tra với cả một trình lặp thô và tạo một danh sách từ trình lặp.

def reversed_iterator(mylist):
    a = reversed(mylist)
    return a

def reversed_with_list(mylist):
    a = list(reversed(mylist))
    return a

Phương pháp 4: Danh sách ngược với lập chỉ mục tùy chỉnh/thủ công

Như thời gian cho thấy, việc tạo ra các phương pháp lập chỉ mục của riêng bạn là một ý tưởng tồi. Sử dụng các phương thức tích hợp trừ khi bạn thực sự cần phải làm một cái gì đó tùy chỉnh. Điều này đơn giản có nghĩa là học các phương pháp tích hợp.

Điều đó nói rằng, không có một hình phạt lớn với kích thước danh sách nhỏ hơn, nhưng khi bạn tăng quy mô hình phạt trở nên to lớn. Mã dưới đây có thể được tối ưu hóa, tôi chắc chắn, nhưng nó không thể khớp với các phương thức tích hợp vì chúng được thực hiện trực tiếp bằng ngôn ngữ bản địa.

def rev_manual_pos_gen(mylist):
    max_index = len(mylist) - 1
    return [ mylist[max_index - index] for index in range(len(mylist)) ]

def rev_manual_neg_gen(mylist):
    ## index is 0 to 9, but we need -1 to -10
    return [ mylist[-index-1] for index in range(len(mylist)) ]

def rev_manual_index_loop(mylist):
    a = []
    reverse_index = len(mylist) - 1
    for index in range(len(mylist)):
        a.append(mylist[reverse_index - index])
    return a
    
def rev_manual_loop(mylist):
    a = []
    reverse_index = len(mylist)
    for index, _ in enumerate(mylist):
        reverse_index -= 1
        a.append(mylist[reverse_index])
    return a

Thời gian mỗi phương pháp

Sau đây là phần còn lại của tập lệnh theo thời gian mỗi phương thức đảo ngược. Nó hiển thị đảo ngược tại chỗ với

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

8 và tạo trình lặp

def rev_in_place(mylist):
    mylist.reverse()
    return mylist

def rev_copy_reverse(mylist):
    a = copy(mylist)
    a.reverse()
    return a

6 luôn nhanh nhất, trong khi sử dụng các lát là cách nhanh nhất để tạo bản sao.

Nó cũng chứng tỏ không cố gắng tạo ra một cách tự mình làm điều đó trừ khi bạn phải!

loops_to_test = 100000
number_of_items = 10
list_to_reverse = list(range(number_of_items))
if number_of_items < 15:
    print("a: {}".format(list_to_reverse))
print('Loops: {:,}'.format(loops_to_test))
# List of the functions we want to test with the timer, in print order
fcns = [rev_in_place, reversed_iterator, rev_slice, rev_copy_reverse,
        reversed_with_list, rev_manual_pos_gen, rev_manual_neg_gen,
        rev_manual_index_loop, rev_manual_loop]
max_name_string = max([ len(fcn.__name__) for fcn in fcns ])
for fcn in fcns:
    a = copy(list_to_reverse) # copy to start fresh each loop
    out_str = ' | out = {}'.format(fcn(a)) if number_of_items < 15 else ''
    # Time in ms for the given # of loops on this fcn
    time_str = time_str_ms(timeit(lambda: fcn(a), number=loops_to_test))
    # Get the output string for this function
    fcn_str = '{}(a):'.format(fcn.__name__)
    # Add the correct string length to accommodate the maximum fcn name
    format_str = '{{fx:{}s}} {{time}}{{rev}}'.format(max_name_string + 4)
    print(format_str.format(fx=fcn_str, time=time_str, rev=out_str))

Kết quả thời gian

Kết quả cho thấy tỷ lệ hoạt động tốt nhất với các phương pháp tích hợp phù hợp nhất cho một loại đảo ngược cụ thể. Nói cách khác, khi số phần tử đối tượng tăng lên, các phương thức tích hợp vượt xa các phương thức khác bằng nhiều hơn nữa.

Phương pháp tích hợp trực tiếp đạt được những gì bạn cần làm tốt hơn việc xâu chuỗi mọi thứ lại với nhau. tức là việc cắt lát là tốt nhất nếu bạn cần một bản sao của danh sách đảo ngược - nó nhanh hơn so với việc tạo một danh sách sao tốc độ, vận tốc. Trong khi đó - các phương thức tùy chỉnh có thể mất các đơn đặt hàng dài hơn với danh sách lớn.

Để chia tỷ lệ, với danh sách 1000 mục, cuộc gọi chức năng ____22 mất ~ 30 ms để thiết lập trình lặp, đảo ngược tại chỗ chỉ mất ~ 55 ms, sử dụng phương thức lát cắt mất ~ 210 ms để tạo một bản sao của danh sách đảo ngược đầy đủ, Nhưng phương pháp thủ công nhanh nhất tôi đã thực hiện mất ~ 8400 ms.~8400 ms.

Với 2 mục trong danh sách:

a: [0, 1]
Loops: 100,000
rev_in_place(a):             24.70 ms | out = [1, 0]
reversed_iterator(a):        30.48 ms | out = 
rev_slice(a):                31.65 ms | out = [1, 0]
rev_copy_reverse(a):         63.42 ms | out = [1, 0]
reversed_with_list(a):       48.65 ms | out = [1, 0]
rev_manual_pos_gen(a):       98.94 ms | out = [1, 0]
rev_manual_neg_gen(a):       88.11 ms | out = [1, 0]
rev_manual_index_loop(a):    87.23 ms | out = [1, 0]
rev_manual_loop(a):          79.24 ms | out = [1, 0]

Với 10 mục trong danh sách:

rev_in_place(a):             23.39 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
reversed_iterator(a):        30.23 ms | out = 
rev_slice(a):                36.01 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_copy_reverse(a):         64.67 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
reversed_with_list(a):       50.77 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_pos_gen(a):      162.83 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_neg_gen(a):      167.43 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_index_loop(a):   152.04 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
rev_manual_loop(a):         183.01 ms | out = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Và với 1000 mục trong danh sách:

rev_in_place(a):             56.37 ms
reversed_iterator(a):        30.47 ms
rev_slice(a):               211.42 ms
rev_copy_reverse(a):        295.74 ms
reversed_with_list(a):      418.45 ms
rev_manual_pos_gen(a):     8410.01 ms
rev_manual_neg_gen(a):    11054.84 ms
rev_manual_index_loop(a): 10543.11 ms
rev_manual_loop(a):       15472.66 ms

Làm thế nào để bạn đảo ngược một danh sách trong Stack Python?

Làm thế nào để bạn đảo ngược một danh sách trong danh sách Python?

Làm thế nào để bạn đảo ngược một danh sách trong lập chỉ mục Python?

Làm thế nào để bạn đảo ngược một danh sách mà không cần đảo ngược?