1 Востаннє редагувалося koala (14.01.2016 09:19:37)

Тема: Трохи про оптимізацію

Знайомий студіозус мені наскаржився, що йому викладач безпідставно, на його думку, знизив оцінку. Задача: знайти мінімум, максимум і їхні індекси в масиві. Рішення знайомого: вводимо дві змінні - індекси мінімума і максимума, в циклі перебираємо весь масив, повертаємо індекси і самі мінімум і максимум (див. FindMinMax нижче - це мій код, але ідея та сама). Викладач вимагав створити ще дві змінні - для мінімума і максимума (див. FindMinMaxCached). Нормально пояснити студенту, чому, він не зміг; я пропоную таке пояснення: уявіть собі, що масив на магнітній стрічці, тоді перемотування до поточних мінімума і максимума перетворять алгоритм складності O(n) на щось типу O(n*log(n)). Але, заради цікавості, вирішив накидати код на Python і порівняти різні алгоритми.

Очікування:

t(FindMinMax) > t(FindMinMaxCached) > t(FindMinMaxPythonic) > t(FindMinMaxFast)
Код:
import random
import time
import timeit

def FindMinMax(bigArray):
    minIndex = 0
    maxIndex = 0
    for i in range(len(bigArray)):
        if bigArray[i] > bigArray[maxIndex]:
            maxIndex = i
        if bigArray[i] < bigArray[minIndex]:
            minIndex = i
    return minIndex,bigArray[minIndex],maxIndex,bigArray[maxIndex]

def FindMinMaxCached(bigArray):
    minIndex = 0
    maxIndex = 0
    minValue = bigArray[0]
    maxValue = bigArray[0]
    for i in range(len(bigArray)):
        if bigArray[i] > maxValue:
            maxIndex = i
            maxValue = bigArray[i]
        if bigArray[i] < minValue:
            minIndex = i
            minValue = bigArray[i]
    return minIndex,minValue,maxIndex,maxValue

def FindMinMaxPythonic(bigArray):
    minValue = min(bigArray)
    maxValue = max(bigArray)
    return bigArray.index(minValue), minValue, bigArray.index(maxValue), maxValue

def FindMinMaxFast(bigArray):
    minIndex = min(range(len(bigArray)), key=bigArray.__getitem__)
    maxIndex = max(range(len(bigArray)), key=bigArray.__getitem__)
    return minIndex, bigArray[minIndex], maxIndex, bigArray[maxIndex]

def genArray(size):
    random.seed()
    return [random.randint(-2000000000,2000000000) for i in range(size)]


def test():
    bigArray = genArray(1000000)
    r1 = FindMinMax(bigArray)
    r2 = FindMinMaxCached(bigArray)
    r3 = FindMinMaxPythonic(bigArray)
    r4 = FindMinMaxFast(bigArray)
    if r1 == r2 == r3 == r4:
        print("All ok!")
    else:
        print(r1,r2,r3,r4,"not equal!")

test()

def callTimeit(func):
    print(func+':')
    print(timeit.timeit(func+'(genArray(10000000))', 'from __main__ import genArray,'+func, time.process_time, 5))

for func in ['FindMinMax','FindMinMaxCached','FindMinMaxPythonic','FindMinMaxFast']:
    callTimeit(func)

Результат:

All ok!
FindMinMax:
156.7342047
FindMinMaxCached:
153.25538239999997
FindMinMaxPythonic:
148.37255109999995
FindMinMaxFast:
155.92299950000006

Насправді:

t(FindMinMax) > t(FindMinMaxFast) > t(FindMinMaxCached) > t(FindMinMaxPythonic) 

