Chwalipięta, czyli bardzo krótka opowieść o optymalizacji

W ramach służbowych zajęć musiałem kiedyś stworzyć proces, który wylicza średnie bieżące koszty obsługi niektórych produktów. Oczywiście nie były to ot, takie sobie „zwykłe” średnie, bardziej wartości zbliżone znaczeniowo do średnich, ale wyliczane w dość zawiły sposób. Bez wchodzenia w szczegóły, powiem tylko, że obliczenia obejmowały kilka wartości z poprzednich wierszy, trochę „na krzyż” (a więc, w zależności od wariantu, użyć wartości z kolumny A do wyliczenia innej wartości w kolumnie B lub na odwrót) i tak dalej. Liczby wynikowe różniły się od „klasycznych” średnich gdzieś tam na drugim miejscu po przecinku, ale jak wiadomo przy odpowiednio wielkiej skali nawet ułamek procenta może zaoszczędzić miliony, więc gra była warta świeczki.

Model obliczeniowy był bardzo prosty do wykonania w Excelu – i taką też wersję dostałem, wraz z porcją danych testowych z poprawnymi wynikami – żebym sobie mógł zweryfikować moje obliczenia.

Spojrzałem na te excelowe karkusze (czyli po naszemu arkusze kalkulacyjne) i stwierdziłem, że phi, błahostka, szympans by to zrobił lewą ręką, drapiąc się prawą po… mniejsza o to.

Obiecałem pokazać pierwsze wyniki nazajutrz.

Trzy dni potem, spływając potem, ciągle byłem na początku drogi. Co gorsza, bazując na mojej obietnicy, jacyś wysoko postawieni Mądrale już naobiecywali innym, jeszcze wyżej postawionym Mądralom, że praktycznie już mamy działający gotowiec, tylko jeszcze musimy zrobić parę końcowych testów.

Na czym polegał problem?

Problem polegał na tym, że obliczenia trzeba było wykonywać wiersz po wierszu. Rekord po rekordzie. Nie dało się zastosować tak kochanej przez SQL-a algebry zbiorów. Albo inaczej: może by się i dało, ale nijak nie potrafiłem tego wykombinować.

Ponieważ terminy goniły, zabrałem się za rozwiązanie problemu od początku, tym razem bardziej systematycznie. Ponieważ dane wejściowe szły w setki milionów rekordów, podzieliłem je sobie na paczki wedle klienta i rodzaju artykułu (raptem coś ze trzy miliony takich paczek) i zbudowałem logikę, która – rekord po rekordzie – pracowicie odtwarzała excelowe formuły.

I co?

I udało mi się. Dla pojedynczej paczki danych zacząłem wreszcie dostawać poprawne wyniki dla każdego możliwego i niemożliwego scenariusza. Z tym, że pojedyncza paczka wykonywała się na tyle długo, że na zakończenie obliczeń musiałbym czekać prawie dwie doby.

Niedobrze.

I tu zapaliła mi się nad głową duża, żółta żarówka. Skoro każda paczka operuje na osobnym zbiorze danych wejściowych, trzeba to zrównoleglić!

Jak najprościej zrównoleglić operację na dużym zbiorze rekordów?

Ano, całkiem prosto, okazuje się. Trzeba znaleźć unikalną kolumnę numeryczną całkowitoliczbową z rozkładem w miarę jednorodnym (a jeżeli takowej nie ma – utworzyć ją i wypełnić wartościami IDENTITY(1, 1)) , a następnie dla każdego rekordu podzielić tę wartość modulo ilość strumieni – w ten sposób dostajemy na wyjściu numer strumienia, do którego należy wysłać ten rekord. I po zawodach. Zamiast uruchamiać całość synchronicznie, zapuściłem to asynchronicznie, w dziesięciu równoległych strumieniach – i po mniej więcej czterech godzinach miałem gotowe wyniki.

Kiedy okazało się, że wyniki są poprawne, zostałem uznany za cudotwórcę. Dowiedziałem się bowiem (poniewczasie…), że problem ten przede mną próbowało już rozwiązać kilku innych spryciarzy. Jeden ocipiał, drugi osiwiał, trzeci uciekł do Nowej Zelandii, czwarty leczy się na depresję, a o piątym słuch zaginął. Tymczasem ja to machnąłem w trzy dni. Ha!

Na zakończenie polecam bardzo dobry kawał, który co prawda już tutaj kiedyś opowiadałem, ale ponieważ bardzo go lubię, zachęcam do lektury:

http://xpil.eu/blog/2011/07/02/docen-zula/

(dla niecierpliwych: kawał jest na samym dole wpisu).

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz