Czy Big O naprawdę ma znaczenie?

W najgorszym przypadku akademii naucza się Big O nad wszystkim innym. W porównaniu ze złożonością przestrzeni, normalną analizą przypadków, prostotą ponad złożonością itp.

W szczególności dla programowania gier i przemysłu, co naprawdę ma największe znaczenie i dlaczego?

Referencje byłyby bardzo pomocne.

Jak w przypadku każdego innego pytania dotyczącego „jednej prawdziwej ścieżki”, są to wszystkie narzędzia w twoim zestawie narzędzi i zdarzają się przypadki, w których big-O przebija wszystko i miejsca, gdzie to nie ma znaczenia (tm).

„Nigdy” nie napisalibyśmy solwera fizycznego bez obawy o duże O. Nie zaimplementowałbyś algorytmu sortowania (dla żadnego zestawu danych oprócz najmniejszego) bez obawy o to. Jeśli piszesz grę sieciową, martwisz się sposobem, w jaki wydajność i ruch sieciowy skalują się na użytkownika.

Być może nie przejmujesz się wielkim O, kiedy, no cóż, tak naprawdę nie potrafię wymyślić czasu, ale jestem pewien, że jest kilka. :) Na szczęście większość rzeczy, które robimy w grach, skaluje się liniowo; chcesz odczytać plik z dysku? Zajmie to trochę czasu liniowo proporcjonalnie do rozmiaru pliku (pomijając stały czynnik poszukiwania i możliwe konsekwencje rozmiaru sektora).

Co jednak jeśli chcesz znaleźć konkretny byt na liście podmiotów? To liniowe wyszukiwanie za każdym razem, gdy to robisz. Jeśli musisz znaleźć gracza raz dla każdego bytu na świecie, to podejście zabije cię dla wszystkich, z wyjątkiem najbardziej trywialnych gier, i nawet wtedy prawdopodobnie warto „zoptymalizować” to wyszukiwanie, aby mieć stały czas (np. Zapisz indeks lub wskaźnik do gracza), co daje więcej czasu na robienie innych rzeczy, które są faktycznie widoczne dla gracza.

Myślę jednak, że to podsumowuje; za każdym razem, gdy procesor robi coś, co nie jest bezpośrednio reprezentowane przez gracza, marnuje czas. Maksymalizacja czasu obliczania przez procesor danych, które będą wyświetlane odtwarzaczowi, maksymalizuje WOW! dajesz graczowi.

Moja ogólna zasada jest taka, że ​​jeśli nie jesteś O (przerażający), twoje inne problemy są bardziej istotne.

Moją inną ogólną zasadą jest to, że dane są królem. O ile nie profilujesz kodu za pomocą realistycznego zestawu danych, po prostu zgadujesz.

Edycja: Aby przejść do bardziej szczegółowych szczegółów, twoje duże O nie jest tak ważne, ponieważ (przynajmniej z mojego doświadczenia) większość twoich zbiorów danych jest stosunkowo niewielka. Prawdopodobnie nie obchodzi Cię górna granica wydajności, gdy pracujesz ze strukturą danych zawierającą mniej niż kilkaset elementów. A jeśli twoje listy zawierają ponad 100 000 elementów, naprawdę musisz wziąć pod uwagę wszystkie aspekty swoich algorytmów. Z mojego doświadczenia wynika, że ​​pamięć jest bardziej czynnikiem ograniczającym niż szybkość procesora. Szybszy algorytm zapamiętywania pamięci może nie być tak dobry jak wąski, ale wolniejszy, w zależności od przypadków użycia.

Duże O ma znaczenie przez większość czasu, ale czasem teoretycznie „gorszy” algorytm okazuje się w praktyce znacznie szybszy.

Sprawdź świetny przykład Tony'ego Albrechta: http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html

Znajdziesz to wszędzie w rozwoju gier, gdzie liczba elementów w operacji jest albo tak duża, że ​​bardzo inny algorytm jest szybszy, albo tak mała, że ​​wystarcza głupszy algorytm (lub mieści się w buforze tak dobrze, że zastępuje wydajność z lepszego algorytmu).

Problem z Big O polega na tym, że jest to ogólne określenie złożoności zadania i nie bierze pod uwagę złożoności współczesnego sprzętu docelowego, ani nie zapewnia żadnego wglądu w czas potrzebny na konfigurację.

W wielu przypadkach najlepsze optymalne rozwiązanie to dwa kroki. W praktyce twórcy gier mają tendencję do korzystania z niskich algorytmów O, ale równoważą koszty z czasem opracowywania lub debugowania. Gdy znajdziesz rozsądne rozwiązanie, zawsze musisz spojrzeć na to, jak sprzęt radzi sobie z zadaniem i jak pozwolić sprzętowi zrobić więcej w krótszym czasie.

