Kiedy „optymalizacja kodu” == „strukturyzuje dane”?

Niedawny artykuł ycombinator wymienia komentarz z zasadami doskonałego programisty.

#7. Dobry programista: optymalizuję kod. Lepszy programista: uporządkuję dane. Najlepszy programista: jaka jest różnica?

Uznanie subiektywnych i kontrowersyjnych pojęć - czy ktoś ma stanowisko co do tego? Tak, ale chciałbym później zredagować to pytanie, aby nie predysponować do odpowiedzi.

Dziewięć razy na dziesięć, gdy dobrze skonstruujesz swój kod / modele, optymalizacja stanie się oczywista. Ile razy widziałeś gniazdo szerszeni i stwierdziłeś, że jest ono całkowicie nieoptymalne, a po jego restrukturyzacji wiele zwolnień stało się niezwykle oczywiste.

Projektant wie, że osiągnął doskonałość nie wtedy, gdy nie ma już nic do dodania, ale kiedy nie ma już nic do zabrania. - Antoine de Saint-Exupéry

Dobrze ustrukturyzowany system będzie miał minimalny charakter, a ze względu na jego minimalną naturę zostanie zoptymalizowany, ponieważ jego niewielka ilość zależy bezpośrednio od tego, jak mało robi, aby osiągnąć swój cel.

Edycja: Aby wyjaśnić punkt, który inni zabrali z tego, jest również całkowicie trafne zobaczyć stwierdzenie jako identyfikujące związek między kodem a danymi. Relacja ta jest zatem następująca: jeśli zmienisz strukturę danych, będziesz musiał zmienić kod, aby zachować zmienioną strukturę. Jeśli chcesz zoptymalizować swój kod, prawdopodobnie będziesz musiał zmienić strukturę danych, aby kod był w stanie optymalnie obsługiwać dane.

To powiedziawszy, istnieje zupełnie osobna możliwość, która została tutaj pominięta, i to znaczy, że ten człowiek mający relacje z YCombinatorem może odnosić się do danych kodu AS w tradycji homoikoniczności LISP. Przypuszczam, że to jest sens w moim umyśle, ale jest to YCombinator, więc nie wykluczyłbym, że cytat po prostu mówi, że LISPers są „najlepszymi programistami”.

Myślę, że autor sugeruje, że jakakolwiek restrukturyzacja danych prowadzi do restrukturyzacji kodu. Dlatego też restrukturyzacja danych w celu optymalizacji systemu zmusi cię również do optymalizacji kodu, wyświetlając pytanie „jaka jest różnica?” odpowiedź.

Zauważ, że „znakomity programista” może odpowiedzieć na „jaka jest różnica?” że pozostała jakaś różnica: kiedy już zaczniesz optymalizować w celu lepszego wykorzystania pamięci podręcznej procesora, możesz zachować taki sam układ struktur danych, ale zmienić kolejność dostępu do nich, możesz zrobić dużo różnica.

Rozważ najbardziej oczywisty przykład tego - „wyszukiwanie danych użytkownika jest zbyt wolne!”

Jeśli dane użytkownika nie zostaną zindeksowane lub przynajmniej posortowane, restrukturyzacja danych szybko przyniesie wzrost wydajności kodu. Jeśli dane są poprawnie skonstruowane, a ty po prostu iterujesz kolekcję (zamiast korzystać z indeksów lub robić coś w rodzaju wyszukiwania binarnego), wówczas modyfikacja kodu powoduje zwiększenie wydajności kodu.

Programiści rozwiązują problemy. Chociaż użyteczne jest rozróżnianie algorytmów od struktur danych, często nie mogą istnieć osobno. Najlepsi programiści wiedzą o tym i nie izolują się niepotrzebnie.

Nie zgadzam się z powyższym stwierdzeniem, przynajmniej bez wyjaśnienia. Widzę, że kodowanie to działanie polegające na wykorzystaniu niektórych struktur danych. Struktury danych miałyby ogólnie wpływ na kodowanie. Więc moim zdaniem istnieje różnica między nimi dwoma.

Myślę, że autor powinien napisać ostatnią część jako „Najlepszy programista: optymalizuję oba”.

Istnieje świetna książka (przynajmniej w momencie jej opublikowania) o nazwie: Algorytmy + Struktury danych = Programy .

Optymalizacja kodu może czasem zwiększyć prędkość dwa razy, a czasami dziesięciokrotnie, a nawet dwadzieścia, ale o to chodzi. Może to zabrzmieć dużo, a jeśli 75% czasu wykonywania programu jest spędzane na pięcioliniowej procedurze, której prędkość można łatwo podwoić, warto zoptymalizować tę optymalizację. Z drugiej strony, wybór struktur danych może wpływać na szybkość wykonywania o wiele rzędów wielkości. Nowoczesny, wysoce zoptymalizowany wielowątkowy procesor z superoptymalizowanym kodem do wyszukiwania danych według klucza na 10 000 000 pozycji liniowej listy połączonej przechowywanej w pamięci RAM byłby wolniejszy niż znacznie wolniejszy procesor z dość prosto zakodowaną tabelą skrótów. Rzeczywiście, gdyby dane były odpowiednio uporządkowane, nawet w 1980 r. ”

