Nie uważam tego za ważne poza komunikowaniem pomysłów i pracuję w obszarach krytycznych pod względem wydajności (raytracing, przetwarzanie obrazu i siatki, systemy cząstek, silniki fizyki itp.) I musiałem opracować wiele zastrzeżonych algorytmów i struktur danych podczas pracy w R&D. W tych obszarach często garstka bardzo wydajnych struktur danych i algorytmów może przynieść zupełnie nowe, najnowocześniejsze produkty, podczas gdy wczorajsze algorytmy powodują, że istniejące produkty stają się przestarzałe, dlatego zawsze dąży się do robienia rzeczy bardziej wydajnie. Jednak z zastrzeżeniem, nigdy nie opublikowałem żadnych artykułów na temat opracowanych przeze mnie algorytmów. Wszystkie były zastrzeżone. Gdybym to zrobił, potrzebowałbym pomocy matematyka, aby sformułować dowody i tak dalej.
Jednak moim zdaniem ilość pracy obliczeniowej na iterację jest często bardziej bezpośrednia niż skalowalność algorytmu, chyba że algorytm skaluje się naprawdę słabo. Jeśli ktoś wymyśli najnowocześniejszą technikę raytracingu, bardziej interesują mnie techniki obliczeniowe, takie jak sposób reprezentowania i dostępu do danych niż złożoność algorytmiczna, ponieważ rozsądna skalowalność jest już zapewniona w tym konkurencyjnym i innowacyjnym scenariuszu. Nie możesz być konkurencyjny wymyślając algorytmy, które nie skalują się.
Oczywiście, jeśli porównujesz złożoność kwadratową do liniowej, to ogromna różnica. Ale większość ludzi w mojej dziedzinie jest wystarczająco kompetentna, aby uniknąć zastosowania algorytmu złożoności kwadratowej do imponujących danych wejściowych. Skalowalność jest często głęboko implikowana, a bardziej znaczące i interesujące pytania brzmią: „Czy korzystałeś z GPGPU? SIMD? Czy działa równolegle? Jak reprezentowałeś dane? Czy zreorganizowałeś je dla wzorców dostępu przyjaznych dla pamięci podręcznej? Jak zajmuje dużo pamięci? Czy może solidnie poradzić sobie z tą sprawą? Czy odraczasz pewne przetwarzanie czy robisz to za jednym razem?
Nawet algorytm liniowo-rytmiczny może przewyższyć algorytm liniowo-czasowy, jeśli ten pierwszy uzyskuje dostęp do pamięci w bardziej optymalny sposób, np. Lub lepiej nadaje się do wielowątkowości i / lub SIMD. Czasami nawet algorytm liniowy może przewyższyć algorytm logarytmiczny z tych powodów, a naturalnie algorytmy czasu liniowego przewyższają algorytmy logarytmiczne dla małych wejść.
Dlatego dla mnie ważniejsze są to, co niektórzy nazywają „mikrooptymalizacjami”, takie jak reprezentacje danych (układy pamięci, wzorce dostępu z podziałem pól gorących / zimnych itp.), Wielowątkowość, SIMD, a czasami GPGPU. W dziedzinie, w której wszyscy są już wystarczająco kompetentni, aby używać przyzwoitych i najnowocześniejszych algorytmów do wszystkiego, a nowe artykuły są publikowane przez cały czas, twoja przewaga konkurencyjna w pokonaniu algorytmów nie polega na poprawie złożoności algorytmicznej, ale na bardziej bezpośredniej wydajność obliczeniowa.
Moje pole jest zdominowane przez genialnych matematyków, ale nie zawsze tych, którzy znają obliczeniowy koszt tego, co robią lub wiele sztuczek na niższym poziomie, aby przyspieszyć kod. To zazwyczaj moja przewaga nad nimi w opracowywaniu szybszych i węższych algorytmów i struktur danych, mimo że moje są o wiele mniej skomplikowane. Bawię się tym, co lubi sprzęt, w stronę bitów i bajtów i sprawia, że każda iteracja pracy jest znacznie tańsza, nawet jeśli wykonuję kilka kolejnych iteracji pracy niż naprawdę wyrafinowany algorytm - praca w moim przypadku jest znacznie tańsza. Kod, który piszę, również jest o wiele prostszy. Jeśli ludzie uważają, że mikrooptymalizowane wersje prostych algorytmów i struktur danych są trudne do zrozumienia i utrzymania,
Jako podstawowy przykład wymyśliłem prostą strukturę siatki, która ostatecznie przewyższyła drzewo KD w naszej firmie w zakresie wykrywania kolizji i usuwania zbędnych punktów. Moja głupia, prymitywna siatka była o wiele mniej skomplikowana algorytmicznie i jestem głupsza matematycznie i algorytmicznie niż facet, który zaimplementował drzewo KD w swoim nowatorskim sposobie znajdowania punktu środkowego, ale właśnie dostroiłem pamięć mojej siatki i wzorce dostępu oraz to wystarczyło, by przewyższyć coś znacznie bardziej wyrafinowanego.
Inną zaletą, która pozwala mi przetrwać na polu zdominowanym przez ludzi znacznie mądrzejszych ode mnie, jest po prostu zrozumienie, w jaki sposób działa użytkownik, ponieważ używam oprogramowania, które rozwijam w ten sam sposób. To daje mi pomysły na algorytmy, które naprawdę natychmiast dostosowują się do zainteresowań użytkowników. Jako podstawowy przykład większość ludzi próbuje przyspieszyć takie rzeczy, jak wykrywanie kolizji za pomocą indeksowania przestrzennego. Prawie kilkadziesiąt lat temu poczyniłem prostą obserwację kształtującą karierę dla modeli organicznych, które na przykład, jeśli postać położy dłonie na twarzy, struktura indeksowania przestrzennego będzie musiała rozdzielić węzły i dokonać drogich aktualizacji, jeśli postać potem zdjął rękę z twarzy. Jeśli zamiast tego partycjonujesz na podstawie danych łączności, a nie pozycji wierzchołków, możesz uzyskać stabilną strukturę hierarchiczną, która aktualizuje się bardzo szybko i nigdy nie musi dzielić ani ponownie równoważyć drzewa (musi tylko aktualizować obwiednię w każdej klatce animacji) ... takie rzeczy - algorytmuje dziecko bez ciężkiego tła matematycznego mogliby wymyślić, gdyby po prostu zrozumieli podstawową koncepcję, ale ci, którzy wymykali się matematykom, ponieważ nie myśleli o rzeczach w sposób tak bliski jak pracowali użytkownicy i zbyt dużo myśleli o właściwościach geometrii, a nie o geometrii był powszechnie używany. Dobrze sobie radzę, opierając się bardziej na ogólnej wiedzy obliczeniowej i wiedzy użytkownika końcowego niż na algorytmach. W każdym razie tak naprawdę nie uważałem za tak ważne skupienie się na złożoności algorytmicznej.