Kiedy jestem kodowania w-silnik, ja często dotyczy jedynie stałą n: Ja już mam partycję przestrzenną ograniczającą liczbę przedmiotów odbioru update(), physics()orazrender() do tych, w przybliżeniu na ekranie i okolic. Maksymalny rozmiar partii jest zwykle dość dobrze zdefiniowany na grę, chociaż niezmiennie jest nieco większy niż planowałeś.

W tym przypadku nie chodzi mi tak bardzo o duże O, jak o stały mnożnik współczynników i warunki niższego rzędu. W przypadku funkcji ze środowiskiem uruchomieniowym, takim jak a*n^2 + b*n + c(która jest O(n^2)), często jestem znacznie bardziej zainteresowany redukcją ai ewentualnie eliminacją c. Koszt przygotowania lub porzucenia cmoże stać się proporcjonalnie duży w stosunku do małego n.

Nie oznacza to jednak, że big-O (a zwłaszcza big-theta ) jest doskonałym wskaźnikiem zapachu kodu. Zobacz O(n^4)gdzieś lub jeszcze gorzej O(k^n)geometryczny czas, i czas upewnić się, że rozważasz inne opcje.

Generalnie bardziej martwię się o optymalizację dużych O i przeskakiwanie przez obręcze w celu znalezienia algorytmów z niższymi dużymi O, gdy mam do czynienia z narzędziami do tworzenia danych. Chociaż liczba obiektów na danym poziomie / obszarze przesyłania strumieniowego jest ogólnie dobrze określona, ​​łączna liczba obiektów / zasobów graficznych / plików konfiguracyjnych / itd. W całej grze może nie być. To także o wiele większa liczba. Nawet uruchamiając równoległe tworzenie danych, wciąż czekamy na minutę (wiem, skamlać - dane powodujące, że konsole mogą trwać kilka godzin - jesteśmy głównie małymi grami podręcznymi), aby przejść przez jam data-clean && jam datacykl.

Podając konkretny przykład: wymknęło się to spod kontroli algorytmu strumieniowania kafelków w tle, który przesyła strumieniowo 8 x 8 256-kolorowych kafelków. Przydatne jest dzielenie buforów przesyłania strumieniowego między „warstwami” tła, a może być ich do 6 na danym poziomie, współużytkując ten sam bufor. Problem polega na tym, że oszacowanie rozmiaru potrzebnego bufora opiera się na możliwych pozycjach wszystkich 6 warstw - a jeśli są to liczby pierwsze szerokość / wysokość / szybkość przewijania, szybko zaczynasz szukać wyczerpującego wyszukiwania - które zaczyna się zbliżaćO(6^numTiles)- która w wielu przypadkach należy do kategorii „dłużej niż wszechświat będzie w pobliżu”. Na szczęście większość przypadków ma zaledwie 2-3 warstwy, ale nawet wtedy mamy ponad pół godziny pracy. W tej chwili próbkujemy bardzo mały podzbiór tych możliwości, zwiększając ziarnistość, aż upłynie określony czas (lub wykonaliśmy zadanie, które może się zdarzyć w przypadku małych konfiguracji dwuwarstwowych). Podkreślamy nieco te szacunki na podstawie wcześniejszych statystyk dotyczących tego, jak często byliśmy błędni, a następnie dodajemy trochę dodatkowego wypełnienia dla lepszej oceny.

Jeszcze jeden zabawny przykład: jakiś czas temu w grze na PC główny inżynier eksperymentował przez chwilę z listami pominięć . Narzut pamięci powoduje więcej efektów pamięci podręcznej, co dodaje pewnego rodzaju niestały mnożnik do całej sprawy - więc naprawdę nie są dobrym wyborem dla małych n. Ale w przypadku większych posortowanych list, na których często przeprowadzane są wyszukiwania, zapewniają one korzyść.

(Często stwierdzam, że naiwny algorytm jest wyższy-O, szybszy na mniejszych zestawach danych i łatwiejszy do zrozumienia; bardziej interesujące / złożone (np. Patricia trie) są trudniejsze do zrozumienia i utrzymania przez ludzi, ale wyższą wydajność na większych zestawy danych.)

Może być przydatny, ale może być również nieistotny. Weźmy na przykład moją najnowszą grę, która jest czymś w rodzaju klonu Smash TV. Odgórna gra, potwory wlewają się z boków, strzelasz do nich.

Teraz istnieje wiele sprytnych sposobów określania kolizji. Możesz użyć KDtrees do podzielenia przestrzeni, abyś nie testował pocisków przeciwko potworom, których nie mogłyby trafić. I oczywiście mogłem być mądry i mogłem to zrobić.