Як бачимо, варіант з зайвими змінними дійсно трохи швидший, хоча й незначно (завдяки, як я розумію, процесорному кешу, в якому зберігаються ті самі значення). Третій варіант - FindMinMaxPythonic- я додав, як демонстрацію неефективності "пітонячого" способу: спершу шукаємо min і max, а потім - їхні індекси. Все коротко і просто, щоправда, там має бути два зайвих цикли... але виходить найшвидше. Гадаю, це завдяки оптимізації стандартних функцій, треба буде порівняти з C++ чи асемблером на дозвіллі. Останній варіант - FindMinMaxFast - я планував як "покращений пітонячий спосіб": стандартної функції пошуку індексу максимального елемента немає, її доводиться формувати саме так, але це (думав я) буде швидше, ніж два цикли в FindMinMaxPythonic. Не так сталося, як гадалося - результат гірший навіть за варіант з 4-ма змінними.

Короткий висновок: без профайлінгу немає сенсу оптимізувати код по швидкості, а добре читаний код кращий за той, що видається швидким, але його важко читати.

Подякували: leofun01, Master_Sergius, 0xDADA11C73

2

Re: Трохи про оптимізацію

Як бачимо, варіант з зайвими змінними дійсно трохи швидший, хоча й незначно (завдяки, як я розумію, процесорному кешу, в якому зберігаються ті самі значення)

Це не пояснює, чому так довго працював перший варіант - він пройшов мільйон елементів масиву, індексуючи кожен елемент, але 1.5% часу потратив на те, щоб просто його ще два рази проіндексувати.

3

Re: Трохи про оптимізацію

Просто отак підряд запустити один раз - це ще не показник (як то кажуть - раз не пдрс). Так як ніякий процес не відбувається у повному вакуумі - у самій ОС відбуваються купи процесів. Потрібно заміряти середнє із хоча би 3 запусків.

Подякували: leofun011

4

Re: Трохи про оптимізацію

Master_Sergius написав:

Просто отак підряд запустити один раз - це ще не показник (як то кажуть - раз не пдрс). Так як ніякий процес не відбувається у повному вакуумі - у самій ОС відбуваються купи процесів. Потрібно заміряти середнє із хоча би 3 запусків.

А ви уважніше подивіться, як я його запускаю.

Подякували: Master_Sergius, leofun012

5

Re: Трохи про оптимізацію

Подивився. Грішний, каюсь. Треба знов сісти за парту :)

6 Востаннє редагувалося koala (14.01.2016 15:27:38)

Re: Трохи про оптимізацію

quez написав:

Як бачимо, варіант з зайвими змінними дійсно трохи швидший, хоча й незначно (завдяки, як я розумію, процесорному кешу, в якому зберігаються ті самі значення)

Це не пояснює, чому так довго працював перший варіант - він пройшов мільйон елементів масиву, індексуючи кожен елемент, але 1.5% часу потратив на те, щоб просто його ще два рази проіндексувати.

Які саме ви маєте на увазі?

Просто роздуми про L1 cache для FindMinMax/FindMinMaxCached. Швидкість виконання обох кодів на процесорі майже ідентична (в другому буде щось типу log(N) додаткових змін змінних, гадаю, це не вони впливають).
FindMinMax - 2 змінні, звертання до 3 елементів масиву за ітерацію.
FindMinMaxCached - 4 змінних, звертання до 1 елементів за ітерацію.
Щоб звернутися до довільного елементу масиву, треба завантажити в кеш весь параграф (line). На моєму A8-3850 64КБ кешу L1 на ядро, 64 байти на параграф. Тобто зайвий елемент масиву займає 1 параграф кешу. Певна кількість параграфів буде зайнята додатковими даними від Python-у, i та range та кодом. Отже, FindMinMaxCached займає до 1 додаткового параграфу змінними, але швидше за все навіть не займає (8 додаткових байт потребуватимуть 1 параграф з імовірністю 1/8 - якщо потраплять на межу), а FindMinMax займає 2 додаткових параграфи кешу. Досить суттєво, щоб збільшити кількість кеш-промахів.

7

Re: Трохи про оптимізацію

Не звертайте уваги, я код прочитав не очима, а чимось іншим. День якийсь не такий, чи що...

