Мураттабсозӣ ва ҷустуҷӯ

Маълумоти мураттаб — нисфи муваффақият дар бисёр масъалаҳо: дар он калонтаринро ёфтан осон аст, элементҳои якхела дар паҳлӯи ҳам меафтанд, ва қимати лозимиро хеле зуд ҷустан мумкин аст.

sorted ва sort

a = [5, 2, 9, 1]
b = sorted(a)       # рӯйхати нави [1, 2, 5, 9], a тағйир наёфт
a.sort()            # худи a-ро мураттаб мекунад, None бармегардонад

• sorted(ҳар чӣ) — рӯйхати нав бармегардонад. Бо сатр ва бо map ҳам кор мекунад: sorted("анор") → ['а', 'н', 'о', 'р'].
• рӯйхат.sort() — рӯйхатро «дар ҷояш» мураттаб мекунад.

Хатои маъмул: a = a.sort() — пас аз ин дар a None мешавад.

Бо тартиби камшавӣ — параметри reverse=True:

print(sorted([3, 8, 1], reverse=True))   # [8, 3, 1]

Сатрҳо аз рӯи алифбо (дақиқтараш, аз рӯи рамзҳои аломатҳо) мураттаб мешаванд: ҳарфҳои калон пеш аз ҳарфҳои хурд меоянд.

Мураттабсозӣ аз рӯи калид

Параметри key муайян мекунад, ки элементҳо аз рӯи кадом аломат муқоиса шаванд. Ба он функсия медиҳанд, ки барои ҳар элемент даъват мешавад:

words = ["себ", "гурба", "тарбуз", "нок"]
print(sorted(words, key=len))        # аз рӯи дарозӣ: ['себ', 'нок', 'гурба', 'тарбуз']

nums = [-7, 3, -1, 5]
print(sorted(nums, key=abs))         # аз рӯи модул: [-1, 3, 5, -7]

names = ["bob", "Alice", "carl"]
print(sorted(names, key=str.lower))  # бе назардошти ҳарфи калон/хурд

Мураттабсозӣ дар Python устувор аст: элементҳои калидашон якхела тартиби аслии худро нигоҳ медоранд. Дар мисоли боло «себ» ва «нок» дарозии якхела доранд, бинобар ин бо ҳамон тартибе ки буданд, монданд.

key дар min ва max ҳам кор мекунад: max(words, key=len) — калимаи дарозтарин.

Функсияҳои худро барои key (масалан, «аввал аз рӯи дарозӣ, баъд аз рӯи алифбо») дар мавзӯи «Функсияҳо» навиштанро меомӯзем.

Мураттабсозӣ чӣ медиҳад

Пас аз мураттабсозӣ:

• минимум — a[0], максимум — a[-1], k-ум аз рӯи бузургӣ — a[-k];
• элементҳои якхела дар паҳлӯи ҳам меистанд — онҳоро бо муқоисаи a[i] ва a[i - 1] ҳисоб кардан осон аст;
• элементҳои ҳамсоя — аз рӯи қимат аз ҳама наздиканд.

Мисол: дар рӯйхат чанд адади гуногун ҳаст?

a = sorted([4, 1, 4, 2, 1, 4])   # [1, 1, 2, 4, 4, 4]
distinct = 1
for i in range(1, len(a)):
    if a[i] != a[i - 1]:
        distinct += 1
print(distinct)                    # 3

Мураттабсозии n элемент тақрибан n · log n амал мегирад — рӯйхати 10⁵–10⁶ адад дар як ҳиссаи сония мураттаб мешавад.

Ҷустуҷӯи хаттӣ

Элементро дар рӯйхати номураттаб танҳо бо гузаштан ёфтан мумкин аст: x in a, a.index(x) ё давра. Ин n қадам аст. Агар бисёр бор ҷустан лозим бошад, дароз мешавад.

Ҷустуҷӯи дуӣ

Дар рӯйхати мураттаб хеле тезтар ҷустан мумкин аст. Ғоя мисли бозии «ададро аз 1 то 100 ёб»: мобайнро мепурсем, ва ҳар ҷавоб нисфи вариантҳоро мепартояд.

Мефаҳмем, ки адади x дар рӯйхати мураттаб ҳаст ё не:

a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23

lo, hi = 0, len(a) - 1
found = False
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == x:
        found = True
        break
    elif a[mid] < x:
        lo = mid + 1      # x аз мобайн росттар аст
    else:
        hi = mid - 1      # x аз мобайн чаптар аст
print(found)              # True

Ҳар қадам порчаи ҷустуҷӯро нисф мекунад, бинобар ин барои як миллион элемент тақрибан 20 қадам лозим аст, на як миллион.

Душвортарин чиз дар ҷустуҷӯи дуӣ — дар сарҳадҳо ба як хато накардан. Бинобар ин барои масъалаҳои стандартӣ модули тайёр ҳаст.

Модули bisect

from bisect import bisect_left, bisect_right

heights = [140, 145, 150, 150, 155, 162]   # мураттаб аст!

print(bisect_left(heights, 150))   # 2 — чанд элемент АЗ 150 ҚАТЪИЯН ХУРД аст
print(bisect_right(heights, 150))  # 4 — чанд элемент АЗ 150 ХУРД Ё БАРОБАР аст

• bisect_left(a, x) — мавқеи аввалест, ки ба он x-ро бе вайрон кардани тартиб гузоштан мумкин аст. Ин маҳз шумораи элементҳои < x аст.
• bisect_right(a, x) — мавқеъ пас аз ҳамаи элементҳои ба x баробар. Ин шумораи элементҳои <= x аст.

Чанд хонанда қадашон аз 145 то 155 (бо дохил) аст?

print(bisect_right(heights, 155) - bisect_left(heights, 145))   # 4

Муҳим: bisect танҳо дар рӯйхати мураттаб дуруст кор мекунад.

Хулоса

• sorted(a) — рӯйхати нав, a.sort() — дар ҷояш; reverse=True — бо тартиби камшавӣ;
• key=len, key=abs, key=str.lower — мураттабсозӣ аз рӯи аломат; дар min/max ҳам кор мекунад;
• пас аз мураттабсозӣ элементҳои якхела дар паҳлӯи ҳам, ҳамсояҳо бошанд — аз рӯи қимат наздиктарин;
• ҷустуҷӯи дуӣ қиматро дар log n қадам меёбад, вале танҳо дар рӯйхати мураттаб;
• bisect_left — чанд элемент < x, bisect_right — чанд элемент <= x.