Byłem jednak leniwy, więc porównałem każdą kulę z każdym potworem. Nawet w najbardziej gorączkowych sytuacjach kod kolizji zużywał znacznie mniej niż 10% procesora gry przy 60 klatkach na sekundę. Big-O: Nieważne.

Podobnie miałem grę w stylu 4x, w której budowałeś miasta na wyspach, a czasem miasta ulegały zniszczeniu. Mogłem być sprytny i próbować odjąć dochód zniszczonego miasta od zmiennych dochodów. Ale ja nie. Właśnie wymazałem dochód i przeliczałem go od nowa za każdym razem, gdy coś się zmieniało. Zupełnie nieistotne z punktu widzenia procesora.

Big-O jest tak samo ważny w grach, jak we wszystkim innym: to znaczy, zupełnie nieważny, aż do momentu, gdy stanie się krytyczny.

Idź napisz kod. Jeśli jest zbyt wolny, profiluj go.

Analiza Big-O jest ważna, ale nie jest to pierwsza rzecz, o której należy pomyśleć przy tworzeniu gry. Ponieważ tworzenie gier wymagało mnóstwa skomplikowanego kodu, zawsze zalecałbym Code Simplicity jako pierwsze kryterium dla algorytmu. Algorytmy ze skomplikowaną księgowością po prostu marnują Twój czas.

Myślę, że naprawdę ważne jest, aby twoja gra zawsze działała przy 60 fps podczas programowania. Gdy zanurzysz się poniżej tego, pierwszą rzeczą, którą zrobisz, jest uruchomienie profilera. Gdy znajdziesz wąskie gardło, atakujesz je. Dużo czasu musisz robić rzeczy niekodujące, takie jak informowanie projektantów poziomów, aby umieszczali mniej rzeczy w danym obszarze (i dawali im do tego narzędzia).

Czasami faktycznie identyfikujesz kod, który należy przyspieszyć. Uważam to za zabawną inżynierię! Chciałbym mieć więcej okazji, aby to zrobić. I oczywiście chcesz iterować zmieniając jedną rzecz na raz i mierząc wydajność. Typowe problemy, które znajduję, to:

1. Upewnij się, że nie dzwonisz do nowego ani do centrum dla każdej ramki (jest to zawsze problem nr 1)
2. Ogranicz pracę: mniej rzutów promieniami, mniej facetów itp.
3. Problemy z typem algorytmu Big-O
4. Spójność pamięci podręcznej: umieść rzeczy w tablicach zamiast w rozproszonej pamięci
5. Nie używaj STL w trybie debugowania. (i zawsze chcesz, aby tryb debugowania działał)

Notacja Big-O jest z definicji asymptotyczną złożonością - tzn. Pokazuje, jak skaluje się czas, gdy N (lub dowolne zmienne, które masz) stają się „bardzo” duże. Aby powtórzyć komentarz Tetrad (który podniosłem) „dane są królem”. Jeśli N jest „bardzo duży” w twojej konkretnej sytuacji, ma to znaczenie, jeśli N jest „bardzo mały”, to nie ma znaczenia. Doświadczenie i praktyka pozwalają poczuć, jak określić ilościowo „bardzo duże” i „bardzo małe”.

Oczywiście zawsze profiluj najpierw, a ostatni optymalizuj (chyba że wykonujesz studium wykonalności funkcji).

Znaczenie Big-O w twoim oprogramowaniu to O (N ² ). W miarę wzrostu N znaczenie właściwego algorytmu rośnie jeszcze bardziej. :)

Big-O to tylko wskazówka - coś, co mówi ci o przybliżonej wydajności, jakiej możesz oczekiwać od algorytmu - i jak możesz oczekiwać, że wydajność będzie się skalować wraz ze wzrostem rozmiaru zestawu danych . Musisz pamiętać o dwóch głównych kwestiach związanych z Big-O:

1) Jeśli masz dwa algorytmy, które w większości robią to samo, ale jeden ma lepsze O, prawdopodobnie powinieneś wybrać ten (oczywiście)

2) Big O dotyczy analizy asymptotycznej . Big-O naprawdę wchodzi w grę tylko wtedy, gdy n jest duże . Na przykład algorytm O (n) może być bardzo podobny w działaniu do algorytmu O (n ^ 2) dla małych n . Jeśli mówisz o algorytmie, który wymaga n ^ 2 operacji na wierzchołek, ale n = 2 lub n = 3, to nie ma dużej różnicy między algorytmem O (n ^ 2) (biorąc odpowiednio 4 i 9 operacji) i O (n) one (odpowiednio 2 i 3 operacje). Jeśli jednak n = 9, nagle mówisz o 81 operacjach dla algorytmu O (n ^ 2) i tylko 9 dla O (n) - większa różnica - a jeśli n = 100, to jesteś mówienie o 100 operacjach vs 10000 - znacznie większa różnica.