8 Востаннє редагувалося koala (14.01.2016 22:56:34)

Re: Трохи про оптимізацію

А тепер - C++!

Код
#include <iostream>  //cout
#include <cstdlib>   //srand
#include <ctime>     //time
#include <tuple>     //tuple
#include <algorithm> //min_element, max_element
#include <windows.h>

using namespace std;

typedef tuple<size_t, int,size_t, int> result;

void createArray(int *tgt, size_t size)
{
    for(size_t i = 0; i < size; ++i) {
        tgt[i] = rand();
    }
}

result findMinMax(int *tgt,size_t size){
    size_t imin = 0, imax = 0;
    for(size_t i = 0; i < size; ++i) {
        if( tgt[imin] > tgt[i] ) {
            imin = i;
        }
        if( tgt[imax] < tgt[i] ) {
            imax = i;
        }
    }
    return result(imin,tgt[imin],imax,tgt[imax]);
}

result findMinMaxCached(int *tgt,size_t size){
    size_t imin = 0, imax = 0;
    int min = tgt[0],max = tgt[0];
    for(size_t i = 0; i < size; ++i) {
        if( min > tgt[i] ) {
            min = tgt[i];
            imin = i;
        }
        if( max < tgt[i] ) {
            max = tgt[i];
            imax = i;
        }
    }
    return result(imin,tgt[imin],imax,tgt[imax]);
}

result findMinMaxStd(int *tgt,size_t size){
    int *ptr_min = min_element(tgt,tgt+size);
    int *ptr_max = max_element(tgt,tgt+size);
    return result(ptr_min-tgt, *ptr_min, ptr_max-tgt, *ptr_max);
}

typedef result (*func)(int*,size_t);

void test(func f, int count, size_t size){
    LARGE_INTEGER  total_time;
    total_time.QuadPart = 0;
    for(int i = 0; i < count; ++i){
        int *tgt = new int[size];
        createArray(tgt, size);
        LARGE_INTEGER start;
        QueryPerformanceCounter (&start);
        (*f)(tgt,size);
        LARGE_INTEGER end;
        QueryPerformanceCounter (&end);
        total_time.QuadPart += end.QuadPart - start.QuadPart;
        delete tgt;
    }
    total_time.QuadPart /= count;
    LARGE_INTEGER Frequency;
    QueryPerformanceFrequency(&Frequency);
    cout<<((double)total_time.QuadPart/Frequency.QuadPart)<<endl;
}

int main()
{
    srand(time(0));
    tuple<const char *,func> functions[] =
        {
            make_tuple("findMinMaxStd",findMinMaxStd),
            make_tuple("findMinMaxCached",findMinMaxCached),
            make_tuple("findMinMax",findMinMax)
        };
    for(auto f: functions){
        cout << get<0>(f) <<endl;
        test( get<1>(f),5,10000000);
    }
}
результат

findMinMaxStd
0.0890707
findMinMaxCached
0.0753431
findMinMax
0.0653551

Щось мені знову Python перестав подобатися :(
Піду подепресую, чи що...

P.S. Я вчора забув поділити результат на кількість спроб - там не 150 секунд, а 30. І тим не менш...

Подякували: leofun011

9

Re: Трохи про оптимізацію

Оптимізував код (-O3).

оптимізований результат

findMinMaxStd
0.0190281
findMinMaxCached
0.0263326
findMinMax
0.0189701

Подякували: leofun011

10 Востаннє редагувалося koala (14.01.2016 23:51:59)

Re: Трохи про оптимізацію

Кому цікаво - заміна на кортежі (tuple) в пітоні ніц не змінює в межах трьох знаків.

виправлений код
def genArray(size):
    random.seed()
    return tuple(random.randint(-2000000000,2000000000) for i in range(size))

def callTimeit(func):
    print(func+':')
    funcname = func+'(genArray(10000000))'
    setup = 'from __main__ import genArray,'+func
    print(timeit.timeit(funcname, setup, time.process_time, 5)/5)
результат

All ok!
FindMinMax:
31.8554042
FindMinMaxCached:
31.275080479999996
FindMinMaxPythonic:
30.24235386
FindMinMaxFast:
31.55276226000001

Подякували: leofun01, ping2

11

Re: Трохи про оптимізацію

Варік на PHP )

