Czy da się pozbyć drabinki ifów nie tracąc na złożoności obliczeniowej/pamięciowej?

0

Jakiś czas temu robiłem projekt typowy z I semestru. Miałem w nim funkcję DaysToNumbers, która niezbyt kulturalnie wyglądała. Ale porobiłem testy, wykonanie się funkcji zajmowało ułamek procenta całości wykonania się programu i tak już to zostało.

Tylko, że teraz mnie to trochę gryzie, bo nadal nie wiem jak to zrobić żeby było jak najlepiej. Proszę o feedback, już upraszczając tłumaczę o co chodzi.

Mam listę jednokierunkową:

struct Node {
    std::string day;    // only these 7 values: "Mon", "Tue", ..., "Sun" are accepted, rest is treated as exception
    ...
    Node *pNext;
};

A o to funkcja DaysToNumbers wraz z 'funkcją-matką' ReplaceDaysToNumbers:

/** Function replaces literal day of the week's name with its corresponding number, i.e.: Mon->1, Tue->2, etc. */
void DaysToNumbers(Node*& p)
{
    if (p->day == "Mon")
        p->day = "1";
    else if (p->day == "Tue")
        p->day = "2";
    else if (p->day == "Wed")
        p->day = "3";
    else if (p->day == "Thu")
        p->day = "4";
    else if (p->day == "Fri")
        p->day = "5";
    else if (p->day == "Sat")
        p->day = "6";
    else if (p->day == "Sun")
        p->day = "7";
}

/** Function iterates through SLL and replaces every node's day of the week by using DaysToNumbers within the function. */
void ReplaceDaysToNumbers(Node*& pHeadNode)
{
    std::cout << "Replacing days with numbers (e.g.: Mon -> 1)..." << std::endl;
    Node* p = pHeadNode;
    while (p) {
        DaysToNumbers(p);
        p = p->pNext;
    }
}

Chodzi o to, że mam wypełnioną listę danymi i chcę pole struktury "days" zamienić na odpowiednik liczbowy.

Nie mogę korzystać z żadnego STLowskiego containera typu map lub vector, ale dozwolone są statyczne tablice. Można implementować swoje odpowiedniki STLowskich containerów.

Myślałem nad mniej więcej czymś takim (pseudokod):

std::string days_db[7] = {"Mon", "Tue", ..., "Sun"};

for (int i = 0; i < 7; i++)
    if (p->day == days_db[i]) {
        p->day = days_db[i];
        break/return;
    }

ale czy to nie jest po prostu gorsze rozwiązanie, bo w końcu trzeba by zaalokować dodatkową pamięć dla arraya, a sama pętla pomijając już alokację i też za pewne coś kosztuje. Jest więc wolniej (nie testowałem) i zajmuje więcej pamięci, więc gorzej. Za to jest czytelniej. (czy aby na pewno? Dla osobo wystarczająco mocno początkującej pierwotny kod byłby czytelniejszy)

Jeszcze jest kwestia co gdyby dni było sto czy tysiąc, to czy bym robił sto ifów? Nie wiem, ale nawet gdybym korzystał z tego drugiego rozwiązania, to i tak musiałbym wpisać te tysiąc dni do tablicy, więc prawie równie dobrze można by ifami jechać.

Chyba można by samemu zaimplementować własną strukturę imitującą std::unordered_map czy coś podobnego, ale czy to nie za duża artyleria na ten problem? (i nie wiem czy złożonościowo i czytelnościowo aby na pewno byłoby lepiej)

Po prostu nie podoba mi się idea, że nawet podoba mi się to rozwiązanie u góry. Ma ktoś jakąś propozycję alternatywnego rozwiązania? Kiedy ważniejsza jest optymalizacja od czytelności kodu i vice versa?

1

To jest to rozwiązanie i jest ono w każdym aspekcie lepsze. Jeśli masz ifa z litetalami to one też muszą być gdzieś zapisane, dokładnie w sekcji .data, więc zupełnie tak samo jak robiąc tablicę statyczną. Tak naprawdę różnica jest tylko taka, że w przypadku ifów kod wynikowy będzie większy i wolniejszy. No chyba że kompilator ogarnia takie optymalizacje, mnie sprawdzałem.

8

Jest więc wolniej (nie testowałem) (...)

W tym miejscu cała dywagacja powinna się skończyć - jakakolwiek rozmowa na temat problemów z wydajnością powinna zacząć się od profilowania, albo przynajmniej od zadania sobie samemu pytania: jak często ta funkcja będzie wywoływana? Czy będzie to raz na sekundę, tysiąc razy czy milion? Czy zaoszczędzę minutę, sekundę czy milisekundę? Czy skupianie się na mikro-optymalizacji w tym miejscu ma w ogóle sens?

Powiązany XKCD: https://xkcd.com/1205/

(...) i zajmuje więcej pamięci, więc gorzej.

O nie, co Ty zrobisz bez tych dwóch kilobajtów RAMu!

Nie wiem, ale nawet gdybym korzystał z tego drugiego rozwiązania, to i tak musiałbym wpisać te tysiąc dni do tablicy, więc prawie równie dobrze można by ifami jechać.

Chyba że wykorzystałbyś stałą globalną - wtedy całość inicjowana byłaby tylko raz.

Kiedy ważniejsza jest optymalizacja od czytelności kodu i vice versa?

