Түгээмэл хурдасгалууд

Танилцуулга

Өмнөх хоёр хичээл хэрэгслүүдэд зориулагдсан: timeit жижиг хэсгийг хэмждэг, cProfile халуун цэгийг олдог. Халуун цэгийг олсны дараа асуулт гарна: үүнийг яаж хурдасгах вэ? Хариулт ихэнхдээ шинэ алгоритм зохиох биш. Python програмын удаан хэсгүүдийн гайхмаар их хувь нь цөөн хэдэн танил загвараас үүсдэг бөгөөд тус бүрд бэлэн, батлагдсан засвар бий.

Энэ хичээлд бид тэдгээрийн дөрвийг судална. Нэгдүгээрт, хайлт: list-ийн оронд set эсвэл dict. Энэ бол өмнөх хичээлийн засварын нууц. Хоёрдугаарт, string нийлүүлэх: +=-ийн оронд join. Гуравдугаарт, generator: бүтэн жагсаалтын оронд нэг нэгээр. Дөрөвдүгээрт, cache: давтагдах тооцооллыг хадгалах. Сүүлийн хоёртой бид аль хэдийн танилцсан, Хичээл 2.2 ба 3.3-т. Энэ удаа тэдгээрийг хурдны өнцгөөс, ялангуяа хэзээ тус болдоггүй өнцгөөс харна.

Энэ хичээлийн гол санаа: засвар бүр нөхцөлтэй. Засвар бүрийг өмнө ба дараа нь хэмжиж, тэр нөхцөлийг тоогоор олно. Интернэтэд “Python-ийг хурдасгах 10 арга” маягийн жагсаалт олон байдаг бөгөөд тэдгээрийн ихэнх нь нөхцөлгүй дүрэм мэт бичигдсэн. Нөхцөлгүй дүрэм бол Хичээл 12.1-ийн буруу зөн совингийн өөр нэг хэлбэр.

Зүйрлэл

Номын санд нэг ном хайж байгаагаа төсөөлөөд үзээрэй. Эхний номын санд ном ирсэн дарааллаар нь тавиур дээр жагссан. Тодорхой номыг олохын тулд эхнээс нь эхлээд нэг нэгээр нь харна. Мянган номтой бол дунджаар таван зуу харна. Хэрэв ном байхгүй бол бүх мянгыг харж байж "байхгүй" гэдгийг мэднэ.

Хоёр дахь номын сан каталогтой. Номын нэрээс тодорхой дүрмээр тавиурын дугаар тооцоолно, жишээлбэл эхний үсгээр. Та тооцоолсон тавиур руу шууд очиж, тэнд байгаа цөөн номыг л харна. Номын сан мянган номтой ч, сая номтой ч хайлт бараг ижил хурдан: тооцоолох, очих, цөөн ном харах.

Python-ий list бол эхний номын сан: in оператор элемент бүрийг нэг нэгээр шалгана. set ба dict бол хоёр дахь: тэд элемент бүрийн hash буюу "тавиурын дугаар"-ыг тооцоолж, шууд тэр байрлал руу очдог. Энэ дугаарыг Python-ий hash() функц тооцоолно. hash("Бат") танд том бүхэл тоо өгнө, бусад бүх зүйл Python-ий дотор автоматаар хийгддэг.

Каталог үнэгүй биш. Номын санд ном нэмэх бүрт каталогт бүртгэх ажил нэмэгдэнэ, каталог өөрөө зай эзэлнэ. Хэрэв та ганцхан удаа, тав хан номтой тавиураас ном хайх гэж байгаа бол каталог бүтээх нь цаг алдах. Энэ нь энэ хичээлийн дөрвөн засвар бүрийн хэлбэр: урьдчилсан зардал, дараа нь хурдан ажил. Ашигтай эсэх нь тэр урьдчилсан зардлыг хэдэн удаа нөхөхөөс хамаарна.

Засвар 1: хайлт — list-ийн оронд set эсвэл dict

Эхлээд нэг хайлтыг хэмжье. 10,000 нэр, хайх нэр нь хамгийн сүүлд байрлана:

python -m timeit -s "names = [f'Хэрэглэгч-{i}' for i in range(10_000)]" "'Хэрэглэгч-9999' in names"
python -m timeit -s "names = {f'Хэрэглэгч-{i}' for i in range(10_000)}" "'Хэрэглэгч-9999' in names"

