بر عکس کردن یک لیست

فرض کنید میخوایم یک لیستی رو برعکس کنیم
دو تا راهش رو میگم و میخوام ببینم تفاوت این دو توی چی هست ؟
استفاده از رم یا تفاوت در زمان اجرا یا چی ؟

fruits = ['banana', 'orange', 'mango', 'lemon']

fruits[::-1]

fruits.reverse()

@Alimehr

پیچیدگی زمان روش اول O(n) هست اما دومی O(1)، در نتیجه روش دوم سریعتر هست، همچنین روش اول چون یک لیست جدید در حافظه ذخیره میکنه استفاده از رم هم افزایش پیدا میکنه. داخل لینک زیر میتونید اسکریپت تستش رو ببینید :
https://gist.github.com/bistcuite/3fdde61e63c01363f3e9a9bde742367f

2 پسندیده

ولی چیزی که من اینجا میبینم روش اول سریع تر هست و فکر نمیکنم لیست جدیدی ذخیره کنه !!!
python reverse

کد رو تغییر دادم و دوباره تست کردم. داخل لیست های بزرگ، reverse() پرفرمنس خیلی بهتری نسبت به اسلایس داره اما داخل لیست های کوچک بعضا اسلایس سریعتر هست :

from timeit import timeit

my_list = list(range(10000))

print("Reverse benchmark in a big list :")
print("reverse_slice: ",timeit(lambda: my_list[::-1],number=10000))
print("reverse_in_place: ",timeit(lambda: my_list.reverse(),number=10000))

my_list2 = [1,2,3,4]

print("\nReverse benchmark in a small list:")
print("reverse_slice: ",timeit(lambda: my_list2[::-1],number=10000))
print("reverse_in_place: ",timeit(lambda: my_list2.reverse(),number=10000))

نتیجه :

Reverse benchmark in a big list :
reverse_slice:  0.931406487
reverse_in_place:  0.15571122599999998

Reverse benchmark in a small list:
reverse_slice:  0.0029031129999999017
reverse_in_place:  0.003123278000000118

در ضمن داخل لینکی که فرستادید، برای reverse، یکبار ol رو دوباره به لیست تبدیل کرده و برابر nl قرار داده، اما کار باید خارج timeit انجام بشه(لینک).

2 پسندیده

میتونید در مورد O(1) یا O(n) یه توضیح مختصر بدید
یا لینکی در موردش قرار بدید ؟ لطفا

فکر می کنم در مورد یه مسأله اینجا اشتباه شده. reverse برای space فقط O(1) هست ولی برای زمان O(n) هست.

اینجا می تونین ببینین:

اما در هر دو حالت memcpy اجرا می شه و یه حجمی از حافظه کپی می شه.

این رو هم اضافه کنم که این کد مربوط به به برعکس کردن آرایه هست اگر پیاده سازی لیست در پایتون به صورت یه doubly linked list باشه پروسه برعکس کردن هم برای زمان هم برای فضا O(1) خواهد بود. ولی باید دید که چه جوری لیست رو پیاده کردن

2 پسندیده

ممنون، اشتباهاً پیچیدگی فضا رو برای زمان بکار بردم.

اما در مورد کدی که فرستادید، پیاده سازی reverse برای لیست متفاوت هست و دارای پیچیدگی O(1) از نظر space هست :
https://github.com/python/cpython/blob/8a6af5a34642f5564220eb50d72caada8f17fc78/Objects/listobject.c#L1062

اما برای slice ها، میاد داخل حافظه لیست جدید ذخیره میکنه و طبیعتا پیچیدگی‌اش O(n) میشه :

https://github.com/python/cpython/blob/8a6af5a34642f5564220eb50d72caada8f17fc78/Objects/listobject.c#L628

1 پسندیده

Big-O Notation: A Simple Explanation with Examples

1 پسندیده

reversed هم داریم

1 پسندیده