متداول‌ترین ساختارهای داده در پایتون

امیرحسین بیگدلو 4 ماه قبل

ساختارهای داده سازه‌های اساسی هستند که برنامه های خود را بر اساس آنها می سازید. هر ساختار داده روش خاصی را برای سازماندهی داده ها ارائه می دهد تا بسته به مورد استفاده شما به طور موثر به آنها دسترسی داشته باشید. پایتون با مجموعه گسترده ای از ساختارهای داده در کتابخانه استاندارد خود عرضه می شود.

 

با این حال، قرارداد نام‌گذاری پایتون همان سطح وضوحی را که در زبان‌های دیگر خواهید یافت، ارائه نمی‌کند. در جاوا، یک لیست فقط یک لیست نیست، بلکه یک LinkedList یا یک ArrayList است. در پایتون اینطور نیست. حتی توسعه دهندگان باتجربه پایتون گاهی اوقات تعجب می کنند که آیا نوع لیست داخلی به عنوان یک لیست پیوندی پیاده سازی شده است یا یک آرایه پویا.

 

دوره پیشنهادی: دوره آموزش الگوریتم‌نویسی در پایتون

 

 #  دیکشنری‌ها، mapها و جداول هش

در پایتون، دیکشنری ها (یا به اختصار dicts) یک ساختار داده مرکزی هستند. Dict ها تعداد دلخواه شی را ذخیره می کنند که هر کدام با یک کلید منحصر به فرد شناسایی می شوند.

 

دیکشنری ها اغلب maps، hashmaps، lookup tables یا associative arrays نیز نامیده می شوند. آنها امکان جستجوی کارآمد، درج و حذف هر شی مرتبط با یک کلید داده شده را فراهم می کنند.

 

دفترچه تلفن یک مثال مناسب در دنیای واقعی برای اشیاء دیکشنری هستند. آنها به شما این امکان را می دهند که به سرعت اطلاعات (شماره تلفن) مرتبط با یک کلید داده شده (نام یک شخص) را بازیابی کنید. به جای اینکه مجبور باشید برای پیدا کردن شماره شخصی یک دفترچه تلفن را از جلو به عقب بخوانید، می توانید کمابیش مستقیماً به یک نام بروید و اطلاعات مرتبط را جستجو کنید.

 

وقتی صحبت از نحوه سازماندهی اطلاعات برای امکان جستجوی سریع می شود، این قیاس تا حدودی از بین می رود. اما ویژگی های عملکردی اساسی وجود دارد. دیکشنری ها به شما این امکان را می دهند که به سرعت اطلاعات مرتبط با یک کلید مشخص را پیدا کنید.

 

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

 

ویدیو پیشنهادی: ویدیو آشنایی با dictionary comprehensions در پایتون

 

 +  dict: دیکشنری آماده به کار شما

از آنجایی که دیکشنری ها بسیار مهم هستند، پایتون دارای یک پیاده سازی دیکشنری قوی است که مستقیماً در زبان اصلی ساخته شده است: نوع داده dict.

 

پایتون همچنین مقداری سینتکس مفید برای کار با دیکشنری در برنامه های شما ارائه می دهد. به عنوان مثال، نحو عبارت آکولاد دیکشنری ({ }) و dictionary comprehension به شما این امکان را می دهد که به راحتی اشیاء دیکشنری جدید را تعریف کنید:

>>> phonebook = {
...     "bob": 7387,
...     "alice": 3719,
...     "jack": 7052,
... }

>>> squares = {x: x * x for x in range(6)}

>>> phonebook["alice"]
3719

>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

 

محدودیت هایی وجود دارد که در آن اشیاء می توانند به عنوان کلیدهای معتبر استفاده شوند.

 

دیکشنری های پایتون با کلیدهایی که می توانند از هر نوع هش پذیری باشند ایندکس می شوند. یک شی قابل هش دارای مقدار هش است که هرگز در طول عمر خود تغییر نمی کند (به __hash__ مراجعه کنید)، و می توان آن را با اشیاء دیگر مقایسه کرد (به __eq__ مراجعه کنید). اشیاء قابل درهم سازی(Hashable) که به صورت مساوی با هم مقایسه می شوند باید مقدار هش یکسانی داشته باشند.

 

داده‌های غیرقابل تغییر مانند رشته ها و اعداد، قابل هش هستند و به خوبی به عنوان کلیدهای دیکشنری کار می کنند. همچنین می‌توانید از اشیاء تاپل به‌عنوان کلیدهای دیکشنری استفاده کنید، به شرطی که خود تاپل فقط انواع قابل هش داشته باشند.

 

برای بیشتر موارد استفاده، پیاده‌سازی دیکشنری داخلی پایتون هر کاری را که نیاز دارید انجام می‌دهد. دیکشنری ها بسیار بهینه شده اند و زیربنای بسیاری از بخش های زبان هستند. به عنوان مثال، class variables به صورت داخلی در دیکشنری ها ذخیره می شوند.

 

دیکشنری های پایتون مبتنی بر پیاده سازی جدول هش به خوبی آزمایش شده و تنظیم شده هستند که ویژگی های عملکردی را که انتظار دارید ارائه می کند: پیچیدگی زمانی O(1) برای عملیات جستجو، درج، به روز رسانی و حذف در حالت متوسط.

 

دلیل کمی برای عدم استفاده از اجرای استاندارد dict موجود در پایتون وجود دارد. با این حال، پیاده‌سازی‌های تخصصی دیکشنری شخص ثالث، مانند  skip lists یا B-tree–based وجود دارد.

 

علاوه بر اشیاء dict ساده، کتابخانه استاندارد پایتون همچنین شامل تعدادی پیاده سازی دیکشنری تخصصی است. این دیکشنری‌های تخصصی همگی بر اساس کلاس دیکشنری داخلی هستند (و ویژگی‌های عملکردی آن را به اشتراک می‌گذارند) اما برخی ویژگی‌های راحتی اضافی را نیز شامل می‌شوند.

 

بیایید نگاهی به آنها بیندازیم.

 

مقاله پیشنهادی: معرفی لیست‌های پیوندی در پایتون

 

 +  collections.OrderedDict: حفظ ترتیب ورود کلیدها

پایتون شامل یک زیرکلاس dict تخصصی است که ترتیب درج کلیدهای اضافه شده به آن را به خاطر می آورد: collections.OrderedDict.

 

در حالی که نمونه‌های استاندارد dict ترتیب درج کلیدها را در CPython 3.6 و بالاتر حفظ می‌کنند، این به سادگی یک اثر جانبی اجرای CPython بود و تا قبل از Python 3.7 در مشخصات زبان تعریف نشده بود. بنابراین، اگر ترتیب کلید برای کارکرد الگوریتم شما مهم است، بهتر است با استفاده از کلاس OrderedDict این موضوع را به وضوح بیان کنید:

>>> import collections
>>> d = collections.OrderedDict(one=1, two=2, three=3)

>>> d
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> d["four"] = 4
>>> d
OrderedDict([('one', 1), ('two', 2),
             ('three', 3), ('four', 4)])

>>> d.keys()
odict_keys(['one', 'two', 'three', 'four'])

 

تا قبل از Python 3.8، نمی‌توانستید با استفاده از reversed() آیتم‌های دیکشنری را به ترتیب معکوس تکرار کنید. فقط نمونه های OrderedDict این قابلیت را ارائه می کردند. حتی در پایتون 3.8، اشیاء dict و OrderedDict دقیقاً یکسان نیستند. نمونه های OrderedDict دارای یک متد .move_to_end() هستند که در نمونه dict ساده در دسترس نیست، و همچنین یک متد .popitem() قابل تنظیم تر از نمونه های یک dict ساده است.

 

