روشهای مرتبسازی¶
- نویسنده:
Andrew Dalke و Raymond Hettinger
فهرستهای پایتون یک متد توکار list.sort() دارند که فهرست را بهصورت درجا تغییر میدهد. همچنین یک تابع توکار sorted() وجود دارد که یک فهرست مرتبشدهی جدید از یک پیمایشپذیر میسازد.
در این سند، روشهای مختلف مرتبسازی دادهها با استفاده از پایتون را بررسی میکنیم.
مبانی مرتبسازی¶
یک مرتبسازی صعودی ساده بسیار آسان است: کافی است تابع sorted() را فراخوانی کنید. این تابع یک فهرست مرتبشدهی جدید برمیگرداند:
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
همچنین میتوانید از متد list.sort() استفاده کنید. این متد فهرست را بهصورت درجا تغییر میدهد (و برای جلوگیری از سردرگمی، None را برمیگرداند). معمولاً به اندازه sorted() راحت نیست، اما اگر نیازی به فهرست اصلی ندارید، کمی کارآمدتر است.
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
تفاوت دیگر این است که متد list.sort() فقط برای فهرستها تعریف شده است. در مقابل، تابع sorted() هر پیمایشپذیری را میپذیرد.
>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]
توابع کلیدی¶
متد list.sort() و توابع sorted()، min()، max()، heapq.nsmallest() و heapq.nlargest() یک پارامتر key دارند که برای مشخص کردن تابعی (یا شیء فراخوانیپذیر دیگر) به کار میرود تا پیش از انجام مقایسهها روی هر عنصر فهرست فراخوانی شود.
برای مثال، در اینجا یک مقایسهی رشتهای بدون حساسیت به بزرگی و کوچکی حروف با استفاده از str.casefold() آمده است:
>>> sorted("This is a test string from Andrew".split(), key=str.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
مقدار پارامتر key باید تابعی (یا یک شیء فراخوانیپذیر دیگر) باشد که یک آرگومان میگیرد و کلیدی برای استفاده در مرتبسازی برمیگرداند. این روش سریع است زیرا تابع کلید دقیقاً یک بار برای هر رکورد ورودی فراخوانی میشود.
یک الگوی رایج، مرتبسازی اشیاء پیچیده با استفاده از برخی از اندیسهای شیء بهعنوان کلید است. برای مثال:
>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
همین روش برای اشیاء دارای ویژگیهای نامدار نیز کار میکند. برای مثال:
>>> class Student:
... def __init__(self, name, grade, age):
... self.name = name
... self.grade = grade
... self.age = age
... def __repr__(self):
... return repr((self.name, self.grade, self.age))
>>> student_objects = [
... Student('john', 'A', 15),
... Student('jane', 'B', 12),
... Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
اشیاء دارای ویژگیهای نامدار میتوانند با یک کلاس معمولی، همانطور که در بالا نشان داده شد، ساخته شوند، یا میتوانند نمونههایی از dataclass یا یک named tuple باشند.
توابع ماژول operator و ارزیابی جزئی تابع¶
الگوهای تابع کلید نشاندادهشده در بالا بسیار رایج هستند، بنابراین پایتون توابع کمکی برای سادهتر و سریعتر کردن توابع دسترسی فراهم میکند. ماژول operator دارای توابع itemgetter()، attrgetter() و methodcaller() است.
با استفاده از آن توابع، مثالهای بالا سادهتر و سریعتر میشوند:
>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
توابع ماژول operator امکان مرتبسازی در چند سطح را فراهم میکنند. برای مثال، برای مرتبسازی بر اساس grade و سپس بر اساس age:
>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
ماژول functools ابزار مفید دیگری برای ساخت توابع کلید فراهم میکند. تابع partial() میتواند تعداد آرگومانها (arity) یک تابع با چند آرگومان را کاهش دهد و آن را برای استفاده بهعنوان یک تابع کلید مناسب کند.
>>> from functools import partial
>>> from unicodedata import normalize
>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()
>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']
>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']
صعودی و نزولی¶
هر دو list.sort() و sorted() یک پارامتر reverse با مقدار بولی میپذیرند. این برای مشخص کردن مرتبسازی نزولی استفاده میشود. برای مثال، برای دریافت دادههای دانشجویی به ترتیب معکوس سن:
>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
پایداری مرتبسازی و مرتبسازیهای پیچیده¶
تضمین میشود که مرتبسازیها پایدار باشند. این بدان معناست که هنگامی که چندین رکورد کلید یکسانی دارند، ترتیب اصلی آنها حفظ میشود.
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
توجه کنید که چگونه دو رکورد برای blue ترتیب اصلی خود را حفظ میکنند، بهطوری که تضمین میشود ('blue', 1) پیش از ('blue', 2) قرار دارد.
این ویژگی فوقالعاده به شما امکان میدهد مرتبسازیهای پیچیده را در مجموعهای از گامهای مرتبسازی ایجاد کنید. برای مثال، برای مرتبسازی دادههای دانشآموز بر اساس نمره بهصورت نزولی و سپس سن بهصورت صعودی، ابتدا مرتبسازی بر اساس سن را انجام دهید و سپس دوباره با استفاده از نمره مرتب کنید:
>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
این را میتوان بهصورت یک تابع پوششی انتزاع کرد که بتواند یک فهرست و تاپلهایی از فیلد و ترتیب را برای مرتبسازی آنها در چندین گذر دریافت کند.
>>> def multisort(xs, specs):
... for key, reverse in reversed(specs):
... xs.sort(key=attrgetter(key), reverse=reverse)
... return xs
>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
الگوریتم Timsort بهکاررفته در پایتون، مرتبسازیهای متعدد را بهطور کارآمد انجام میدهد، زیرا میتواند از هرگونه ترتیب از پیش موجود در یک مجموعه داده بهره ببرد.
آرایش-مرتبسازی-ناآرایش (Decorate-Sort-Undecorate)¶
این اصطلاح به نام Decorate-Sort-Undecorate نامیده میشود که برگرفته از سه مرحلهی آن است:
ابتدا، فهرست اولیه با مقادیر جدیدی که ترتیب مرتبسازی را کنترل میکنند، آراسته میشود.
دوم، فهرست دکورشده مرتب میشود.
در نهایت، آرایشها (decorations) حذف میشوند و فهرستی ایجاد میشود که فقط شامل مقادیر اولیه به ترتیب جدید است.
برای مثال، برای مرتبسازی دادههای دانشآموزان بر اساس نمره با استفاده از رویکرد DSU:
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
این روش کار میکند زیرا تاپلها بهصورت لغتنامهای مقایسه میشوند؛ آیتمهای اول مقایسه میشوند؛ اگر یکسان باشند، آیتمهای دوم مقایسه میشوند و به همین ترتیب.
در همه موارد، آوردن اندیس i در فهرست آراسته اکیداً ضروری نیست، اما گنجاندن آن دو مزیت دارد:
مرتبسازی پایدار است — اگر دو آیتم کلید یکسانی داشته باشند، ترتیب آنها در فهرست مرتبشده حفظ میشود.
آیتمهای اصلی لازم نیست قابل مقایسه باشند، زیرا ترتیب تاپلهای دکورشده حداکثر بر اساس دو آیتم اول تعیین میشود. بنابراین برای مثال، فهرست اصلی میتواند شامل اعداد مختلط باشد که نمیتوان آنها را بهطور مستقیم مرتب کرد.
نام دیگر این اصطلاح Schwartzian transform، برگرفته از نام Randal L. Schwartz است که آن را میان برنامهنویسان Perl رواج داد.
اکنون که مرتبسازی پایتون توابع کلید را فراهم میکند، اغلب نیازی به این روش نیست.
توابع مقایسه¶
برخلاف توابع کلید که یک مقدار مطلق را برای مرتبسازی برمیگردانند، یک تابع مقایسه ترتیب نسبی دو ورودی را محاسبه میکند.
برای مثال، یک ترازوی دوکفهای دو نمونه را مقایسه میکند و یک ترتیب نسبی ارائه میدهد: سبکتر، برابر، یا سنگینتر. به همین ترتیب، یک تابع مقایسه مانند cmp(a, b) مقدار منفی برای کوچکتر بودن، صفر اگر ورودیها برابر باشند، یا مقدار مثبت برای بزرگتر بودن برمیگرداند.
معمول است که هنگام ترجمه الگوریتمها از زبانهای دیگر با توابع مقایسه مواجه شوید. همچنین، برخی کتابخانهها توابع مقایسه را بهعنوان بخشی از API خود ارائه میکنند. برای مثال، locale.strcoll() یک تابع مقایسه است.
برای سازگاری با این موقعیتها، پایتون functools.cmp_to_key را فراهم میکند تا تابع مقایسه را در بر بگیرد و آن را بهعنوان تابع کلید قابلاستفاده کند:
sorted(words, key=cmp_to_key(strcoll)) # locale-aware sort order
راهبردهایی برای انواع و مقادیر غیرقابلمرتبسازی¶
هنگام مرتبسازی ممکن است مسائل مختلفی مربوط به نوع و مقدار پیش بیاید. در اینجا چند راهبرد آمده است که میتواند کمک کند:
انواع ورودی غیرقابلمقایسه را پیش از مرتبسازی به رشته تبدیل کنید:
>>> data = ['twelve', '11', 10]
>>> sorted(map(str, data))
['10', '11', 'twelve']
این مورد لازم است، زیرا بیشتر مقایسههای بیننوعی یک TypeError پرتاب میکنند.
مقادیر خاص را پیش از مرتبسازی حذف کنید:
>>> from math import isnan
>>> from itertools import filterfalse
>>> data = [3.3, float('nan'), 1.1, 2.2]
>>> sorted(filterfalse(isnan, data))
[1.1, 2.2, 3.3]
این لازم است زیرا استاندارد IEEE-754 تصریح میکند که: «هر NaN باید در مقایسه با هر چیزی، از جمله خودش، نامرتب باشد.»
به همین ترتیب، میتوان None را نیز از مجموعهدادهها حذف کرد:
>>> data = [3.3, None, 1.1, 2.2]
>>> sorted(x for x in data if x is not None)
[1.1, 2.2, 3.3]
این مورد لازم است زیرا None با انواع دیگر قابلمقایسه نیست.
پیش از مرتبسازی، انواع نگاشت را به فهرستهای مرتبشده از آیتمها تبدیل کنید:
>>> data = [{'a': 1}, {'b': 2}]
>>> sorted(data, key=lambda d: sorted(d.items()))
[{'a': 1}, {'b': 2}]
این کار لازم است، زیرا مقایسهی دیکشنری با دیکشنری باعث پرتاب TypeError میشود.
پیش از مرتبسازی، انواع مجموعه را به فهرستهای مرتبشده تبدیل کنید:
>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> sorted(map(sorted, data))
[['a', 'b', 'c'], ['b', 'c', 'd']]
این امر لازم است زیرا المانهای موجود در انواع مجموعهای ترتیب قطعی ندارند. برای مثال، list({'a', 'b'}) ممکن است ['a', 'b'] یا ['b', 'a'] را تولید کند.
موارد متفرقه¶
برای مرتبسازی آگاه از locale، از
locale.strxfrm()بهعنوان تابع کلید یا ازlocale.strcoll()بهعنوان تابع مقایسه استفاده کنید. این کار ضروری است، زیرا ترتیبهای مرتبسازی «الفبایی» میتوانند بین فرهنگها متفاوت باشند، حتی اگر الفبای زیربنایی یکسان باشد.پارامتر reverse همچنان پایداری مرتبسازی را حفظ میکند (بهطوری که رکوردهایی با کلیدهای برابر، ترتیب اصلی خود را حفظ میکنند). جالب است که میتوان آن اثر را بدون این پارامتر، با دو بار استفاده از تابع توکار
reversed()شبیهسازی کرد:>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> standard_way = sorted(data, key=itemgetter(0), reverse=True) >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0)))) >>> assert standard_way == double_reversed >>> standard_way [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
روالهای مرتبسازی هنگام مقایسهی دو شیء از
<استفاده میکنند. بنابراین، افزودن یک ترتیب مرتبسازی استاندارد به یک کلاس با تعریف یک متد__lt__()آسان است:>>> Student.__lt__ = lambda self, other: self.age < other.age >>> sorted(student_objects) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
با این حال، توجه داشته باشید که اگر
__lt__()پیادهسازی نشده باشد،<میتواند به استفاده از__gt__()روی بیاورد (برای جزئیات سازوکار،object.__lt__()را ببینید). برای جلوگیری از موارد غیرمنتظره، PEP 8 توصیه میکند که هر شش متد مقایسهای پیادهسازی شوند. دکوراتور@~functools.total_orderingبرای آسانتر کردن این کار ارائه شده است.توابع کلید لازم نیست مستقیماً به اشیایی که مرتب میشوند وابسته باشند. یک تابع کلید همچنین میتواند به منابع خارجی دسترسی داشته باشد. برای مثال، اگر نمرات دانشآموزان در یک دیکشنری ذخیرهشده باشد، میتوان از آنها برای مرتبسازی فهرستی جداگانه از نامهای دانشآموزان استفاده کرد:
>>> students = ['dave', 'john', 'jane'] >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'} >>> sorted(students, key=newgrades.__getitem__) ['jane', 'dave', 'john']
مرتبسازیهای جزئی¶
برخی کاربردها تنها نیاز دارند که بخشی از دادهها مرتب باشد. کتابخانه استاندارد چندین ابزار ارائه میدهد که کار کمتری نسبت به مرتبسازی کامل انجام میدهند:
min()وmax()بهترتیب کوچکترین و بزرگترین مقادیر را برمیگردانند. این توابع یک پیمایش واحد روی دادههای ورودی انجام میدهند و تقریباً به هیچ حافظه کمکی نیاز ندارند.heapq.nsmallest()وheapq.nlargest()بهترتیب n مقدار کوچکترین و n مقدار بزرگترین را برمیگردانند. این توابع دادهها را در یک گذر واحد پیمایش میکنند و در هر لحظه فقط n عنصر را در حافظه نگه میدارند. برای مقادیر n که نسبت به تعداد ورودیها کوچک هستند، این توابع مقایسههای بسیار کمتری نسبت به یک مرتبسازی کامل انجام میدهند.heapq.heappush()وheapq.heappop()یک چیدمان تا حدی مرتبشده از دادهها ایجاد و نگهداری میکنند که کوچکترین عنصر را در موقعیت0نگه میدارد. این توابع برای پیادهسازی صفهای اولویتی که معمولاً برای زمانبندی وظایف استفاده میشوند، مناسب هستند.