Хоёр мөрийн цорын ганц ялгаа нь хаалт: дөрвөлжин хаалт list comprehension, гоё хаалт set comprehension. Нэг компьютер дээрх үр дүн:

5000 loops, best of 5: 61.3 usec per loop
10000000 loops, best of 5: 24.1 nsec per loop

List-д 61 микросекунд, set-д 24 наносекунд: 2,500 дахин хурдан. Хамгийн чухал нь: list-ийн хугацаа элементийн тоотой пропорциональ, 100,000 нэр бол арав дахин удаан. set-ийн хугацаа элементийн тооноос бараг хамаардаггүй. Өмнөх хичээлийн засварт list-ийн index-ийг dict-ийн хайлтаар солиход энэ шалтгаанаар index-ийн 0.149 секунд хүснэгтээс алга болсон.

Гэвч set-ийг бүтээх ч зардалтай. Хэмжье:

python -m timeit -s "names = [f'Хэрэглэгч-{i}' for i in range(10_000)]" "set(names)"

1000 loops, best of 5: 287 usec per loop

Set бүтээх нь list-ээс нэг хайлт хийхээс тав дахин удаан. Тэгэхээр ганц хайлтын тулд list-ийг set болгох нь хурдыг удаашруулна. Энэ засвар тавиас олон хайлт хийх үед л өөрийгөө нөхнө. Мөн маш жижиг цуглуулгад, хэдэн элементтэй, list ба set-ийн ялгаа хэмжигдэхүйц биш.

Засвар жинхэнэ утгаа гаргадаг загвар: давталт доторх хайлт. Давхардлыг арилгах бодит жишээ:

python

import time


def unique_with_list(items):
    seen = []
    result = []
    for item in items:
        if item not in seen:
            seen.append(item)
            result.append(item)
    return result


