Подходи на езика Python - забавен пример за оптимизация
Един ден приятел ми зададе един на пръв поглед прост въпрос: кой е най-добрият начин да преобразувам списък от цели числа в низ, ако приемем, че тези цели числа са във формат ASCII. Например, списъкът [97, 98, 99] трябва да бъде преобразуван в низа 'abc'. Да кажем, че искаме да напишем някаква функция за това.
Първият вариант, който измислих, беше откровено прост:
def f1 (списък): низ = "" за елемент в списъка: низ = низ + chr ( елемент ) връщащ низ
„Този метод може да не е най-бързият“, каза моят приятел. Какво ще кажете за нещо подобно:
def f2 (списък): връщане намалява (ламбда низ, елемент: низ + chr (елемент), списък, "")
Тази опция изпълнява абсолютно същия набор от операции с низове като предишната, но ние се отказахме от допълнителните разходи за цикъла for в полза на предполагаемо по-бързия неявен цикъл reduce().
„Разбира се“, отговорих аз, „но прави всичко това чрез извикване на функция (ламбда) на всеки елемент от списъка. Обзалагам се, че е по-бавно, тъй като извикването на функция в Python е по-сложно, отколкото цикъл.“
(Добре, вече сравних преди това: f2() отне 60% повече време от f1(). Подобно на това :-)
"Хм", каза моят приятел, "имам нужда от това, за да работи по-бързо." „Добре“, казах аз, „какво ще кажете за тази версия“:
def f3 (списък): низ = "" за знак в карта ( chr , списък): низ = низ + символ връщащ низ
За наша взаимна изненада, f3() беше два пъти по-бърз от f1()! Причината за нашата изненада беше двойна: първо, в този случай беше използвана повече памет (резултатът от извикването на map(chr, list) е друг списък със същата дължина); в-второ, той съдържа два цикъла вместо един (този във функцията map() и цикъла for).
Разбира се, пространството за сметка на времето е добре познат компромис, така че първото не трябва да ни изненадва. И все пак как два цикъла се оказват по-бързи от един? Причините за това са две.
Първо, във f1() вградената функция chr() се търси при всяка итерация, докато във f3() това се прави само веднъж (при обработка на аргумента map()). „Търсенията са относително скъпи“, казах на приятел, „защото правилата за динамично пространство от имена на Python търсят първо в общия речник на текущия модул (където се проваля) и след това във вградения речник (където намира това, което търси). По-лошото е, че неуспешното търсене в речника е средно малко по-бавно от успешното, поради естеството на верижното хеширане.“
Втората причина, поради която f3() е по-бърз от f1() е, че достъпът до chr(item), изпълняван от интерпретатора на байткод, вероятно е малко по-бавен, отколкото когато се извършва от функцията map() - интерпретаторът на байткод трябва да изпълни три инструкции за байткод за всеки достъп (зареждане 'chr', зареждане 'item', повикване), докато функцията map() прави всичко в C.
Всичко това ни доведе до идеята за компромис, който да ни позволи да не губим допълнително място, но ще ускори търсенето на функцията chr ():
def f4 (списък): низ = "" lchr = chr за елемент в списъка: низ = низ + lchr ( елемент ) връщащ низ
Както се очакваше, 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 (списък): низ = "" за i в диапазон (0, 256, 16): # 0, 16, 32,48, 64, . s = "" за знак в карта ( chr , списък[ i : i + 16 ]): s = s + символ низ = низ + s връщащ низ
За съжаление, за списък от 256 елемента, тази версия беше малко по-бавна (макар и не повече от 20%) от f3(). Тъй като писането на обща версия може само да забави нещата, ние не си направихме труда да обмислим тази посока по-нататък (освен че все пак я сравнихме с версията без карта (), която, разбира се, отново беше по-бавна).
В крайна сметка опитах коренно различен подход от предишните: използвайте само имплицитни цикли. Обърнете внимание, че цялата операция може да бъде описана по следния начин: прилагане на chr() към всеки от елементите на списъка; след това свържете получените знаци. Вече използвахме имплицитен цикъл за първата част: map(). За щастие модулът за низове има няколко внедрени в C функции за конкатенация на низове. По-специално, string.joinfields(list_of_strings, delimiter) свързва списък от низове, като поставя дадения разделител между всеки два низа. Нищо не ни попречи да свържем списък със знаци (които са просто низове с една дължина в Python), използвайки празния низ като разделител. Слушайте и гледайте:
импортиране на низ def f6 (списък): връщащ низ. joinfields (карта (chr, списък), "")
Тази функция беше четири до пет пъти по-бърза от най-бързия от основните си конкуренти, f3(). Освен това, той няма квадратичното поведение на предишните версии.
И стана победител.
На следващия ден си спомних една функция на езика Python: модулът масив. Този модул има операции за създаване на масив от еднобайтови цели числа от списък на Python с цели числа и всеки масив можеда бъдат записани във файл или преобразувани в низ като двоична структура от данни. Ето нашата функция, реализирана с помощта на тези операции:
импортиране на масив def f7 (списък): връщане array.array( 'b' , списък). низ ()
Това вече е три пъти по-бързо от f6() или 12-15 пъти по-бързо от f3()! Той също така използва по-малко междинна памет - разпределя само два обекта от N байта (плюс фиксирани режийни разходи), докато f6() започва с разпределяне на списък от N елемента, който обикновено струва 4N байта (8N байта на 64-битова машина) - при предположението, че символните обекти се споделят с подобни обекти в цялата програма (както за малки цели числа, Python кешира низове с единична дължина в повечето случаи).
"Спри", каза приятелят ми, "нека спрем, преди да получим отрицателно време за изпълнение - тази скорост е напълно достатъчна за моята програма." Съгласих се, въпреки че исках да опитам друг подход: да напиша цялата функция на C. Това ще помогне за минимизиране на изискванията за памет (ще разпредели низ с дължина N наведнъж) и ще спести няколко допълнителни инструкции в C кода, за които знаех, че са в модула на масива, тъй като е по-гъвкав (поддържа цели числа с ширина 1, 2 и 4 байта). Това обаче няма да избегне необходимостта да се извличат елементи от списъка един по един, както и да се получават C цели числа от тях: и двете операции са доста скъпи в API на Python-C, така че предположих в най-добрия случай леко ускоряване в сравнение с f7 (). Като се има предвид усилието, което ще отнеме да напиша и тествам разширението (в сравнение с добавянето на няколко реда на Python), и зависимостта от нестандартно разширение на Python, реших да не изследвам тази опция. Заключение
Ако имате остра нужда от скорост, обърнете се към вградените функции - не можете да създадете по-добър цикъл от този, написан на C. Потърсете функции, които правят това, от което се нуждаете, в ръководството на библиотеката за вградени функции. Ако няма такава функция, ето някои принципи за оптимизиране на цикли:
* Правило номер едно: оптимизирайте само ясно критични зони. Оптимизирайте само най-вътрешния цикъл. (Това правило съществува независимо от езика Python, но не е лошо да го повторите, тъй като може да спести много работа. :-) * Малкото е красиво. Предвид високите разходи за инструкции за байткод и търсене на променливи, рядко си струва да добавяте допълнителни проверки към кода си, за да спестите малко работа. * Използвайте вградени операции. Неявният цикъл в map() е по-бърз от изричния for цикъл; цикълът while с явен брояч на цикъл е още по-бавен. * Избягвайте да извиквате функции на Python във вътрешен цикъл. Това важи и за ламбда. Вграждането на вътрешния цикъл може да спести много време. * Локалните променливи се обработват по-бързо от глобалните; ако използвате глобална константа в цикъл, копирайте я в локална променлива преди цикъла. Освен това в Python функциите (глобални или вградени) също са глобални константи! * Опитайте да използвате map(), filter() или reduce(), за да замените изричен for цикъл, но само ако можете да използвате вградена функция: map() с вградена функция е по-бърза от for, но for с вграден код е по-бърза от map() с ламбда функция! * Проверете вашия алгоритъм за квадратично поведение. Но имайте предвид, че по-сложният алгоритъм се изплаща само в случай на големи стойности на N - за малки N сложността не еотплаща се. В нашия случай 256 беше достатъчно малък, за да може по-простата версия на функцията да остане най-бързата. Вашите разходи може да варират в зависимост от случая - струва си да проучите. * Не на последно място, събирайте данни. Отличният модул за профилиране на език Python може бързо да ви покаже тясно място във вашия код. Ако сравнявате различни версии на алгоритъм, тествайте го в кратък цикъл с помощта на функцията time.clock().
Между другото, ето функцията за отчитане на времето, която използвах. Той извиква функция f n*10 пъти с аргумент a и отпечатва името на функцията, последвано от необходимото време, закръглено до най-близката милисекунда. 10-те повторения се правят, за да се сведе до минимум натоварването на самата функция за синхронизация. Можете да отидете дори по-далеч и да направите 100 разговора. Обърнете внимание също, че изразът range(n) оценява извън обхвата на измерението, друг трик за минимизиране на режийните разходи, въведени от функцията за време. Ако сте загрижени за тези разходи, можете да ги калибрирате, като извикате функцията за време с празна (неправеща нищо) функция.
време за импортиране def време (f, n, a): печат f. __име__, r = диапазон (n) t1 = време. clock() за i в r: f ( a ); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f (a) t2 = време. clock() печат кръг ( t2 - t1 , 3 )
Няколко дни по-късно моят приятел отново дойде при мен с въпроса: как ще извършите обратната операция? Тези. създаване на списък с ASCII кодове от низ. О, не, ето ни отново, мина ми през ума.
Но този път всичко се оказа относително безболезнено. Имаше двама кандидати, очевидният:
def g1 (низ): карта за връщане ( ord , низ )
И малко по-малко очевидно:
импортиране на масив def g2 (низ): връщане array.array('b', низ). tolist()
Определянето на тяхното време на работа показа, че g2() е около пет пъти по-бърз от g1(). Въпреки че имаше уловка: g2() върна цели числа в интервала -128..127, докато g1() върна цели числа в интервала 0..255. Ако имате нужда от положителни числа, g1() ще бъде по-бърз от която и да е последваща обработка на резултатите, получени с g2(). (Забележка: тъй като това есе е написано, кодът от тип 'B' за неподписани байтове е добавен към модула на масива, така че вече няма причина да се предпочита g1()).