مقاله پیشنهادی: یونیکد و رمزگذاری کاراکتر در پایتون

 

 +  collections.defaultdict: برگشت مقدار پیشفرض برای کلیدهای ناموجود

کلاس defaultdict یکی دیگر از زیر کلاس های دیکشری است که در سازنده خود یک callable را می پذیرد که اگر کلید درخواستی یافت نشد از مقدار بازگشتی آن استفاده می شود.

 

این می‌تواند در تایپ کردن شما صرفه‌جویی کند و در مقایسه با استفاده از get() یا گرفتن استثنای KeyError در دیکشنری‌های معمولی، اهداف شما را واضح‌تر کند:

>>> from collections import defaultdict
>>> dd = defaultdict(list)

>>> # Accessing a missing key creates it and
>>> # initializes it using the default factory,
>>> # i.e. list() in this example:
>>> dd["dogs"].append("Rufus")
>>> dd["dogs"].append("Kathrin")
>>> dd["dogs"].append("Mr Sniffles")

>>> dd["dogs"]
['Rufus', 'Kathrin', 'Mr Sniffles']

 

 

 +  collections.ChainMap: جستجوی چند دیکشنری در یک واحد

ساختار داده collections.ChainMap چندین دیکشنری را در یک واحد گروه بندی می کند. جستجوگرها بخش‌های زیرین را یکی یکی جستجو می کنند تا زمانی که یک کلید پیدا شود. درج‌ها، به‌روزرسانی‌ها و حذف‌ها فقط بر اولین بخش اضافه شده به زنجیره تأثیر می‌گذارند:

>>> from collections import ChainMap
>>> dict1 = {"one": 1, "two": 2}
>>> dict2 = {"three": 3, "four": 4}
>>> chain = ChainMap(dict1, dict2)

>>> chain
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})