To powiedziawszy, projektowanie wydajnych struktur danych często wymaga bardziej złożonych kompromisów niż optymalizacja kodu. Na przykład w wielu przypadkach struktury danych, które umożliwiają najbardziej efektywny dostęp do danych, są mniej wydajne w aktualizacji (czasami o rząd wielkości) niż te, które umożliwiają szybkie aktualizacje, a te, które umożliwiają najszybsze aktualizacje, mogą pozwolić na najwolniejszy dostęp. Ponadto w wielu przypadkach struktury danych, które są optymalne dla dużych zbiorów danych, mogą być stosunkowo nieefektywne z małymi. Dobry programista powinien dążyć do zrównoważenia tych konkurujących czynników z ilością czasu programisty wymaganego do wdrożenia i utrzymywania różnych struktur danych oraz być w stanie osiągnąć odpowiednią równowagę między nimi.

Struktury danych wpływają na wiele czynników związanych z wydajnością. Myślę, że możemy długo i długo patrzeć na problemy z założonym wyobrażeniem o idealnej strukturze danych, aw tym kontekście myślenia nawet tworzyć dowody (często przez indukcję) optymalności. Na przykład, jeśli umieścimy posortowaną listę w tablicy i oszacujemy takie rzeczy, jak koszt wstawienia elementu, możemy zdecydować, że średnio musimy przesunąć 1/2 tablicy dla każdego wstawiania. Dla każdego wyszukiwania binarnego możemy znaleźć pasujący element (lub nie) w log n krokach.

Ewentualnie, jeśli odłożymy decyzję o strukturze danych (unikniemy przedwczesnej optymalizacji ) i przestudiujemy przychodzące dane oraz kontekst, w którym będziemy ich używać, jak duże są, jakie opóźnienia i jakie mają znaczenie dla użytkowników, ile mamy pamięci vs. użyłby z reprezentacjami danych, które znamy lub możemy opracować.

W obszarach takich jak sortowanie i wyszukiwanie istnieje wiele informacji. Naprawdę wielcy programiści pracowali nad tym od dawna. Dobre zrozumienie tych problemów jest przydatne i jest to świetna rzecz, jeśli znasz więcej metod, niż gdy ukończyłeś klasę struktur danych. Drzewa binarne mogą zapewnić lepszą wydajność wstawiania w zamian za większe wykorzystanie pamięci. Tabele skrótów zapewniają jeszcze większe ulepszenia, ale wciąż więcej pamięci. Drzewo radix i sortowanie radix mogą jeszcze bardziej ulepszyć.

Kreatywne strukturyzowanie danych może pomóc w przeformułowaniu problemu i otworzyć drzwi dla nowych algorytmów, dzięki którym trudne aplikacje są szybsze, a czasem niemożliwe.

Aby wyrazić moje najlepsze przypuszczenie, co oznacza ten artykuł, przyjmuję niewypowiedziany podtekst (którego brakuje w artykule), który każdy programista powinien zrozumieć na temat optymalizacji:

• optymalizacja następuje dopiero po prawidłowym uruchomieniu programu:
  • spraw, by działał poprawnie, a następnie spraw, by działał szybko
  • zasada ta jest punktem maksymy Knutha: „przedwczesna optymalizacja jest źródłem wszelkiego zła”
• jeśli i kiedy stwierdzisz, że optymalizacja nie jest przedwczesna, musisz ją zmierzyć najpierw, aby ustalić, co faktycznie wymaga optymalizacji, i jeszcze raz i jeszcze podczas optymalizacji, aby powiedzieć, jakie efekty mają twoje próby optymalizacji.
  • jeśli twój kod działa w trakcie programowania, profiler jest twoim przyjacielem w tym.
  • jeśli kod działa w środowisku produkcyjnym, musisz go oprzyrządować i zaprzyjaźnić się z systemem logowania.

A teraz: Twoje pomiary pokażą Ci, w którym miejscu kodu urządzenie pali najwięcej cykli. „Dobry” programista skupi się na optymalizacji tych części kodu, zamiast na marnowaniu czasu na optymalizację nieistotnych części.

Jednak często można uzyskać większe korzyści, patrząc na system jako całość i znajdując sposób, aby pozwolić maszynie wykonać mniej pracy. Często zmiany te wymagają zmiany organizacji danych; w ten sposób „lepszy” programista będzie częściej konstruował dane.

„Najlepszy programista” będzie miał dokładny model mentalny działania maszyny, dobre podstawy w projektowaniu algorytmów i praktyczne zrozumienie interakcji między nimi. To pozwala mu traktować system jako zintegrowaną całość - nie zobaczy różnicy między optymalizacją kodu a danymi, ponieważ ocenia je na poziomie architektonicznym.

Najlepszy programista: jaka jest różnica?

Najlepszy programista? Nie. Kiepski programista. Zakładam, że słowo „optymalizacja” oznacza rzeczy, które programiści zwykle próbują zoptymalizować, pamięć lub czas pracy procesora. W tym sensie optymalizacja idzie w parze z niemal każdą inną metryką oprogramowania. Zrozumiałość, łatwość konserwacji, testowalność itp .: Wszystko to wymaga krótkiej analizy, gdy celem jest optymalizacja - chyba że ktoś próbuje zoptymalizować ludzką zrozumiałość, łatwość konserwacji, testowalność itp. Nie wspominając o kosztach. Napisanie algorytmu optymalnego pod względem prędkości / przestrzeni kosztuje znacznie więcej pod względem czasu programisty niż naiwne kodowanie algorytmu przedstawione w tekście lub czasopiśmie. Kiepski programista nie zna różnicy. Dobry robi. Najlepszy programista wie, jak dokładnie określić, co należy zoptymalizować, i robi to rozsądnie.