def unique_with_set(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result


ids = [f"ORD-{i}" for i in range(20_000)]

for func in (unique_with_list, unique_with_set):
    start = time.perf_counter()
    func(ids)
    print(f"{func.__name__}: {time.perf_counter() - start:.4f} с")

unique_with_list: 1.9412 с
unique_with_set: 0.0021 с

Хоёр функц үгээр бараг ижил: []-ийн оронд set(), append-ийн оронд add. Гэвч 900 дахин ялгаатай. unique_with_list бол Хичээл 12.1-ийн pop(0)-ийн ах дүү: давталт бүр өсөн нэмэгдэж буй жагсаалтыг бүтнээр нь шалгана, тиймээс нийт ажил квадратаар өснө. unique_with_set давталт бүрт тогтмол зардалтай. result жагсаалтыг тусад нь хадгалсан нь дарааллыг хадгалахын тулд: set өөрөө элементүүдийн дарааллыг баталгаажуулдаггүй.

Энэ хүсэлтэд Python-д илүү товч арга бий: list(dict.fromkeys(ids)). dict нь Python 3.7-оос хойш түлхүүрүүдийг оруулсан дарааллаар нь хадгалдаг тул dict.fromkeys давхардлыг арилгаж, анхны дарааллыг хадгална. Энгийн list(set(ids)) ч давхардлыг арилгана, гэвч дараалал алдагдана.

Засвар 2: string нийлүүлэх — join

Олон жижиг string-ээс том текст бүтээх нь тайлан, log, HTML үүсгэхэд байнга тохиолддог. Хоёр арга:

python

def build_plus(pieces):
    text = ""
    for piece in pieces:
        text += piece
    return text


def build_join(pieces):
    return "".join(pieces)

String бол Python-д өөрчлөгддөггүй, immutable, объект: text += piece нь хуучин string-ийг өөрчлөхгүй, шинэ string үүсгэнэ. Онолоор бол энэ нь давталт бүрт өсөн нэмэгдэж буй текстийг бүтнээр нь хуулах тул квадрат өсөлттэй байх ёстой. Олон сурах бичиг тэгж бичдэг. Хэмжье, 20,000 хэсэг:

python

import time


class Report:
    def __init__(self):
        self.text = ""

    def add(self, piece):
        self.text += piece


pieces = [f"мөр {i}\n" for i in range(20_000)]

start = time.perf_counter()
build_plus(pieces)
print(f"local +=:     {time.perf_counter() - start:.4f} с")

start = time.perf_counter()
build_join(pieces)
print(f"join:         {time.perf_counter() - start:.4f} с")

start = time.perf_counter()
report = Report()
for piece in pieces:
    report.add(piece)
print(f"attribute +=: {time.perf_counter() - start:.4f} с")

local +=:     0.0021 с
join:         0.0012 с
attribute +=: 0.3804 с

Энэ хэмжилт сурах бичгийн дүрмийг хоёр чиглэлд засна. Функцийн дотоод хувьсагчид += гайхмаар хурдан, join-оос ердөө хоёр дахин удаан. Шалтгаан: CPython, бидний хэрэглэдэг стандарт Python, тусгай оновчлолтой. Хэрэв string-ийг өөр хэн ч хэрэглэхгүй бол хуулахын оронд байранд нь сунгадаг. Гэвч энэ оновчлол нөхцөлтэй: зөвхөн функцийн дотоод хувьсагчид ажилладаг. Report класс шиг объектын attribute-д тэр ажиллахгүй, бодит квадрат өсөлт буцаж ирж, 300 дахин удаан. Энэ оновчлол хэлний баталгаа биш, CPython-ий дотоод нарийн зүйл бөгөөд бусад Python хэрэгжүүлэлтүүдэд байхгүй байж болно.

Дүгнэлт: join үргэлж найдвартай хурдан. Хэдэн хэсгийг нийлүүлэхэд += эсвэл f-string бүрэн тохиромжтой, ойлгомжтой. Мянга, сая хэсэгт, ялангуяа attribute эсвэл олон функцээр дамжин текст бүтээхэд хэсгүүдийг list-д цуглуулж, төгсгөлд нь нэг join хий. Report-ийн засвар: self.parts = [], add-д self.parts.append(piece), текст хэрэгтэй үед "".join(self.parts).

Засвар 3: generator — эрт зогсох

Хичээл 2.2 ба 3.4-т generator-ийн гол ашгийг хэмжсэн: санах ой. Хурдны хувьд Хичээл 2.2-т шударга үр дүн гарсан: бүх элементийг нийлбэрлэх ажилд list comprehension generator-оос бага зэрэг хурдан. Generator-ийн хурдны жинхэнэ ашиг нэг тохиолдолд л гарна: бүх элементийг шаарддаггүй ажилд.

Сая захиалгаас том дүнтэй эхний захиалгыг олъё, тэр нь 100-р байрлалд байна:

python

import time

amounts = [1_000] * 1_000_000
amounts[100] = 500_000

start = time.perf_counter()
first = [a for a in amounts if a > 100_000][0]
print(f"list:      {time.perf_counter() - start:.6f} с")

start = time.perf_counter()
first = next(a for a in amounts if a > 100_000)
print(f"generator: {time.perf_counter() - start:.6f} с")

list:      0.021437 с
generator: 0.000006 с

List хувилбар сая элементийг бүгдийг шалгаж, жагсаалт бүтээгээд, эхнийхийг нь авна. Generator хувилбар 101 элемент шалгаад зогсоно: Хичээл 1.3-ын next() эхний утгыг авмагц ажил дуусна. any(), all(), next(), Хичээл 2.4-ын islice бүгд энэ эрт зогсолтыг ашигладаг. Хэрэв таарах элемент байхгүй бол хоёр хувилбар хоёулаа бүгдийг шалгах тул хурдны ялгаа алга, харин next() StopIteration шиднэ. next(..., None) гэж default өгвөл None буцаана.

Дүгнэлт: бүх өгөгдлийг боловсруулах ажилд generator хурдасгахгүй, санах ой хэмнэнэ. Эрт зогсож болох ажилд generator хурдасгана, заримдаа мянга дахин.

Засвар 4: cache — давталт бүр давтагдах үед л

Хичээл 3.3-т lru_cache fib(30)-ийг 2.7 сая дуудлагаас 31 дуудлага болгосон. Тэр гайхалтай жишээ, учир нь fib ижил аргументаар олон дахин дуудагддаг. Одоо эсрэг тохиолдлыг хэмжье: нэрийг хайлтад бэлтгэдэг хямд функц.

python

import time
from functools import lru_cache


def normalize(name):
    return name.strip().casefold()


@lru_cache(maxsize=None)
def normalize_cached(name):
    return name.strip().casefold()


distinct = [f" Хэрэглэгч-{i} " for i in range(100_000)]
repeated = [f" Хэрэглэгч-{i % 500} " for i in range(100_000)]

for label, data in (("ялгаатай", distinct), ("давтагдсан", repeated)):
    for func in (normalize, normalize_cached):
        start = time.perf_counter()
        for name in data:
            func(name)
        print(f"{label:<10} {func.__name__:<17} {time.perf_counter() - start:.4f} с")
    print(" ", normalize_cached.cache_info())
    normalize_cached.cache_clear()

maxsize=None нь cache-д хязгааргүй хэмжээ өгнө. cache_clear() нь хоёр туршилтын хооронд cache-ийг хоосолж, тэдгээрийг бие биенээсээ тусгаарлана.

ялгаатай   normalize         0.0118 с
ялгаатай   normalize_cached  0.0241 с
  CacheInfo(hits=0, misses=100000, maxsize=None, currsize=100000)
давтагдсан normalize         0.0117 с
  normalize_cached  0.0079 с
  CacheInfo(hits=99500, misses=500, maxsize=None, currsize=500)

Аргументууд бүгд ялгаатай үед cache хоёр дахин удаашруулсан: hits=0, нэг ч удаа ашиг өгөөгүй, харин 100,000 үр дүнг санах ойд хадгалсан. Аргументууд давтагдах үед 99.5 хувь нь cache-ээс ирсэн, гэвч хурд ердөө 1.5 дахин нэмэгдсэн. Яагаад fib шиг гайхалтай биш вэ? cache-ээс хайх өөрөө зардалтай: аргументын hash тооцоолох, dict-ээс хайх. normalize маш хямд тул түүнийг тооцоолох нь cache-ээс хайхаас бараг удаан биш.

Дүгнэлт: cache хоёр нөхцөл хангагдах үед ашигтай. Нэгдүгээрт, ижил аргументууд давтагдана: cache_info()-ийн hits үүнийг тоогоор харуулна. Хоёрдугаарт, функц cache-ээс хайхаас мэдэгдэхүйц үнэтэй: recursive тооцоолол, файл унших, сүлжээний хүсэлт. Аль нэг нь хангагдахгүй бол cache зөвхөн санах ой ба нарийн төвөгтэй байдал нэмнэ.

Дөрвөн засварын нийтлэг хэлбэр

Дөрвөн засвар бүгд зүйрлэлийн каталогийн хэлбэртэй: урьдчилсан зардал, дараа нь хурдан ажил. set бүтээх зардал олон хайлтаар нөхөгдөнө. join хэсгүүдийг жагсаалтад цуглуулах зардал бүхэл текстийг давтан хуулахгүй байх хэмнэлтээр нөхөгдөнө. generator тусдаа машин үүсгэх зардал эрт зогсолтоор нөхөгдөнө. cache санах ойн зардал давтагдсан тооцооллоор нөхөгдөнө. Тиймээс засвар бүрийн өмнө асуух асуулт ижил: урьдчилсан зардал хэдэн удаа нөхөгдөх вэ? Хариултыг таамаглахгүй, бодит өгөгдлийн хэмжээ дээр хэмжинэ.

Туршаад үзээрэй

Хүсвэл Засвар 1-ийн хайлтын хэмжилтийг 10, 100, 1,000, 10,000 элементтэй list ба set дээр давтаж, list хэдэн элементээс эхлэн мэдэгдэхүйц удаан болж байгааг олж үзээрэй. Сонирхвол Засвар 2-ын Report классыг parts жагсаалт ба join-оор засаж, хэмжилтээр батлах нь энэ хичээлийн загварыг бүрэн давтах дасгал. Мөн өөрийн өмнөх төслүүдээс давталт доторх in шалгалт эсвэл attribute-д += хийдэг газар хайж үзэх нь сонирхолтой: ийм загвар бодит кодонд гайхмаар олон тохиолддог. Эдгээр бүгд санал бөгөөд дараагийн хичээлүүд үүнийг хийсэн гэж үзэхгүй.

Түгээмэл алдаанууд

TypeError: unhashable type: ‘list’. “list төрөл hash хийгдэх боломжгүй” гэсэн утгатай. list эсвэл dict-ийг set-д нэмэх, dict-ийн түлхүүр болгох, эсвэл lru_cache-тэй функцэд дамжуулахад гарна. Каталогийн зүйрлэлээр: өөрчлөгдөж болох зүйлийн тавиурын дугаарыг тооцоолох боломжгүй, учир нь агуулга өөрчлөгдвөл дугаар өөрчлөгдөж, ном буруу тавиур дээр үлдэнэ. Шийдэл: list-ийг tuple болгох, seen.add(tuple(item)). Хичээл 7.4-ийн frozen dataclass ч hash хийгдэх боломжтой.

TypeError: sequence item 2: expected str instance, int found. "Дарааллын 2-р элемент: str хүлээсэн, int олдсон" гэсэн утгатай. join-д string биш элемент дамжуулахад гарна: join тоог автоматаар string болгодоггүй. Шийдэл: ", ".join(str(x) for x in values), эсвэл Засвар 3-ын generator-ийн хэв маягаар map(str, values).

Дараалал чимээгүй алдагдах. Мессежгүй. list(set(items))-ээр давхардлыг арилгахад үр дүн зөв элементүүдтэй, гэвч санамсаргүй мэт дараалалтай. Програмын бусад хэсэг дарааллаас хамаардаг бол алдаа огт өөр газар илэрнэ. Дарааллыг хадгалах шаардлагатай бол list(dict.fromkeys(items)).

Жижиг өгөгдөл дээр хэмжиж "ялгаа алга" гэж дүгнэх. Мессежгүй, хэмжилтийн алдаа. 100 элементтэй жагсаалтад unique_with_list ба unique_with_set хоёр хоёулаа нэг миллисекундээс бага зарцуулах тул "ялгаагүй" мэт харагдана. Квадрат өсөлтийн асуудал зөвхөн бодит хэмжээнд илэрдэг. Хичээл 12.1-ийн загвар: хэмжээг өөрчилж хэм.

cache-тэй функцийн буцаасан объектыг өөрчлөх. Мессежгүй, ноцтой алдаа. lru_cache-тэй функц list буцаадаг бол дуудлага бүр ижил list объектыг буцаана. Нэг газар түүнд append хийвэл cache дэх объект өөрчлөгдөж, дараагийн бүх дуудлага өөрчлөгдсөн утгыг авна. Хичээл 7.3-ын хуваалцсан mutable объектын урхитай ижил механизм. Cache-тэй функцээс tuple эсвэл frozen dataclass зэрэг өөрчлөгддөггүй утга буцаа.

Товч дүгнэлт

Python програмын удаан хэсгүүдийн ихэнх нь цөөн танил загвараас үүсдэг бөгөөд дөрвөн түгээмэл засвар бий. set ба dict элемент бүрийн hash-аар шууд байрлал руу очдог тул хайлтын хугацаа хэмжээнээс бараг хамаардаггүй, list элемент бүрийг шалгадаг. Гэвч set бүтээх нь зардалтай тул олон хайлтад л ашигтай. Давталт доторх list-ийн хайлт квадрат өсөлт үүсгэдэг. Дарааллыг хадгалан давхардал арилгахад dict.fromkeys. join олон хэсэг нийлүүлэхэд үргэлж найдвартай. CPython функцийн дотоод хувьсагчийн +=-ийг оновчилдог, attribute-ийнхыг биш. Generator санах ой хэмнэдэг ба зөвхөн эрт зогсож болох ажилд хурдасгадаг. Cache аргументууд давтагдаж, функц cache-ээс хайхаас мэдэгдэхүйц үнэтэй үед л ашигтай, cache_info()-ийн hits тоо үүнийг баталдаг. Дөрвөн засвар бүгд урьдчилсан зардал, дараа нь хурдан ажил гэсэн хэлбэртэй бөгөөд урьдчилсан зардал хэдэн удаа нөхөгдөхийг хэмжилт л хэлнэ.

Дараагийн хичээлээр Түвшин 4 дуусна. Бүлэг 10-ын typing, Бүлэг 11-ийн exception дизайн, энэ бүлгийн хэмжилтийн загвар гурвыг нэг бодит төсөлд нэгтгэж, өмнөх build-үүдийн адил Git branch, pytest тестүүд, commit-оор дуусгана.