>>> # ChainMap searches each collection in the chain
>>> # from left to right until it finds the key (or fails):
>>> chain["three"]
3
>>> chain["one"]
1
>>> chain["missing"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'missing'

 

مقاله پیشنهادی: معرفی کلمات کلیدی در پایتون

 

 +  types.MappingProxyType: یک پوشش برای ساخت دیکشنری‌های فقط خواندنی

MappingProxyType یک بسته بندی در اطراف یک دیکشنری استاندارد است که یک نمای فقط خواندنی در داده های دیکشنری پیچیده ارائه می دهد. این کلاس در پایتون 3.3 اضافه شده است و می توان از آن برای ایجاد نسخه های پروکسی تغییرناپذیر دیکشنری ها استفاده کرد.

 

MappingProxyType می تواند مفید باشد، به عنوان مثال، اگر بخواهید یک دیکشنری حاوی حالت داخلی را از یک کلاس یا ماژول بازگردانید و در عین حال دسترسی نوشتن به این شی را منع کنید. استفاده از MappingProxyType به شما این امکان را می دهد که این محدودیت ها را بدون نیاز به ایجاد یک کپی کامل از دیکشنری اعمال کنید:

>>> from types import MappingProxyType
>>> writable = {"one": 1, "two": 2}
>>> read_only = MappingProxyType(writable)

>>> # The proxy is read-only:
>>> read_only["one"]
1
>>> read_only["one"] = 23
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment

>>> # Updates to the original are reflected in the proxy:
>>> writable["one"] = 42
>>> read_only
mappingproxy({'one': 42, 'two': 2})

 

 

 +  نتیجه گیری: دیکشنری‌ها در پایتون

تمام پیاده‌سازی‌های دیکشنری پایتون که در این آموزش فهرست شده‌اند، پیاده‌سازی‌های معتبری هستند که در کتابخانه استاندارد پایتون ساخته شده‌اند.

 

اگر به دنبال یک توصیه کلی در مورد نوع mapping برای استفاده در برنامه های خود هستید، من به نوع داده dict داخلی اشاره می کنم. این یک پیاده سازی جدول هش همه کاره و بهینه است که مستقیماً در زبان اصلی ساخته شده است.

 

توصیه می‌کنم تنها در صورتی از یکی از دیگر انواع داده‌های فهرست‌شده در اینجا استفاده کنید که الزامات خاصی دارید که فراتر از آنچه توسط dict ارائه شده است.

 

همه پیاده‌سازی‌ها گزینه‌های معتبری هستند، اما اگر کد شما در بیشتر مواقع به دیکشنری‌های استاندارد پایتون متکی باشد، واضح‌تر و راحت‌تر نگهداری می‌شود.

 

مقاله پیشنهادی: اجرای برنامه‌های فلسک با داکر

 

 #  نوع داده آرایه(array)

آرایه یک ساختار داده بنیادی است که در اکثر زبان های برنامه نویسی موجود است و طیف وسیعی از کاربردها در الگوریتم های مختلف دارد.

 

در این بخش، به پیاده‌سازی آرایه‌ها در پایتون نگاهی می‌اندازید که فقط از ویژگی‌های زبان اصلی یا عملکرد موجود در کتابخانه استاندارد پایتون استفاده می‌کنند. شما نقاط قوت و ضعف هر رویکرد را خواهید دید تا بتوانید تصمیم بگیرید که کدام پیاده سازی برای مورد استفاده شما مناسب است.

 

اما قبل از اینکه وارد بحث شویم، ابتدا برخی از اصول اولیه را پوشش می دهیم. آرایه ها چگونه کار می کنند و چه کاربردی دارند؟ آرایه‌ها از رکوردهای داده با اندازه ثابت تشکیل شده‌اند که به هر عنصر اجازه می‌دهد تا بر اساس ایندکس خود به‌طور مؤثری قرار گیرد:

ساختارهای داده آرایه در پایتون

 

از آنجایی که آرایه‌ها اطلاعات را در بلوک‌های مجاور حافظه ذخیره می‌کنند، به عنوان ساختارهای داده پیوسته در نظر گرفته می‌شوند (به عنوان مثال، برخلاف ساختارهای داده مرتبط مانند لیست‌های پیوندی).

 

یک قیاس در دنیای واقعی برای ساختار داده آرایه یک پارکینگ است. شما می توانید به پارکینگ به عنوان یک کل نگاه کنید و آن را به عنوان یک شی واحد در نظر بگیرید، اما در داخل محوطه پارکینگ هایی وجود دارد که با یک عدد منحصر به فرد نمایه شده اند. مکان‌های پارکینگ کانتینری برای وسایل نقلیه هستند - هر مکان پارک می‌تواند خالی باشد یا ماشین، موتور سیکلت یا وسیله نقلیه دیگری روی آن پارک شده باشد.

 

اما همه پارکینگ ها یکسان نیستند. برخی از پارکینگ ها ممکن است فقط به یک نوع وسیله نقلیه محدود شوند. به عنوان مثال، یک پارکینگ موتور اجازه نمی دهد دوچرخه در آن پارک شود. یک پارکینگ محدود مربوط به یک ساختار داده آرایه تایپ شده است که فقط به عناصری اجازه می دهد که نوع داده مشابهی در آنها ذخیره شده باشد.

 

از نظر عملکرد، جستجوی یک عنصر موجود در یک آرایه با توجه به index عنصر بسیار سریع است. اجرای آرایه مناسب زمان دسترسی O(1) ثابت را برای این مورد تضمین می کند.

 

پایتون شامل چندین ساختار داده آرایه مانند در کتابخانه استاندارد خود است که هر کدام دارای ویژگی های کمی متفاوت هستند. بیا یک نگاهی بیندازیم.

 

مقاله پیشنهادی: متد append پایتون

 

 +  list: یک آرایه قابل تغییر پویا

لیست ها بخشی از زبان اصلی پایتون هستند. علیرغم نام آنها، لیست های پایتون به عنوان آرایه های پویا در پشت صحنه پیاده سازی می شوند.

 

این بدان معنی است که یک لیست اجازه می دهد تا عناصر اضافه یا حذف شوند، و لیست به طور خودکار ذخیره پشتیبان که این عناصر را با اختصاص یا آزاد کردن حافظه تنظیم می کند، تنظیم می کند.

 

لیست‌های پایتون می‌توانند عناصر دلخواه را در خود جای دهند—همه چیز در پایتون یک شی است، از جمله توابع. بنابراین، می‌توانید انواع مختلفی از انواع داده‌ها را ترکیب و مطابقت دهید و همه آنها را در یک لیست واحد ذخیره کنید.

 

این می تواند یک ویژگی قدرتمند باشد، اما نقطه ضعف این است که پشتیبانی از چندین نوع داده به طور همزمان به این معنی است که داده ها به طور کلی کمتر فشرده هستند. در نتیجه کل ساختار فضای بیشتری را اشغال می کند:

>>> arr = ["one", "two", "three"]
>>> arr[0]
'one'

>>> # Lists have a nice repr:
>>> arr
['one', 'two', 'three']

>>> # Lists are mutable:
>>> arr[1] = "hello"
>>> arr
['one', 'hello', 'three']

>>> del arr[1]
>>> arr
['one', 'three']

>>> # Lists can hold arbitrary data types:
>>> arr.append(23)
>>> arr
['one', 'three', 23]

 

ویدیو مرتبط: توضیح tuple در پایتون

 

 +  tuple: کانتینرهای تغییر ناپذیر

درست مانند لیست ها، تاپل ها بخشی از زبان اصلی پایتون هستند. با این حال، بر خلاف لیست ها، اشیاء تاپل پایتون تغییرناپذیر هستند. این بدان معنی است که عناصر را نمی توان به صورت پویا اضافه یا حذف کرد - همه عناصر یک تاپل باید در زمان ایجاد تعریف شوند.

 

تاپل ها ساختار داده دیگری هستند که می توانند عناصری از انواع داده دلخواه را در خود جای دهند. داشتن این انعطاف‌پذیری قدرتمند است، اما باز هم به این معنی است که داده‌ها نسبت به آرایه‌های تایپی فشرده‌تر هستند:

>>> arr = ("one", "two", "three")
>>> arr[0]
'one'

>>> # Tuples have a nice repr:
>>> arr
('one', 'two', 'three')

>>> # Tuples are immutable:
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

>>> del arr[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object doesn't support item deletion

>>> # Tuples can hold arbitrary data types:
>>> # (Adding elements creates a copy of the tuple)
>>> arr + (23,)
('one', 'two', 'three', 23)

 

 

 +  array.array: آرایه‌های تایپی پایه

ماژول array پایتون ذخیره سازی فضای کارآمد انواع داده های پایه به سبک C مانند بایت ها، اعداد صحیح 32 بیتی، اعداد ممیز اعشاری و غیره را فراهم می کند.

 

آرایه های ایجاد شده با کلاس array.array قابل تغییر هستند و به جز یک تفاوت مهم مشابه لیست ها رفتار می کنند: آنها آرایه های تایپ شده محدود به یک نوع داده واحد هستند.

 

به دلیل این محدودیت، اشیاء array.array با عناصر زیاد نسبت به لیست ها و تاپل ها فضا کارآمدتر هستند. عناصر ذخیره شده در آنها به خوبی بسته بندی شده اند، و این می تواند مفید باشد اگر شما نیاز به ذخیره بسیاری از عناصر از یک نوع دارید.

 

همچنین، آرایه‌ها از بسیاری از متدهای مشابه لیست‌های معمولی پشتیبانی می‌کنند و ممکن است بتوانید از آنها به عنوان جایگزینی کشویی بدون نیاز به تغییرات دیگری در کد برنامه خود استفاده کنید.

>>> import array
>>> arr = array.array("f", (1.0, 1.5, 2.0, 2.5))
>>> arr[1]
1.5

>>> # Arrays have a nice repr:
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

>>> # Arrays are mutable:
>>> arr[1] = 23.0
>>> arr
array('f', [1.0, 23.0, 2.0, 2.5])

>>> del arr[1]
>>> arr
array('f', [1.0, 2.0, 2.5])

>>> arr.append(42.0)
>>> arr
array('f', [1.0, 2.0, 2.5, 42.0])

>>> # Arrays are "typed":
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

 

ویدیو مرتبط: ویدیو آموزش رشته ها در پایتون

 

 +  str: آرایه‌ای تغییر ناپذیر از کاراکترهای یونیکد

پایتون 3.x از اشیاء str برای ذخیره داده های متنی به عنوان دنباله های تغییرناپذیر کاراکترهای یونیکد استفاده می کند. از نظر عملی، این بدان معناست که یک str آرایه ای غیرقابل تغییر از کاراکترها است. به اندازه کافی عجیب، همچنین یک ساختار داده بازگشتی است - هر کاراکتر در یک رشته، خود یک شی str به طول 1 است.

 

اشیاء رشته ای در فضا کارآمد هستند، زیرا آنها کاملاً بسته بندی شده اند و در یک نوع داده واحد تخصص دارند. اگر متن یونیکد را ذخیره می کنید، باید از یک رشته استفاده کنید.

 

از آنجایی که رشته ها در پایتون تغییر ناپذیر هستند، تغییر رشته مستلزم ایجاد یک کپی تغییر یافته است. نزدیکترین معادل به یک رشته قابل تغییر، ذخیره کاراکترهای جداگانه در یک لیست است:

>>> arr = "abcd"
>>> arr[1]
'b'

>>> arr
'abcd'

>>> # Strings are immutable:
>>> arr[1] = "e"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

>>> del arr[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object doesn't support item deletion

>>> # Strings can be unpacked into a list to
>>> # get a mutable representation:
>>> list("abcd")
['a', 'b', 'c', 'd']
>>> "".join(list("abcd"))
'abcd'

>>> # Strings are recursive data structures:
>>> type("abc")
"<class 'str'>"
>>> type("abc"[0])
"<class 'str'>"

 

 

 +  bytes: آرایه‌ای تغییر ناپذیر از یک بایت

اشیاء بایت دنباله‌های تغییرناپذیر بایت‌های منفرد یا اعداد صحیح در محدوده 0 تا 255 هستند.

 

مانند رشته ها، بایت ها نحو تحت اللفظی خود را برای ایجاد اشیاء دارند و در فضا کارآمد هستند. اشیاء بایت تغییرناپذیر هستند، اما برخلاف رشته‌ها، یک نوع داده آرایه بایت قابل تغییر اختصاصی وجود دارد که بایت آرایه نامیده می‌شود که می‌توان آن‌ها را در آن باز کرد:

>>> arr = bytes((0, 1, 2, 3))
>>> arr[1]
1

>>> # Bytes literals have their own syntax:
>>> arr
b'\x00\x01\x02\x03'
>>> arr = b"\x00\x01\x02\x03"

>>> # Only valid `bytes` are allowed:
>>> bytes((0, 300))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: bytes must be in range(0, 256)

>>> # Bytes are immutable:
>>> arr[1] = 23
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'bytes' object does not support item assignment

>>> del arr[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'bytes' object doesn't support item deletion

 

دوره پیشنهادی: دوره آموزش GraphQL در پایتون

 

 +  bytearray: آرایه‌ای تغییرپذیر از یک بایت

نوع bytearray یک دنباله قابل تغییر از اعداد صحیح در محدوده 0 تا 255 است. شی bytearray ارتباط نزدیکی با شی bytes دارد، با تفاوت اصلی این است که یک بایت آرایه را می توان آزادانه تغییر داد—شما می توانید عناصر را بازنویسی کنید، عناصر موجود را حذف کنید. ، یا موارد جدید اضافه کنید. شی بایت آرایه بر این اساس رشد و کوچک می شود.

 

یک bytearray را می توان دوباره به اشیاء bytes تغییرناپذیر تبدیل کرد، اما این شامل کپی کردن کامل داده های ذخیره شده است - یک عملیات کند که زمان O(n) را می گیرد:

>>> arr = bytearray((0, 1, 2, 3))
>>> arr[1]
1

>>> # The bytearray repr:
>>> arr
bytearray(b'\x00\x01\x02\x03')

>>> # Bytearrays are mutable:
>>> arr[1] = 23
>>> arr
bytearray(b'\x00\x17\x02\x03')

>>> arr[1]
23

>>> # Bytearrays can grow and shrink in size:
>>> del arr[1]
>>> arr
bytearray(b'\x00\x02\x03')

>>> arr.append(42)
>>> arr
bytearray(b'\x00\x02\x03*')

>>> # Bytearrays can only hold `bytes`
>>> # (integers in the range 0 <= x <= 255)
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer

>>> arr[1] = 300
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: byte must be in range(0, 256)

>>> # Bytearrays can be converted back into bytes objects:
>>> # (This will copy the data)
>>> bytes(arr)
b'\x00\x02\x03*'

 

دوره پیشنهادی: دوره آموزش Descriptors در پایتون

 

 +  نتیجه گیری: آرایه‌ در پایتون

تعدادی ساختار داده داخلی وجود دارد که می توانید هنگام پیاده سازی آرایه ها در پایتون یکی از آنها را انتخاب کنید. در این بخش، شما بر ویژگی‌های زبان اصلی و ساختارهای داده موجود در کتابخانه استاندارد تمرکز کرده‌اید.

 

اگر مایلید فراتر از کتابخانه استاندارد پایتون بروید، بسته های شخص ثالث مانند NumPy و pandas طیف گسترده ای از پیاده سازی آرایه های سریع را برای محاسبات علمی و علم داده ارائه می دهند.

 

اگر می خواهید خود را به ساختارهای داده آرایه موجود در پایتون محدود کنید، در اینجا چند دستورالعمل وجود دارد:

 

  • اگر نیاز به ذخیره اشیاء دلخواه، به طور بالقوه با انواع داده‌های مختلط دارید، بسته به اینکه ساختار داده غیرقابل تغییری می‌خواهید یا نه، از یک لیست یا یک تاپل استفاده کنید.
  • اگر داده‌های عددی (اعداد صحیح یا ممیز اعشاری) دارید و بسته‌بندی و عملکرد بسیار مهم است، array.array را امتحان کنید.
  • اگر داده های متنی دارید که به صورت کاراکترهای یونیکد نمایش داده می شوند، از str داخلی پایتون استفاده کنید. اگر به یک ساختار داده رشته مانند نیاز دارید، از list کاراکترها استفاده کنید.
  • اگر می‌خواهید یک بلوک به‌هم پیوسته از بایت‌ها را ذخیره کنید از bytes استفاده کنید، اگر به ساختار داده‌ای قابل تغییر نیاز دارید، از نوع بایت‌های تغییرناپذیر یا bytearray استفاده کنید.

 

در بیشتر موارد، من دوست دارم با یک لیست ساده شروع کنم. فقط در صورتی که عملکرد یا فضای ذخیره سازی مشکلی ایجاد شود، بعداً نوع داده را تغییر میدهم. در بیشتر مواقع، استفاده از یک ساختار داده آرایه همه منظوره مانند لیست، سریع ترین راه توسعه و بیشترین راحتی برنامه نویسی را به شما می دهد.

 

 

 #  رکوردها، ساختارها و آبجکت‌های انتقال داده

در مقایسه با آرایه ها، ساختارهای داده رکورد(record) تعداد ثابتی از فیلدها را ارائه می دهند. هر فیلد می تواند یک نام داشته باشد و همچنین ممکن است نوع متفاوتی داشته باشد.

 

در این بخش، نحوه پیاده‌سازی رکوردها، ساختارها(struct) و اشیاء داده قدیمی را در پایتون با استفاده از انواع داده‌های داخلی و کلاس‌های کتابخانه استاندارد خواهید دید.

 

پایتون چندین نوع داده را ارائه می دهد که می توانید از آنها برای پیاده سازی رکوردها، ساختارها و اشیاء انتقال داده(data transfer objects) استفاده کنید. در این بخش، نگاهی سریع به هر پیاده سازی و ویژگی های منحصر به فرد آن خواهید داشت. در پایان، یک خلاصه و یک راهنمای تصمیم گیری پیدا خواهید کرد که به شما در انتخاب خود کمک می کند.

 

ویدیو مرتبط: ویدیو آموزش متدهای hasattr, getattr, setattr, delattr در پایتون

 

 +  dict: نوع داده ساده

همانطور که قبلا ذکر شد، دیکشنری های پایتون تعداد دلخواه شی را ذخیره می کنند که هر کدام با یک کلید منحصر به فرد شناسایی می شوند. دیکشنری ها اغلب mapها یا آرایه های انجمنی نیز نامیده می شوند و امکان جستجو، درج و حذف هر شی مرتبط با یک کلید مشخص را فراهم می کنند.

 

استفاده از دیکشنری ها به عنوان یک نوع داده رکورد یا شی داده در پایتون امکان پذیر است. ایجاد دیکشنری در پایتون آسان است، زیرا آنها سینتکس خاص خود را در زبان دارند. نحو دیکشنری مختصر و برای تایپ بسیار راحت است.

 

اشیاء داده ایجاد شده با استفاده از دیکشنری قابل تغییر هستند و محافظت کمی در برابر نام فیلدهای غلط املایی وجود دارد زیرا فیلدها می توانند آزادانه در هر زمان اضافه و حذف شوند. هر دوی این ویژگی‌ها می‌توانند باگ‌های شگفت‌انگیزی را ایجاد کنند، و همیشه بین راحتی و انعطاف‌پذیری خطا، معاوضه‌ای وجود دارد:

>>> car1 = {
...     "color": "red",
...     "mileage": 3812.4,
...     "automatic": True,
... }
>>> car2 = {
...     "color": "blue",
...     "mileage": 40231,
...     "automatic": False,
... }

>>> # Dicts have a nice repr:
>>> car2
{'color': 'blue', 'automatic': False, 'mileage': 40231}

>>> # Get mileage:
>>> car2["mileage"]
40231

>>> # Dicts are mutable:
>>> car2["mileage"] = 12
>>> car2["windshield"] = "broken"
>>> car2
{'windshield': 'broken', 'color': 'blue',
 'automatic': False, 'mileage': 12}

>>> # No protection against wrong field names,
>>> # or missing/extra fields:
>>> car3 = {
...     "colr": "green",
...     "automatic": False,
...     "windshield": "broken",
... }

 

ویدیو مرتبط: ویدیو آموزش فانکشن های any و all در پایتون

 

 +  tuple: یک گروه تغییرناپذیر از آبجکت‌ها

تاپل های پایتون یک ساختار داده ساده برای گروه بندی اشیاء دلخواه هستند. تاپل ها تغییر ناپذیر هستند - پس از ایجاد نمی توان آنها را تغییر داد.

 

از نظر عملکرد، تاپل ها نسبت به لیست های موجود در CPython کمی حافظه کمتری اشغال می کنند، و همچنین سریعتر ساخته می شوند.

 

همانطور که در جداسازی بایت کد زیر می بینید، ساختن یک ثابت تاپلی به یک اپکد LOAD_CONST نیاز دارد، در حالی که ساخت یک شی فهرست با همان محتویات به چندین عملیات دیگر نیاز دارد:

>>> import dis
>>> dis.dis(compile("(23, 'a', 'b', 'c')", "", "eval"))
      0 LOAD_CONST           4 ((23, "a", "b", "c"))
      3 RETURN_VALUE

>>> dis.dis(compile("[23, 'a', 'b', 'c']", "", "eval"))
      0 LOAD_CONST           0 (23)
      3 LOAD_CONST           1 ('a')
      6 LOAD_CONST           2 ('b')
      9 LOAD_CONST           3 ('c')
     12 BUILD_LIST           4
     15 RETURN_VALUE

 

با این حال، شما نباید روی این تفاوت ها تاکید زیادی داشته باشید. در عمل، تفاوت عملکرد اغلب ناچیز خواهد بود، و تلاش برای حذف عملکرد اضافی از یک برنامه با تغییر از لیست به تاپل، احتمالاً رویکرد اشتباهی خواهد بود.

 

یک نقطه ضعف بالقوه تاپل های ساده این است که داده هایی که در آنها ذخیره می کنید تنها با دسترسی به آنها از طریق ایندکس‌های اعداد صحیح قابل استخراج است. شما نمی توانید نامی برای خصوصیات فردی که در یک تاپل ذخیره شده اند بدهید. این می تواند بر خوانایی کد تأثیر بگذارد.

 

همچنین، یک تاپل همیشه یک ساختار Ad-hoc است: اطمینان از اینکه دو تاپل دارای تعداد یکسانی از فیلدها و ویژگی های یکسان ذخیره شده در آنها هستند، دشوار است.

 

این باعث می‌شود که به راحتی بتوان باگ‌های اشتباه را معرفی کرد، مانند اختلاط ترتیب میدانی. بنابراین، توصیه می کنم تعداد فیلدهای ذخیره شده در یک تاپل را تا حد امکان کم نگه دارید:

>>> # Fields: color, mileage, automatic
>>> car1 = ("red", 3812.4, True)
>>> car2 = ("blue", 40231.0, False)

>>> # Tuple instances have a nice repr:
>>> car1
('red', 3812.4, True)
>>> car2
('blue', 40231.0, False)

>>> # Get mileage:
>>> car2[1]
40231.0

>>> # Tuples are immutable:
>>> car2[1] = 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

>>> # No protection against missing or extra fields
>>> # or a wrong order:
>>> car3 = (3431.5, "green", True, "silver")

 

ویدیو پیشنهادی: ویدیو آموزش ماژول sys در پایتون

 

 +  ساخت کلاس سفارشی: کار بیشتر، کنترل بیشتر

کلاس ها به شما امکان می دهند طرح های قابل استفاده مجدد را برای اشیاء داده تعریف کنید تا اطمینان حاصل کنید که هر شی مجموعه ای از فیلدها را ارائه می دهد.

 

استفاده از کلاس‌های پایتون معمولی به‌عنوان انواع داده‌های رکورد امکان‌پذیر است، اما برای دستیابی به ویژگی‌های راحتی سایر پیاده‌سازی‌ها نیز به کار دستی نیاز است. به عنوان مثال، افزودن فیلدهای جدید به سازنده __init__ پیچیده است و زمان می برد.

 

همچنین، نمایش رشته پیش‌فرض برای اشیاء نمونه‌سازی شده از کلاس‌های سفارشی چندان مفید نیست. برای رفع آن، ممکن است مجبور شوید متد __repr__ خود را اضافه کنید، که معمولاً کاملاً پرمخاطب است و باید هر بار که یک فیلد جدید اضافه می‌کنید، به‌روزرسانی شود.

 

فیلدهای ذخیره شده در کلاس ها قابل تغییر هستند و فیلدهای جدید را می توان آزادانه اضافه کرد که ممکن است دوست داشته باشید یا نخواهید. امکان کنترل دسترسی بیشتر و ایجاد فیلدهای فقط خواندنی با استفاده از دکوراتور  @property وجود دارد، اما یک بار دیگر، این نیاز به نوشتن کد چسب بیشتری دارد.

 

هر زمان که بخواهید منطق و رفتار تجاری را با استفاده از متدها به اشیاء رکورد خود اضافه کنید، نوشتن یک کلاس سفارشی یک گزینه عالی است. با این حال، این بدان معنی است که این اشیاء از نظر فنی دیگر اشیاء داده ساده نیستند:

>>> class Car:
...     def __init__(self, color, mileage, automatic):
...         self.color = color
...         self.mileage = mileage
...         self.automatic = automatic
...
>>> car1 = Car("red", 3812.4, True)
>>> car2 = Car("blue", 40231.0, False)

>>> # Get the mileage:
>>> car2.mileage
40231.0

>>> # Classes are mutable:
>>> car2.mileage = 12
>>> car2.windshield = "broken"

>>> # String representation is not very useful
>>> # (must add a manually written __repr__ method):
>>> car1
<Car object at 0x1081e69e8>

 

 

 +  dataclasses.dataclass: پایتون 3.7+

کلاس های داده در پایتون 3.7 و بالاتر در دسترس هستند. آنها یک جایگزین عالی برای تعریف کلاس های ذخیره سازی داده های خود از ابتدا ارائه می دهند.

 

با نوشتن یک data class به جای یک کلاس ساده پایتون، نمونه های شی شما چند ویژگی مفید را دریافت می کنند که تایپ و کارهای پیاده سازی دستی را برای شما ذخیره می کند:

  • سینتکس برای تعریف متغیرهای instance کوتاهتر است، زیرا نیازی به پیاده سازی متد .__init__() ندارید.
  • instanceهایی که از data calssهای شما ساخته میشوند به‌طور خودکار از طریق یک متد .__repr__() که به‌طور خودکار تولید می‌شود، نمایش رشته‌ای با ظاهر زیبا دریافت می‌کنند.
  • Instance variableها type annotations را می‌پذیرند و dataclassهای شما را تا حدی مستند می‌کنند. به خاطر داشته باشید که type annotationsها فقط نکاتی هستند که بدون ابزار بررسی نوع جداگانه اعمال نمی شوند.

 

datclassها معمولاً با استفاده از دکوراتور @dataclass ایجاد می شوند، همانطور که در مثال کد زیر مشاهده می کنید:

>>> from dataclasses import dataclass
>>> @dataclass
... class Car:
...     color: str
...     mileage: float
...     automatic: bool
...
>>> car1 = Car("red", 3812.4, True)

>>> # Instances have a nice repr:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

>>> # Accessing fields:
>>> car1.mileage
3812.4

>>> # Fields are mutable:
>>> car1.mileage = 12
>>> car1.windshield = "broken"

>>> # Type annotations are not enforced without
>>> # a separate type checking tool like mypy:
>>> Car("red", "NOT_A_FLOAT", 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)

 

ویدیو پیشنهادی: ویدیو آموزش ساخت آبجکت های iterable در پایتون

 

 +  collections.namedTuples: اشیا داده مناسب

کلاس namedtuple موجود در Python 2.6+ پسوندی از نوع داده تاپل داخلی را ارائه می دهد. مشابه تعریف یک کلاس سفارشی، استفاده از namedtuple به شما امکان می دهد تا طرح های قابل استفاده مجدد را برای رکوردهای خود تعریف کنید که از استفاده از نام فیلدهای صحیح اطمینان حاصل کنید.

 

اشیاء namedtuple تغییرناپذیر هستند، درست مانند تاپل های معمولی. این بدان معنی است که شما نمی توانید پس از ایجاد نمونه namedtuple، فیلدهای جدید اضافه کنید یا فیلدهای موجود را تغییر دهید.

 

علاوه بر این، اشیاء نامگذاری شده، خوب هستند. . . تاپل ها به نام هر شی ذخیره شده در آنها از طریق یک شناسه منحصر به فرد قابل دسترسی است. این شما را از به خاطر سپردن شاخص‌های اعداد صحیح یا متوسل شدن به راه‌حل‌هایی مانند تعریف ثابت‌های عدد صحیح به‌عنوان یادگاری برای ایندکس‌های خود رها می‌کند.

 

اشیاء namedtuple به عنوان کلاس های پایتون معمولی در داخل پیاده سازی می شوند. وقتی صحبت از استفاده از حافظه به میان می‌آید، آنها همچنین بهتر از کلاس‌های معمولی هستند و به اندازه تاپل‌های معمولی کارآمد حافظه هستند:

>>> from collections import namedtuple
>>> from sys import getsizeof

>>> p1 = namedtuple("Point", "x y z")(1, 2, 3)
>>> p2 = (1, 2, 3)

>>> getsizeof(p1)
64
>>> getsizeof(p2)
64

 

اشیاء namedtuple می تواند یک راه آسان برای پاکسازی کد شما و خوانایی بیشتر آن با اعمال ساختاری بهتر برای داده های شما باشد.

 

من متوجه شدم که رفتن از انواع داده‌های موقتی مانند دیکشنری‌ها با فرمت ثابت به اشیاء نام‌دوگانه به من کمک می‌کند تا هدف کدم را واضح‌تر بیان کنم. اغلب زمانی که من این refactoring را اعمال می کنم، به طور جادویی راه حل بهتری برای مشکلی که با آن روبرو هستم پیدا می کنم.

 

استفاده از اشیاء نام‌گذاری شده روی تاپل‌ها و dictهای معمولی(بدون ساختار) همچنین می‌تواند زندگی همکاران شما را با ایجاد داده‌هایی که در اطراف خود مستندسازی می‌شوند، حداقل تا حدی آسان‌تر کند:

>>> from collections import namedtuple
>>> Car = namedtuple("Car" , "color mileage automatic")
>>> car1 = Car("red", 3812.4, True)

>>> # Instances have a nice repr:
>>> car1
Car(color="red", mileage=3812.4, automatic=True)

>>> # Accessing fields:
>>> car1.mileage
3812.4

>>> # Fields are immtuable:
>>> car1.mileage = 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute

>>> car1.windshield = "broken"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Car' object has no attribute 'windshield'

 

ویدیو پیشنهادی: ویدیو آموزش آبجکت های container در پایتون

 

 +  typing.namedTuples: داده namedTuples بهترشده

اضافه شده در Python 3.6، داده typing.NamedTuple برادر کوچکتر از کلاس namedtuple در ماژول collections است. این بسیار شبیه به namedtuple است، با تفاوت اصلی یک نحو به روز شده برای تعریف انواع رکوردهای جدید و پشتیبانی اضافه شده برای type hint.

>>> from typing import NamedTuple

>>> class Car(NamedTuple):
...     color: str
...     mileage: float
...     automatic: bool

>>> car1 = Car("red", 3812.4, True)

>>> # Instances have a nice repr:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

>>> # Accessing fields:
>>> car1.mileage
3812.4

>>> # Fields are immutable:
>>> car1.mileage = 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute

>>> car1.windshield = "broken"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Car' object has no attribute 'windshield'

>>> # Type annotations are not enforced without
>>> # a separate type checking tool like mypy:
>>> Car("red", "NOT_A_FLOAT", 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)

 

 

 +  struct.Struct: ساختار‌های سریالایز C

کلاس struct.Struct بین مقادیر پایتون و ساختارهای C سریال شده به اشیاء بایت پایتون تبدیل می کند. به عنوان مثال، می توان از آن برای مدیریت داده های باینری ذخیره شده در فایل ها یا دریافت از اتصالات شبکه استفاده کرد.

 

Struct با استفاده از یک زبان کوچک بر اساس رشته‌های قالب تعریف می‌شوند که به شما امکان می‌دهد ترتیب انواع داده‌های C مانند char، int، و long و همچنین انواع بدون علامت آنها را تعریف کنید.

 

structهای سریالایز شده به ندرت برای نشان دادن اشیاء داده استفاده می شوند که صرفاً در کد پایتون مدیریت می شوند. آنها در درجه اول به عنوان یک قالب تبادل داده در نظر گرفته شده اند تا به عنوان راهی برای نگهداری داده ها در حافظه که فقط توسط کد پایتون استفاده می شود.

 

در برخی موارد، بسته‌بندی داده‌های اولیه در ساختارها ممکن است از حافظه کمتری نسبت به نگهداری آن در سایر انواع داده استفاده کند. با این حال، در بیشتر موارد این یک بهینه سازی کاملاً پیشرفته (و احتمالاً غیر ضروری) خواهد بود:

>>> from struct import Struct
>>> MyStruct = Struct("i?f")
>>> data = MyStruct.pack(23, False, 42.0)

>>> # All you get is a blob of data:
>>> data
b'\x17\x00\x00\x00\x00\x00\x00\x00\x00\x00(B'

>>> # Data blobs can be unpacked again:
>>> MyStruct.unpack(data)
(23, False, 42.0)

 

ویدیو پیشنهادی: ویدیو آموزش ماژول logging در پایتون

 

 +  typing.SimpleNamespace: دسترسی به ویژگی‌های فانتزی

در اینجا یک انتخاب کمی مبهم دیگر برای پیاده سازی اشیاء داده در پایتون وجود دارد: Types.SimpleNamespace. این کلاس در پایتون 3.3 اضافه شد و دسترسی ویژگی(attribute) را به فضای نام آن فراهم می کند.

 

این بدان معناست که نمونه های SimpleNamespace همه کلیدهای خود را به عنوان ویژگی های کلاس در معرض نمایش می گذارند. می‌توانید از دسترسی ویژگی نقطه‌دار obj.key به جای نحو ایندکس براکت obj['key'] استفاده کنید که توسط dictهای معمولی استفاده می‌شود. همه نمونه‌ها به طور پیش‌فرض دارای یک __repr__ معنی‌دار هستند.

 

همانطور که از نام آن مشخص است، SimpleNamespace ساده است! این اساسا یک دیکشنری است که اجازه دسترسی به ویژگی را می دهد و به خوبی چاپ می کند. ویژگی ها را می توان آزادانه اضافه، اصلاح و حذف کرد:

>>> from types import SimpleNamespace
>>> car1 = SimpleNamespace(color="red", mileage=3812.4, automatic=True)

>>> # The default repr:
>>> car1
namespace(automatic=True, color='red', mileage=3812.4)

>>> # Instances support attribute access and are mutable:
>>> car1.mileage = 12
>>> car1.windshield = "broken"
>>> del car1.automatic
>>> car1
namespace(color='red', mileage=12, windshield='broken')

 

 

 +  نتیجه گیری: رکوردها، ساختار‌ها و آبجکت‌های انتقال داده

همانطور که مشاهده کردید، تعداد زیادی گزینه مختلف برای اجرای رکوردها یا اشیاء داده وجود دارد. از کدام نوع برای اشیاء داده در پایتون استفاده کنید؟ به طور کلی تصمیم شما به مورد استفاده شما بستگی دارد:

  • اگر فقط چند فیلد دارید، در صورتی که ترتیب فیلدها به راحتی قابل یادآوری باشد یا نام فیلدها اضافی باشد، استفاده از یک شی تاپلی ساده ممکن است مشکلی نداشته باشد. به عنوان مثال، به یک نقطه (x، y، z) در فضای سه بعدی فکر کنید.
  • اگر به فیلدهای تغییرناپذیر نیاز دارید، پس تاپل های ساده، collections.namedtuple و typing.NamedTuple همگی گزینه های خوبی هستند.
  • اگر باید نام فیلدها را قفل کنید تا از اشتباهات املایی جلوگیری شود، collections.namedtuple و typing.NamedTuple دوستان شما هستند.
  • اگر می خواهید همه چیز را ساده نگه دارید، یک شیء دیکشنری ساده ممکن است به دلیل نحو مناسبی که بسیار شبیه JSON است، انتخاب خوبی باشد.
  • اگر به کنترل کامل بر روی ساختار داده خود نیاز دارید، زمان آن رسیده است که یک کلاس سفارشی با تنظیم‌کننده‌ها و دریافت‌کننده‌های property@ بنویسید.
  • اگر برای سریال‌سازی آن‌ها روی دیسک یا ارسال آن‌ها از طریق شبکه نیاز به بسته‌بندی محکم دارید، وقت آن است که struct.Struct را بخوانید زیرا این یک مورد استفاده عالی برای آن است!

 

اگر به دنبال یک انتخاب پیش‌فرض مطمئن هستید، توصیه کلی من برای پیاده‌سازی یک رکورد ساده، ساختار یا شی داده در پایتون این است که از collections.namedtuple در Python 2.x و برادر کوچک‌تر آن، typing.NamedTuple در Python3 استفاده کنید.

 

ویدیو پیشنهادی: ویدیو آموزش ماژول textwrap در پایتون

 

 #  set و multiset

در این بخش، نحوه پیاده‌سازی ساختارهای داده قابل تغییر و تغییرناپذیر set و multiset را در پایتون با استفاده از انواع داده‌ها و کلاس‌های داخلی کتابخانه استاندارد خواهید دید.

 

set مجموعه ای نامرتب از اشیاء است که اجازه تکرار عناصر را نمی دهد. به طور معمول، setها برای آزمایش سریع یک مقدار برای عضویت در مجموعه، برای درج یا حذف مقادیر جدید از یک مجموعه، و برای محاسبه اتحاد(union) یا تقاطع(intersection) دو مجموعه استفاده می شوند.

 

در اجرای set مناسب، انتظار می رود که آزمون های عضویت در زمان O(1) سریع اجرا شوند. عملیات اتحاد، تقاطع، تفاوت و زیر مجموعه باید به طور متوسط زمان O(n) داشته باشد. set پیاده‌سازی‌ شده موجود در کتابخانه استاندارد پایتون از این ویژگی‌های عملکرد پیروی می‌کنند.

 

درست مانند دیکشنری ها، setها در پایتون مورد توجه ویژه قرار می گیرند و ساختن آنها آسان است.

vowels = {"a", "e", "i", "o", "u"}
squares = {x * x for x in range(10)}

 

اما مراقب باشید: برای ایجاد یک set خالی، باید متد set() را فراخوانی کنید. استفاده از آکولاد خالی ({}) مبهم است و به جای آن یک دیکشنری خالی ایجاد می کند.

 

پایتون و کتابخانه استاندارد آن چندین set پیاده سازی را ارائه می دهند. بیایید نگاهی به آنها بیندازیم.

 

 

 +  set: مجموعه در دسترس شما

نوع set، اجرای مجموعه داخلی در پایتون است. قابل تغییر است و امکان درج و حذف پویا عناصر را فراهم می کند.

 

setهای پایتون توسط نوع داده dict پشتیبانی می‌شوند و ویژگی‌های عملکردی یکسانی دارند. هر شیء قابل هش را می توان در set ذخیره کرد:

>>> vowels = {"a", "e", "i", "o", "u"}
>>> "e" in vowels
True

>>> letters = set("alice")
>>> letters.intersection(vowels)
{'a', 'e', 'i'}

>>> vowels.add("x")
>>> vowels
{'i', 'a', 'u', 'o', 'x', 'e'}

>>> len(vowels)
6

 

 

 +  frozenset: نوع set تغییرناپذیز

کلاس frozenset یک نسخه تغییرناپذیر از set را پیاده سازی می کند که پس از ساخته شدن قابل تغییر نیست.

 

اشیای frozenset ثابت هستند و فقط عملیات پرس و جو را روی عناصر خود اجازه می دهند، نه درج یا حذف. از آنجا که اشیاء frozenset ثابت و قابل هش هستند، می‌توانند به عنوان کلیدهای دیکشنری یا عناصر set دیگری استفاده شوند، چیزی که با اشیاء set معمولی (تغییرپذیر) امکان پذیر نیست:

>>> vowels = frozenset({"a", "e", "i", "o", "u"})
>>> vowels.add("p")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

>>> # Frozensets are hashable and can
>>> # be used as dictionary keys:
>>> d = { frozenset({1, 2, 3}): "hello" }
>>> d[frozenset({1, 2, 3})]
'hello'

 

 

 +  collections.Counter: چند set

کلاس collections.Counter در کتابخانه استاندارد پایتون یک نوع multiset را پیاده‌سازی می‌کند که به عناصر set اجازه می‌دهد بیش از یک رخداد داشته باشند.

 

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

>>> from collections import Counter
>>> inventory = Counter()

>>> loot = {"sword": 1, "bread": 3}
>>> inventory.update(loot)
>>> inventory
Counter({'bread': 3, 'sword': 1})

>>> more_loot = {"sword": 1, "apple": 1}
>>> inventory.update(more_loot)
>>> inventory
Counter({'bread': 3, 'sword': 2, 'apple': 1})

 

یک نکته برای کلاس Counter این است که باید هنگام شمارش تعداد عناصر موجود در یک شی Counter مراقب باشید. فراخوانی len() تعداد عناصر منحصر به فرد را در multiset برمی گرداند، در حالی که تعداد کل عناصر را می توان با استفاده از sum() به دست آورد:

>>> len(inventory)
3  # Unique elements

>>> sum(inventory.values())
6  # Total no. of elements

 

 

 #  Stack(LIFO)

stack مجموعه ای از اشیاء است که از معنای سریع Last-In/First-Out (LIFO) برای درج و حذف پشتیبانی می کند. برخلاف listها یا آرایه‌ها، stackها معمولاً اجازه دسترسی تصادفی به اشیاء موجود در آنها را نمی‌دهند. عملیات درج و حذف اغلب push و pop نیز نامیده می شود.

 

یک قیاس مفید در دنیای واقعی برای ساختار داده stack، پشته ای از صفحات است. صفحات جدید به بالای پشته اضافه می شوند و از آنجایی که صفحات گرانبها و سنگین هستند، فقط بالاترین صفحه را می توان جابجا کرد. به عبارت دیگر، آخرین صفحه روی پشته باید اولین صفحه برداشته شود (LIFO). برای رسیدن به صفحاتی که پایین تر در پشته قرار دارند، بالاترین صفحات باید یکی یکی جدا شوند.

 

از نظر عملکرد، انتظار می رود اجرای پشته مناسب برای عملیات درج و حذف زمان O(1) را ببرد.

 

پایتون با چندین پیاده‌سازی stack عرضه می‌شود که هر کدام ویژگی‌های کمی متفاوت دارند. بیایید نگاهی به آنها بیندازیم و ویژگی های آنها را با هم مقایسه کنیم.

 

 

 +  list: ساده و داخلی

نوع لیست داخلی پایتون یک ساختار داده پشته مناسبی ایجاد می کند زیرا از عملیات push و pop در زمان استهلاک O(1) پشتیبانی می کند.

 

فهرست‌های پایتون به‌عنوان آرایه‌های پویا در داخل پیاده‌سازی می‌شوند، به این معنی که گهگاه نیاز به تغییر اندازه فضای ذخیره‌سازی عناصر ذخیره‌شده در آنها هنگام افزودن یا حذف عناصر دارند. list، فضای ذخیره سازی پشتیبان خود را بیش از حد اختصاص می دهد، به طوری که هر push یا pop نیازی به تغییر اندازه ندارد. در نتیجه، پیچیدگی زمانی O(1) مستهلک شده برای این عملیات دریافت می کنید.

 

نکته منفی این است که عملکرد آن‌ها نسبت به درج‌ها و حذف‌های O(1) پایدار ارائه‌شده توسط یک پیاده‌سازی مبتنی بر list پیوندی (همانطور که در زیر با collections.deque خواهید دید) سازگاری کمتری دارد. از سوی دیگر، لیست ها دسترسی تصادفی سریع O(1) را به عناصر موجود در stack فراهم می کنند و این می تواند یک مزیت اضافی باشد.

 

یک هشدار مهم در عملکرد وجود دارد که هنگام استفاده از لیست ها به عنوان stack باید از آن آگاه باشید: برای دریافت عملکرد مستهلک شده O(1) برای درج و حذف، موارد جدید باید با متد append() به انتهای لیست اضافه شده و دوباره از انتها با استفاده از pop() حذف شوند. برای عملکرد بهینه، stackهای مبتنی بر listهای پایتون باید به سمت indexهای بالاتر رشد کنند و به سمت indexهای پایین تر کوچک شوند.

 

افزودن و حذف از جلو بسیار کندتر است و زمان O(n) را می طلبد، زیرا عناصر موجود باید به اطراف جابجا شوند تا فضا برای عنصر جدید باز شود. این یک ضد الگوی عملکرد است که باید تا حد امکان از آن اجتناب کنید:

>>> s = []
>>> s.append("eat")
>>> s.append("sleep")
>>> s.append("code")

>>> s
['eat', 'sleep', 'code']

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list

 

 

 +  collections.deque: سریع و قوی

کلاس deque یک صف دو سر را پیاده سازی می کند که از افزودن و حذف عناصر از هر طرف در زمان O(1) (غیر مستهلک) پشتیبانی می کند. از آنجایی که deque ها از افزودن و حذف عناصر از هر دو انتهای یکسان به خوبی پشتیبانی می کنند، می توانند هم به عنوان queue و هم به عنوان stack عمل کنند.

 

اشیاء deque پایتون به صورت لیست‌هایی با پیوند دوگانه پیاده‌سازی می‌شوند که به آنها عملکرد عالی و ثابتی برای درج و حذف عناصر می‌دهد اما عملکرد O(n) ضعیفی برای دسترسی تصادفی به عناصر در وسط یک stack به آنها می‌دهد.

 

به طور کلی، اگر به دنبال ساختار داده stack در کتابخانه استاندارد پایتون هستید که ویژگی های عملکردی پیاده سازی لیست پیوندی را داشته باشد، collections.deque یک انتخاب عالی است:

>>> from collections import deque
>>> s = deque()
>>> s.append("eat")
>>> s.append("sleep")
>>> s.append("code")

>>> s
deque(['eat', 'sleep', 'code'])

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

 

 

 #  Queue(FIFO)

در این بخش، نحوه پیاده‌سازی ساختار داده صف First-In/First-Out (FIFO) را با استفاده از انواع داده‌های داخلی و کلاس‌های کتابخانه استاندارد پایتون خواهید دید.

 

صف مجموعه ای از اشیاء است که از معنای سریع FIFO برای درج و حذف پشتیبانی می کند. عملیات درج و حذف را گاهی اوقات enqueue و dequeue می نامند. برخلاف listها یا آرایه‌ها، صف‌ها معمولاً اجازه دسترسی تصادفی به اشیاء موجود در آنها را نمی‌دهند.

 

صف ها شبیه به stackها هستند. تفاوت بین آنها در نحوه حذف موارد نهفته است. با یک صف، آیتمی که اول اضافه شده است (FIFO) را حذف می کنید، اما با یک پشته، آیتمی که آخر اضافه شده است (LIFO) را حذف می کنید.

 

از نظر عملکرد، انتظار می‌رود که اجرای صف مناسب، زمان O(1) را برای عملیات درج و حذف ببرد. این دو عملیات اصلی هستند که روی یک صف انجام می شوند و در اجرای صحیح باید سریع باشند.

 

 

 +  list: یک صف بسیار کند

استفاده از یک لیست معمولی به عنوان صف امکان پذیر است، اما این از منظر عملکرد ایده آل نیست. لیست ها برای این منظور بسیار کند هستند زیرا درج یا حذف یک عنصر در ابتدا مستلزم جابجایی تمام عناصر دیگر به اندازه یک ایندکس، به زمان O(n) است.

 

بنابراین، من استفاده از یک لیست را به عنوان یک صف موقت در پایتون توصیه نمی کنم، مگر اینکه فقط با تعداد کمی از عناصر سروکار داشته باشید:

>>> q = []
>>> q.append("eat")
>>> q.append("sleep")
>>> q.append("code")

>>> q
['eat', 'sleep', 'code']

>>> # Careful: This is slow!
>>> q.pop(0)
'eat'

 

 

 +  collections.deque: صف سریع و قوی

کلاس deque یک صف دو سر را پیاده سازی می کند که از افزودن و حذف عناصر از هر طرف در زمان O(1) (غیر مستهلک) پشتیبانی می کند. از آنجایی که deque ها از افزودن و حذف عناصر از هر دو انتهای یکسان به خوبی پشتیبانی می کنند، می توانند هم به عنوان صف و هم به عنوان stack عمل کنند.

 

اشیاء deque پایتون به صورت لیست های دارای پیوند دوگانه پیاده سازی می شوند. این به آنها عملکرد عالی و ثابتی برای درج و حذف عناصر می دهد، اما عملکرد O(n) ضعیفی برای دسترسی تصادفی به عناصر در وسط stack می دهد.

 

در نتیجه، اگر به دنبال ساختار داده صف در کتابخانه استاندارد پایتون هستید، collections.deque یک انتخاب پیش‌فرض عالی است:

>>> from collections import deque
>>> q = deque()
>>> q.append("eat")
>>> q.append("sleep")
>>> q.append("code")

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'

>>> q.popleft()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

 

 

 +  Queue.queue: قفل کردن برای محاسبات موازی

اجرای queue.Queue در کتابخانه استاندارد پایتون همزمان است و قفل را برای پشتیبانی از چندین تولید کننده(producers) و مصرف کننده(consumers) همزمان ارائه می دهد.

 

ماژول queue شامل چندین کلاس دیگر است که صف های چند تولید کننده و چند مصرف کننده را پیاده سازی می کنند که برای محاسبات موازی مفید هستند.

 

بسته به مورد استفاده شما، قفل ممکن است مفید باشد یا فقط هزینه های غیر ضروری را متحمل شود. در این مورد، بهتر است از collections.deque به عنوان یک صف همه منظوره استفاده کنید:

>>> from queue import Queue
>>> q = Queue()
>>> q.put("eat")
>>> q.put("sleep")
>>> q.put("code")

>>> q
<queue.Queue object at 0x1070f5b38>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get_nowait()
queue.Empty

>>> q.get()  # Blocks/waits forever...

 

 

 #  نتیجه گیری

به این ترتیب گشت و گذار شما در ساختارهای داده رایج در پایتون به پایان می رسد. با دانشی که در اینجا به دست آورده اید، آماده اجرای ساختارهای داده کارآمدی هستید که برای الگوریتم خاص یا مورد استفاده شما مناسب هستند.

مطالب مشابه



مونگارد