$array = ['q'=>10, 't'=>1, 'w'=>20];
$max = max($array);
$min = min($array);
echo array_search($max, $array); //w
echo array_search($min, $array); //t

12

Re: Трохи про оптимізацію

VTrim написав:

Варік на PHP )

$array = ['q'=>10, 't'=>1, 'w'=>20];
$max = max($array);
$min = min($array);
echo array_search($max, $array); //w
echo array_search($min, $array); //t

А можете протестувати варіанти?

13 Востаннє редагувалося VTrim (15.01.2016 10:09:19)

Re: Трохи про оптимізацію

koala написав:
VTrim написав:

Варік на PHP )

$array = ['q'=>10, 't'=>1, 'w'=>20];
$max = max($array);
$min = min($array);
echo array_search($max, $array); //w
echo array_search($min, $array); //t

А можете протестувати варіанти?

В принципі можу,але як мені здається цей варіант "з коробки" буде все рівно працювати швидше,аніж перебір масиву мною. Оскільки на C. Так?
Хоча не знаю що там під капотом функції.
Свій варіант такий.

$array = ['q'=>10, 't'=>1, 'w'=>20];
$max = max($array);
$min = min($array);
              
foreach($array as $key => $value) {
    if($value == $max) echo $key;
    if($value == $min) echo $key;
}

14

Re: Трохи про оптимізацію

У вас трохи інша структура даних - словник, а не масив. PHP приховує різницю, але вона існує.

15

Re: Трохи про оптимізацію

Маєте на увазі [10,1,20] ,то ключ для min має бути 1, а для max - 2 ?

16

Re: Трохи про оптимізацію

Так. Масив не зберігає своїх ключів, а прямо відображає їх на пам'ять, це значно швидше.

17

Re: Трохи про оптимізацію

Ну такий варіант теж працює.

$array = [10, 1, 20];
$max = max($array);
$min = min($array);
echo array_search($max, $array); //2
echo array_search($min, $array); //1

18

Re: Трохи про оптимізацію

Згадав PHP...

Прихований текст
<?php
function findMinMax(&$arr)
{
    $imin = 0;
    $imax = 0;
    for( $i=0; $i < count($arr); $i++ ){
        if( $arr[$i] < $arr[$imin] ){
            $imin = $i;
        }
        if( $arr[$i] > $arr[$imax] ){
            $imax = $i;
        }
    }
    return [$imin, $arr[$imin], $imax, $arr[$imax]];
}

function findMinMaxCached(&$arr)
{
    $imin = 0;
    $imax = 0;
    $min = 0;
    $max = 0;
    for( $i=0; $i < count($arr); $i++ ){
        if( $arr[$i] < $min ){
            $imin = $i;
            $min = $arr[$i];
        }
        if( $arr[$i] > $max ){
            $imax = $i;
            $max = $arr[$i];
        }
    }
    return [$imin, $min, $imax, $max];
}

function findMinMaxStandard(&$arr)
{
    $min = min($arr);
    $max = max($arr);
    return [array_search($min,$arr),$min,array_search($max,$arr),$max];
}

function fillArray(&$arr,$size)
{
    for($i=0;$i<$size;++$i) {
        $arr[$i]=rand();
    }
    return $arr;
}

function test($func,$count,$size,&$arr)
{
    $time = 0;
    for($i = 0;$i<$count;++$i)
    {
        $arr = fillArray($arr,$size);
        $start = microtime(true);
        $func($arr);
        $time += microtime(true) - $start;
    }
    $time/=5;
    echo $time.PHP_EOL;
}