Dlatego zawsze należy brać pod uwagę Big-O w tym świetle: ma na celu porównywanie algorytmów, które robią to samo w oparciu o najgorsze wyniki, gdy n staje się duże . Różnice między algorytmami mogą być prawie nieistotne, gdy n jest bardzo małe.

Nie mam żadnych referencji, ale Big O jest przynajmniej przydatny, aby być świadomym podczas analizy problemu i dyskusji. Z drugiej strony, oczywiście, jeśli wersja O (log n) jest znacznie bardziej zaangażowana w O niż wersja O (n), jest to sporne porównanie. I jak w przypadku wszystkiego, zawsze następuje kompromis. Złożoność przestrzeni może być problemem, chociaż można to również wyrazić w O w ogóle. Normalna analiza przypadków ... mniej, ponieważ nie chcesz, aby wartości odstające również się poprawiały. Moim zdaniem prostota nad złożonością jest względnie bezużyteczna w tworzeniu gier, ponieważ prędkość prawie zawsze stanowi problem, więc chyba, że ​​prostota prowadzi do przyspieszeń (ale wtedy oznacza to, że twoja złożona sprawa była błędna z niewłaściwych powodów) prostota będzie musiała pójść przez okno na rzecz prędkości. Ale Big O jest zdecydowanie przydatny,

Kiedy prototyp funkcji gier lub aspekt gry, nie należy martwić się o optymalizację go w ogóle .

W trakcie jego prototypowania i poznawania osobliwości tej funkcjonalności niezbędne optymalizacje staną się oczywiste i będą uwzględniać ostateczny projekt, taki jak 2. natura ... przez większość czasu.

Nie przejmuj się.

To nie powinno być wszystko i koniec. Pomaga to jednak rozwiązać oczywiste problemy, które mogą powodować pogorszenie wydajności; po co używać czegoś w czasie O (n ^ 2), skoro można zrobić to samo w czasie O (log n)?

Myślę, że dotyczy to gier bardziej niż większości innych branż, ponieważ rynek jest tym, który najbardziej zauważyłby problemy z prędkością. Ktoś korzystający z edytora tekstu nie będzie dbał o to, czy opóźnienie o pół sekundy na wykonanie akcji X, ale gracze prawdopodobnie pójdą „omg omg gra Y jest tak wolna, że ​​wykonanie czynności Z zajmuje wieki.

W rozwoju gier (i większości innych) narzekamy na jedną dodatkową operację wykonaną na pętlę:

for (int i = 0; i < array.length; i ++) { /* ... */ }

vs.

for (int i = 0, l = array.length; i < l; i ++) { /* ... */ }

Większość współczesnych gier ma fizykę, a znajdziesz problem symulacji n-ciała . W naiwnym algorytmie jest to O (n ^ 2), ale istnieje optymalizacja, która czyni go O (n log n) (ale poświęca pewną dokładność).

Można powiedzieć, że nie programujesz interakcji grawitacyjnych i cząsteczkowych, ale co z zachowaniem zespołu armii (zombie), w której poruszają się one w zależności od innych lokalizacji (bardziej konkretnie: roju)?

W konwencjonalnym algorytmie wykrywania kolizji złożoność czasowa wynosi O (n ^ 2), podobnie jak ciało n. Jest jednak lepszy sposób: rozdziel świat na wiele małych części, aby wykryć kolizję tylko obiektów w tej samej części. Zobacz http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php .

Jeśli twoja gra jest skryptowalna, NIE zmuszaj scriptera do pisania w skrypcie algorytmów O (n ^ 2) (i więcej), takich jak przeszukiwanie torby użytkownika. Zamiast tego wykonaj wbudowaną funkcję w kodzie.

W prawdziwym świecie liczy się tylko surowa wydajność. Teraz Big-O algorytmu może służyć jako pierwsza wskazówka, czego użyć, ale w zależności od sprzętu implementacja może być strasznie nieefektywna. Na przykład wyszukiwanie liniowe może często być szybsze niż wyszukiwanie binarne, ponieważ uzyskuje się dostęp do pamięci liniowej i brak rozgałęzień.

Ponadto, ze względu na obecny kierunek w wielowątkowych platformach i architekturach, Big-O traci duże znaczenie, ponieważ bierze pod uwagę tylko pionową skalowalność pamięci lub dotknięć danych na operację, a nie bierze również pod uwagę sposób, w jaki algorytm skaluje się z większą liczbą wątków.