Prawie zawsze ważniejsza jest czytelność - optymalizować powinieneś dopiero taki kod, który podczas profilowania stanowi hot spot / hot path. W innym wypadku mówimy o premature optimization i generalnie jest sytuacja niepożądana, ponieważ zabiera cenny czas programisty na błahostki, które prawdopodobnie nigdy nie będą stanowić problemu.

1

@Patryk27: ja bym nie był taki kategoryczny w sprawie przedwczesnej optymalizacji. Oczywiście w pracy to jest duży błąd, ale człowiek się uczy i po to jest czas uczyć się żeby móc robić rzeczy których w pracy robić nie wolno. Tym bardziej, że @Hodor pokazał że nie zna podstaw więc dobrze że spytał i dzięki temu pozna podstawy. Może zmieni to jego kierunek rozwoju, kto wie? W takim wypadku w ogóle najlepiej byłoby gdyby zobaczył jaki kod w assemblerze wygeneruje jeden i drugi kod (w g++ flaga -S). Wtedy zobaczy jak jego wyobrażenia mają się do rzeczywistości.

Tak drogą drogą to dzień tygodnia powinien być zapisany liczba, nie stringiem. Wtedy już w ogóle najlepiej, run bardziej że to C++ więc w sumie nie mogę przewidziec co się stanie. Jeśli będzie liczba i na jej podstawie wybieranie napisu. Tak to należy zrobić. I to nie jest przedwczesna optymalizacja tylko nauka podstaw.

1

@Patryk27:

Szczerze mówiąc nie rozumiem dogmatu, że póki nie ma profilowania, póty jakiekolwiek optymalizacje są niepożądane.

Kiedyś coś tam dłubałem w Unity3D i ostro używałem LINQ. I zaczęło mi się wydawać, że coś jednak nie tak jest z tym, co piszę. Wziąłem kartkę papieru, w dwóch wierszach wyliczyłem sobie długopisem, że to, co napisałem, ma złożoność tak tragiczną, że będzie się wykonywać dwie godziny.

Naprawiłem tragiczności. Działało ładnie.

Ale, wedle tego dogmatu, postąpiłem niesłusznie, gdyż winienem był wpierw uruchomić profiler. Ale to byłaby strata czasu, gdyż z góry wiedziałem, że to jest złe!

Takie przykłady można mnożyć. Schemat: rzut oka na kod albo samą koncepcję kodu nawet wystarczy, by było oczywiste, że to NIE MA PRAWA zmieścić się w zadanych ramach wydajnościowych. Ale nie: nie można od razu usunąć tragiczności: bo dogmat każe, by wpierw tracić czas na ukończenie pisania kodu - o którym wiadomo, że jest zły - profilować go - mimo iż wiadomo, gdzie jest usterka - i wtedy dopiero go naprawić?

Jak jest zadanie algorytmiczne, gdzie z zakresu danych jak wół wynika, że n^2 nie pójdzie, to mam pisać n^2 bo prostszy i czytelniejszy, nie działa i dopiero wtedy pisać n log n?

3

@kmph:

Szczerze mówiąc nie rozumiem dogmatu, że póki nie ma profilowania, póty jakiekolwiek optymalizacje są niepożądane. (...) Ale, wedle tego dogmatu, postąpiłem niesłusznie, gdyż winienem był wpierw uruchomić profiler.

Wziąłeś pod uwagę jedynie fragment tego, co napisałem; całość brzmi tak:

jakakolwiek rozmowa na temat problemów z wydajnością powinna zacząć się od profilowania, albo przynajmniej od zadania sobie samemu pytania: jak często ta funkcja będzie wywoływana?

Tak czy siak, pamiętać należy, że nie jest to żaden dogmat (a przynajmniej nie w taki sposób mój post miał zabrzmieć), ponieważ - jak zawsze - spektrum przypadków jest szerokie.

Co powiesz na alternatywną wersję:

Kiedyś coś tam dłubałem w Unity3D i ostro używałęm LINQ. I zaczęło mi się wydawać, że coś jednak nie tak jest z tym, co piszę. Wziąłęlm kartkę papieru, w dwóch wierszach wyliczyłem sobie długopisem, że to, co napisałem, ma złożoność tak tragiczną, że będzie się wykonywać godzinę. Naprawiłem tragiczności, teraz wykonuje się 5 minut. Szkoda, że usprawnienie zajęło mi trzy dni, a w zasadzie aplikacja i tak miała być odpalona tylko raz.

Idąc dalej:

rzut oka na kod albo samą koncepcję kodu nawet wystarczy, by było oczywiste, że to NIE MA PRAWA zmieścić się w zadanych ramach wydajnościowych. Ale nie: nie można od razu usunąć tragiczności: bo dogmat każe, by wpierw tracić czas na ukończenie pisania kodu - o którym wiadomo, że jest zły - profilować go - mimo iż wiadomo, gdzie jest usterka - i wtedy dopiero go naprawić?

Wolałbym stwierdzić: dogmat mówi, że masz ruszyć głową - dlatego właśnie pierwsza część mojego postu skupia się wokół zastanawiania się nad zasadnością poświęcania czasu na wskazaną optymalizację:

jak często ta funkcja będzie wywoływana? Czy będzie to raz na sekundę, tysiąc razy czy milion? Czy zaoszczędzę minutę, sekundę czy milisekundę?

Nie twierdzę zawsze odpalaj profiler - raczej: zawsze myśl.

0

ja dodam, że funkcja daty void DaysToNumbers(Node*& p), która działa tylko an jakimś Node to jest co najmniej dziwne.

1 użytkowników online, w tym zalogowanych: 0, gości: 1