$funcs = ["findMinMax","findMinMaxCached","findMinMaxStandard"];
foreach($funcs as $func) {
    $arr = [];
    echo $func.PHP_EOL;
    test($func,5,10000000,$arr);
}

Результати треба орієнтовно на 2 множити, це інший комп:

Прихований текст

findMinMax
0.86228623390198
findMinMaxCached
0.61166095733643
findMinMaxStandard
0.17181696891785

19

Re: Трохи про оптимізацію

Ну так як я і казав. Вбудовані працюють швидше.

20 Востаннє редагувалося ADR (02.02.2016 00:38:09)

Re: Трохи про оптимізацію

Ви "трішки" не те рахуєте)
(але я числа зменшив. влом стільки чекати)

Оновіть, будь ласка, дані на своєму компі. (цікавить порівняння із С++)

Прихований текст

[code=python]
import random
import time
import timeit

def FindMinMax(bigArray):
    minIndex = 0
    maxIndex = 0
    for i in range(len(bigArray)):
        if bigArray[i] > bigArray[maxIndex]:
            maxIndex = i
        if bigArray[i] < bigArray[minIndex]:
            minIndex = i
    return minIndex,bigArray[minIndex],maxIndex,bigArray[maxIndex]

def FindMinMaxCached(bigArray):
    minIndex = 0
    maxIndex = 0
    minValue = bigArray[0]
    maxValue = bigArray[0]
    for i in range(len(bigArray)):
        if bigArray[i] > maxValue:
            maxIndex = i
            maxValue = bigArray[i]
        if bigArray[i] < minValue:
            minIndex = i
            minValue = bigArray[i]
    return minIndex,minValue,maxIndex,maxValue

def FindMinMaxPythonic(bigArray):
    minValue = min(bigArray)
    maxValue = max(bigArray)
    return bigArray.index(minValue), minValue, bigArray.index(maxValue), maxValue

def FindMinMaxFast(bigArray):
    minIndex = min(range(len(bigArray)), key=bigArray.__getitem__)
    maxIndex = max(range(len(bigArray)), key=bigArray.__getitem__)
    return minIndex, bigArray[minIndex], maxIndex, bigArray[maxIndex]

def genArray(size):
    random.seed()
    return [random.randint(-2000000000,2000000000) for i in range(size)]


def test():
    bigArray = genArray(1000000)
    r1 = FindMinMax(bigArray)
    r2 = FindMinMaxCached(bigArray)
    r3 = FindMinMaxPythonic(bigArray)
    r4 = FindMinMaxFast(bigArray)
    if r1 == r2 == r3 == r4:
        print("All ok!")
    else:
        print(r1,r2,r3,r4,"not equal!")

test()

sampleArray = genArray(100000)

def callTimeit(func):
    print(func+':')
    print('\tall: ', timeit.timeit(
            func+'(genArray(100000))', 'from __main__ import genArray,'+func, time.process_time, 5)/5)
    print('\tgenArray: ',
          timeit.timeit('genArray(100000)', 'from __main__ import genArray,'+func, time.process_time, 5)/5)
    print('\tfindMinMax: ',
          timeit.timeit(func+'(sampleArray)', 'from __main__ import genArray; from __main__ import sampleArray,'+func,
                        time.process_time, 5)/5)

for func in ['FindMinMax','FindMinMaxCached','FindMinMaxPythonic','FindMinMaxFast']:
    callTimeit(func)
[/code]

Прихований текст

All ok!
FindMinMax:
  all:  0.21450988440000004
  genArray:  0.19718003080000007
  findMinMax:  0.020288479400000094
FindMinMaxCached:
  all:  0.2080217414
  genArray:  0.19314022860000007
  findMinMax:  0.01581712660000001
FindMinMaxPythonic:
  all:  0.2011791422
  genArray:  0.19367534219999988
  findMinMax:  0.00863502700000005
FindMinMaxFast:
  all:  0.21154788939999988
  genArray:  0.19302947639999993
  findMinMax:  0.020088932599999866

Подякували: koala1