Підходи мови Python – кумедний приклад оптимізації.
Одного разу приятель поставив мені, здавалося б, просте питання: як найкраще перетворити список цілих чисел у рядок, припускаючи, що ці цифри представлені у форматі ASCII. Наприклад, список [97, 98, 99] має бути перетворений на рядок 'abc'. Допустимо, що ми хочемо написати для цього деяку функцію.
Перший варіант, який я вигадав, був відверто простим:
def f1 (list): string = "" for item in list: string = string + chr ( item ) return string
"Цей спосіб не може бути найшвидшим," - сказав мій приятель. Як щодо такого:
def f2 (list): return reduce ( lambda string , item : string + chr ( item ), list, "")
Цей варіант виконує точно той самий набір рядкових операцій, як і попередній, але тут відмовилися від накладних витрат виконання циклу for на користь, як передбачалося, швидшого неявного циклу функції reduce().
"Звичайно,"- відповів я, - "але він робить все це за рахунок виклику функції (lambda) для кожного елемента списку. Можу сперечатися, що це повільніше, адже виклик функції в мові Python вимагає більших витрат, ніж цикл".
(Добре, я вже порівняв перед цим: f2() зажадала на 60% більше часу, ніж f1(). Ось так :-)
"Хмм," - сказав мій знайомий - "Мені потрібно, щоб усе це працювало швидше". "Добре," - сказав я, - "як щодо такої версії":
def f3 (list): string = "" for character in map (chr, list): string = string + character return string
На взаємне подив, f3() виявилася вдвічі швидше, ніж f1()! Причина нашого подиву була двоякою: по-перше, у цьому випадку використовувався більший обсяг пам'яті (результат виклику map(chr, list) є ще одним списком тієї ж довжини); по-друге, тут містилося два цикли замість одного (той, що укладено у функції map(), і цикл for).
Безумовно, простір за рахунок часу – це відомий компроміс, тож перше не мало нас здивувати. І все ж таки як два цикли виявилися швидше, ніж один? Тому є дві причини.
По-перше, в f1() вбудована функції chr() шукається при кожній ітерації, тоді як f3() це робиться тільки один раз (при обробці аргументу map()). "Пошук щодо доріг," - сказав я приятелю- "оскільки правила динамічної області імен Python припускають пошук спочатку в загальному словнику поточного модуля (де він виявляється невдалим), а потім у словнику вбудованих функцій (де і знаходять шукане). невдалий словниковий пошук у середньому трохи повільніший, ніж успішний, через особливості ланцюжкового хешування.
Друга причина того, що f3() швидше, ніж f1(), полягає в тому, що звернення до chr(item), яке виконується інтерпретатором байт-коду, ймовірно, трохи повільніше, ніж коли це робиться функцією map() - інтерпретатору байт- коду доводиться виконувати три байт-кодові інструкції для кожного звернення (load 'chr', load 'item', call), тоді як функція map() робить це все на C.
Все це призвело до ідеї компромісу, який дозволив би не витрачати зайвий простір, але прискорив би пошук функції chr():
def f4 (list): string = "" lchr = chr for item in list: string = string + lchr ( item ) return string
Як і очікувалося, f4() виявилася повільнішою, ніж f3(), але тільки на 25%; і все ж таки була приблизно на 40% швидше, ніж f1(). Так вийшло тому, що пошук локальних змінних відбувається швидше, ніж пошук глобальних або вбудованих змінних: "компілятор" мови Python оптимізує більшу частину функцій такимТаким чином, для локальних змінних не потрібно пошуку в словнику, а досить простої індексації масиву. Відносна швидкість f4() порівняно з f1() і f3() передбачає існування обох названих вище причин швидкої роботи функції f3(), проте перша причина (менше пошуків) трохи важливіше. (Щоб отримати більш точні дані про це, ми мали б вкомпілювати відповідні можливості в інтерпретатор).
Тим не менш, наш найкращий варіант, f3(), до цих пір був лише вдвічі швидше, ніж саме прямолінійне рішення, f1(). Чи могли ми щось покращити?
Я турбувався, що квадратична поведінка алгоритму нас погубить. До цих пір ми використовували як тестові дані список з 256 цілих чисел, оскільки саме для цього моєму знайомому і потрібна була функція, що розглядається. Але що було б, якщо застосувати її до списку двох тисяч символів? Ми з'єднували б все більш і більш довгі рядки, по одному символу за раз. Легко бачити, що крім накладних витрат, щоб створити таким чином список довжиною N, доведеться копіювати 1 + 2 + 3 + . + (N-1) символів або N*(N-1)/2, або 0.5*N**2 - 0.5*N. Крім того, існує N операцій виділення рядка, проте для досить великого N елемент, що містить N**2, перевершує накладні витрати ці операції. Дійсно, для списку в 2048 елементів, який у 8 разів довший за тестовий, кожна з цих функцій виконується повільніше набагато більше, ніж у 8 разів; фактично, ближче до 16. Я не наважився спробувати список, у 64 рази довший за тестовий.
Щоб уникнути квадратичного поведінки подібних алгоритмів, існує загальний підхід. Я записав його для рядків, що складаються точно з 256 елементів:
def f5 (list): string = "" for i in range ( 0 , 256 , 16 ): # 0, 16, 32,48, 64, . s = "" for character in map ( chr , list[ i : i + 16 ]): s = s + character string = string + s return string
На жаль, для списку з 256 елементів ця версія працювала трохи повільніше (хоча і не більше ніж на 20%), ніж f3(). Оскільки написання загальної версії могло тільки сповільнити процес, ми не стали турбуватися про те, щоб далі розглядати цей напрямок (за винятком того, що ми все ж таки порівняли його з варіантом, що не використовує map(), який, звичайно ж, знову виявився повільнішим) .
Зрештою, я спробував радикально відмінний від попередніх підхід: використовувати тільки неявні цикли. Зауважте, що вся операція загалом може бути описана таким чином: застосувати chr() до кожного з елементів списку; потім конкатенувати отримані символи. Ми вже використовували неявний цикл першої частини: map(). На щастя, у рядковому модулі є кілька реалізованих на З функцій конкатенації рядків. Зокрема, string.joinfields(list_of_strings, delimiter) конкатенує список рядків, розміщуючи заданий роздільник між кожними двома рядками. Ніщо не заважало нам зробити конкатенацію списку символів (які лише рядки одиничної довжини в мові Python), використовуючи порожній рядок як роздільник. Слухайте і дивіться:
import string def f6 (list): return string . joinfields ( map ( chr , list), " " )
Ця функція працювала у чотири-п'ять разів швидше, ніж найшвидший з її головних суперників, f3(). Більше того, вона не має квадратичної поведінки колишніх версій.
І переможцем став.
Наступного дня я згадав про одну особливість мови Python: модуль array. Цей модуль має операції створення масиву однобайтових цілих чисел зі списку цілих чисел мови Python, і кожен масив можебути записаний у файл або перетворений на рядок як бінарна структура даних. Ось наша функція, реалізована з використанням цих операцій:
import array f7 (list): return array.array( 'b' , list). tostring()
Це вже втричі швидше ніж f6(), або в 12-15 разів швидше ніж f3()! Тут також використаний менший об'єм проміжної пам'яті - виділяються лише два об'єкти з N байт (плюс фіксовані накладні витрати), тоді як f6() починає з виділення списку з N елементів, яке зазвичай коштує 4N байт (8N байт на 64-бітній машині) - в припущенні, що символьні об'єкти поділяються з подібними об'єктами всюди в програмі (як для малих цілих чисел, як правило, Python кешує рядки одиничної довжини).
"Стоп," - сказав мій знайомий - "зупинимося, поки ми не отримали негативного часу виконання - такої швидкості цілком достатньо для моєї програми". Я погодився, хоча мені хотілося спробувати ще один підхід: написати всю функцію на С. Це допомогло б мінімізувати потреби в об'ємі пам'яті (вона виділятиме відразу рядок довжини N) та заощадити кілька зайвих інструкцій у коді на С, які, як я знав, були в модулі array, тому що він більш універсальний (підтримує цілі числа шириною 1, 2 і 4 байти). Тим не менш, при цьому не вдалося б уникнути необхідності витягувати елементи зі списку по одному, а також отримувати з них цілі числа: обидві ці операції є досить дорогими в Python-C API, так що я припускав у кращому випадку невелике прискорення в порівнянні з f7(). Зважаючи на зусилля, які необхідно було б витратити на написання та тестування розширення (порівняно з накиданням пари рядків на Python), та залежність від нестандартного розширення Python, я вирішив не дослідити цей варіант. Висновок
Якщо вам потрібна швидкість, зверніться до вбудованих функцій - ви не зможете створити цикл краще, ніж написаний на С. Пошукайте функції, що роблять те, що вам потрібно, в бібліотечному посібнику з вбудованих функцій. Якщо там немає такої функції, наведені нижче деякі принципи оптимізації циклів:
* Правило номер один: оптимізуйте тільки критичні ділянки. Оптимізуйте лише внутрішній цикл. (Це правило існує незалежно від мови Python, але нешкідливо його повторити, оскільки воно може заощадити багато роботи. :-) * Маленьке красиво. Враховуючи високі накладні витрати на байт-кодові інструкції та пошук змінних, рідко варто додавати до коду додаткові перевірки для економії невеликої роботи. * Використовуйте вбудовані операції. Неявний цикл map() працює швидше, ніж явний цикл for; цикл while з явним лічильником циклу працює ще повільніше. * Уникайте виклику функцій, написаних на Python, у внутрішньому циклі. Це стосується і lambda. Розгорнення (inlining) внутрішнього циклу може заощадити багато часу. * Локальні змінні обробляються швидше, ніж глобальні; Якщо ви використовуєте глобальну константу в циклі, скопіюйте її у локальну змінну перед циклом. Крім того, у мові Python функції (глобальні чи вбудовані) також є глобальними константами! * Спробуйте використовувати map(), filter() або reduce() для заміни явного циклу for, але тільки якщо ви можете використовувати вбудовану функцію: map() із вбудованою функцією швидше for, проте for з розгорнутим (in-line) кодом швидше, ніж map() з функцією lambda! * Перевірте ваш алгоритм на квадратичну поведінку. Але зауважте, що складніший алгоритм окупається лише у разі великих значень N - для маленьких N складність неокупається. У нашому випадку 256 виявилося досить маленьким значенням для того, щоб простіша версія функції залишалася найшвидшою. Ваші витрати у різних випадках можуть відрізнятися – це варто дослідити. * І останнє за згадкою, але не за значенням: збирайте дані. Чудовий модуль профілювання мови Python може швидко продемонструвати вам вузьке місце у вашому коді. Якщо ви порівняєте різні версії деякого алгоритму, тестуйте його в короткому циклі, використовуючи функцію time.clock().
До речі, ось функція хронометражу, яку я використовував. Вона викликає функцію f n * 10 разів з аргументом a, і друкує ім'я функції і слідом - час, який вона відпрацювала, округлений до мілісекунд. 10 повторних викликів робляться для мінімізації накладних витрат функції хронометражу. Ви можете піти навіть далі і зробити 100 дзвінків. Зауважте також, що вираз range(n) розраховується поза рамками вимірювання - інший прийом мінімізації витрат, що вносяться функцією хронометражу. Якщо ви стурбовані цими витратами, ви можете відкалібрувати їх за допомогою виклику функції хронометражу з порожньою (що нічого не робить) функцією.
import time def timing (f, n, a): print f. __name__, r = range (n) t1 = time. clock () for i in r : f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a) t2 = time. clock () print round (t2 - t1, 3)
Декількома днями пізніше мій приятель знову звернувся до мене з питанням: як ти зробиш зворотну операцію? Тобто. створення списку ASCII-кодів із рядка. О ні, ось ми й знову тут, промайнуло у мене в голові.
Але цього разу виявилося відносно безболісним. Було два кандидати, очевидний:
def g1 (string): return map (ord, string)
І дещо менш очевидний:
import array def g2 (string): return array.array( 'b' , string ). tolist ()
Визначення часу їхньої роботи показало, що g2() приблизно в п'ять разів швидше, ніж g1(). Хоча була і пастка: g2() повертала цілі числа інтервалі -128..127, тоді як g1() повертала цілі числа інтервалі 0..255. Якщо вам потрібні позитивні числа, g1() буде швидше, ніж будь-яка постобробка результатів, отриманих за допомогою g2(). (Примітка: з тих пір, як було написано це есе, модуль array був доданий код типу 'B' для беззнакових байт, таким чином тепер більше немає підстав для переваги функції g1()).