Czy często nie używa się bibliotek do standardowych algorytmów numerycznych i dlaczego?

Wiele algorytmów numerycznych (integracja, różnicowanie, interpolacja, funkcje specjalne itp.) Jest dostępnych w bibliotekach obliczeń naukowych, takich jak GSL . Ale często widzę kod z „ręcznie walcowanymi” implementacjami tych funkcji. Czy w przypadku małych programów, które niekoniecznie są przeznaczone do publicznej dystrybucji, powszechną praktyką wśród naukowców zajmujących się obliczeniami jest samodzielne wdrażanie algorytmów numerycznych (tzn. Kopiowanie lub transkrybowanie ze strony internetowej, Przepisy numeryczne lub podobne), kiedy są potrzebne? Jeśli tak, to czy istnieje jakiś szczególny powód, aby unikać linkowania do czegoś takiego jak GSL, czy może jest to po prostu bardziej „tradycja” niż cokolwiek innego?

Pytam, ponieważ jestem wielkim fanem ponownego wykorzystania kodu , co sugerowałoby, że powinienem spróbować użyć istniejących implementacji, jeśli to możliwe. Jestem jednak ciekawy, czy istnieją powody, dla których zasada ta jest mniej cenna w obliczeniach naukowych niż w programowaniu ogólnym.

Zapomniałem wspomnieć: konkretnie pytam o C i C ++, w przeciwieństwie do języków takich jak Python, w których korzystanie z biblioteki ma wyraźną korzyść (szybkość wykonywania).

Sam wszystko wdrażałem, ale ostatnio zacząłem używać bibliotek znacznie więcej. Sądzę, że korzystanie z biblioteki ma kilka bardzo ważnych zalet, poza kwestią tego, czy sam musisz napisać procedurę, czy nie. Jeśli korzystasz z biblioteki, dostajesz

• Kod, który został przetestowany przez setki / tysiące / więcej użytkowników
• Kod, który będzie nadal aktualizowany i ulepszany w przyszłości, bez żadnej pracy z twojej strony
• Zoptymalizowany kod, który jest bardziej wydajny i być może bardziej skalowalny niż w przypadku pierwszej próby
• W zależności od biblioteki, ustanawiając interfejs w kodzie, możesz uzyskać dostęp do wielu algorytmów, których obecnie nie używasz, ale zechcesz w przyszłości

W ostatnim punkcie powyżej myślę o dużych bibliotekach, takich jak Trilinos lub PETSc . Mogę to wzmocnić kilkoma konkretnymi osobistymi przykładami w rozwoju PyClaw . Chociaż zrównanie Clawpack z wywołaniami MPI byłoby proste , zdecydowaliśmy się na użycie PETSc. To pozwoliło nam ograniczyć paralle kodu w pakiecie do mniej niż 300 linii Pythona, ale jeszcze lepiej, dzięki umieszczeniu naszych danych w formacie PETSc uzyskaliśmy natychmiastowy dostęp do niejawnych solverów PETSc, umożliwiając bieżącą pracę nad niejawnym solverem w PyClaw. Jako drugi przykład, PyClaw początkowo obejmował ręczną rekonstrukcję WENO piątego rzędu, ale ostatecznie postanowiliśmy polegać na PyWENOpakiet do tego. Był to ogromny zysk, ponieważ PyWENO może automatycznie generować procedury WENO dowolnego zamówienia w kilku językach.

Wreszcie, jeśli korzystasz z bibliotek, możesz wnieść swój wkład , opracowując ulepszenia lub znajdując błędy, które przyniosą korzyści wielu innym osobom, podczas gdy debugowanie lub ulepszanie własnego kodu przynosi korzyści tylko tobie.

Łączenie się z funkcją biblioteki wiąże się z dużym nakładem programisty, szczególnie jeśli biblioteka ta jest nowa dla programisty. Często łatwiej jest po prostu przepisać proste algorytmy niż poznać specyfikę konkretnej biblioteki. Gdy algorytmy stają się coraz bardziej złożone, to zachowanie się zmienia.

Python celuje w zmniejszaniu tego narzutu za pomocą narzędzi takich jak pip / easy_install i jednolitego interfejsu struktury danych (tzn. Wydaje się, że każda biblioteka przyjmuje i tworzy tablicę numpy).

Jednym z projektów, w których jestem teraz zaangażowany, jest napisanie elastycznego pakietu do symulacji i analiz dla klasy detektorów fizyki cząstek. Jednym z celów tego projektu jest dostarczenie do bazy kodu stosowanego w tych rzeczach w nadchodzących dziesięcioleciach.

W tym momencie mamy już dwa tuziny zależności, co sprawia, że ​​proces budowania jest koszmarem, który wydzielił oddzielny projekt zarządzany z centrum obliczeniowego Fermilab, aby zapewnić niezawodny łańcuch narzędzi.

Teraz wyobraź sobie, że napotykasz potrzebę jakiegoś narzędzia, którego nie ma w tym łańcuchu narzędzi (zdarzyło mi się to w zeszłym miesiącu). Masz trzy możliwości

1. Rzuć swoją własnością. Ze wszystkimi związanymi z tym ryzykami i kłopotami.
2. Zeskrob gdzieś kod z biblioteki i umieść go w The Project. Oznacza to, że musisz kontynuować konserwację w przyszłości i że musisz zrozumieć kod innej osoby, kiedy to nastąpi.
3. Idź do osób, które utrzymują łańcuch narzędzi, błagaj ich o to, czego potrzebujesz, a następnie poczekaj na cykl wydania, aby je zdobyć. Ci faceci są dość responsywni, ale musisz to zrobić bez działającego kodu lub po zakończeniu (1) lub (2).

Wybór jest bardzo łatwy (1). Może zbyt łatwe.

Myślę, że jest to dość powszechne, z niektórymi algorytmami, które mogą być ponownie zaimplementowane niż inne.

Istnieje trudny kompromis między tym, jak irytująca jest instalacja biblioteki, jak trudno jest samodzielnie wdrożyć algorytm, jak trudno jest go zoptymalizować i jak dobrze biblioteka odpowiada twoim potrzebom. Czasami używanie biblioteki to po prostu przesada: użyłem algorytmu powolnej bisekcji w jednym z moich programów, ponieważ zadzwoniłem do niego tylko kilka razy i nie chciałem dodawać biblioteki tylko do tego.

Czy łatwo jest napisać dobrze zoptymalizowaną wersję? Jeśli tak, lepiej być może. Dostaniesz dokładnie to, czego potrzebujesz i nie będziesz zależał od czyjejś pracy. Ale oczywiście naprawdę musisz wiedzieć, co robisz: nawet proste algorytmy mogą być trudne do wdrożenia.

Byłbym ciekawy badania na ten temat, ale z mojej stronniczej perspektywy naukowcy często używają bibliotek do algebry liniowej i generatorów liczb losowych, przy czym większość pozostałego kodu jest domowa.

Myślę, że implementacja algorytmu zamiast korzystania z biblioteki może czasem dać lepsze zrozumienie i kontrolę nad modelem. Kiedy koduję jakiś program do obliczeń naukowych, ważne jest, aby zrozumieć, co robię. Wdrożenie ważnych algorytmów pomaga mi lepiej poznać problem i uzyskać lepszą kontrolę nad nim.

Z drugiej strony czasem nie jest trywialnym zadaniem wybranie biblioteki, która jest potrzebna do uzyskania rozwiązania, więc lepiej jest szukać już zaimplementowanych algorytmów, gdy masz pewność, co chcesz osiągnąć i dlaczego tego chcesz.

Jeśli algorytmy są złożone, ręczne kodowanie daje możliwość poprawy wydajności / jakości rozwiązania za pomocą funkcji specyficznych dla zadania. A czasem trzeba nieco zmienić algorytm, co jest łatwiejsze, jeśli znasz kod, który napisałeś i możesz go edytować tak, jak chcesz.

Jedną odpowiedzią jest to, że istnieje tak wiele niewielkich zmian w kodzie numerycznym, że naprawdę trudno jest go zapisać w bibliotece. Weź to w porównaniu z oprogramowaniem internetowym, które często jest łatwe do zainstalowania i ma przejrzysty zestaw danych wejściowych i wyjściowych. Myślę, że bardziej powszechne jest, że ludzie chwytają framework lub dużą bibliotekę, która działa jak framework (Trilinos / PETSc) i używają tego ekosystemu, aby czerpać korzyści z używania kodów społeczności.

Przed podjęciem decyzji, czy korzystać z bibliotek, myślę, że chciałbyś również dowiedzieć się, w jakim stopniu użycie biblioteki pomoże Twojemu kodowi. Jeśli zamierzasz używać dobrze zoptymalizowanej biblioteki dla kluczowego jądra obliczeniowego, prawdopodobnie jest to o wiele bardziej wydajne niż próba napisania własnej.

Jeśli jednak piszesz specjalną procedurę, która zostanie wywołana tylko raz podczas wykonywania programu, dostosowanie kodu do struktury wymaganej przez bibliotekę może nie być opłacalne.

(Inna rzecz do przemyślenia: ile trzeba przebudować, aby skorzystać z biblioteki? Chyba że godziny pracy poświęcone na naprawę kodu są kompensowane przez odpowiedni wzrost wydajności lub dokładności numerycznej, może nie warto na dłuższą metę. Idealnie jest to jednak coś, co planujesz początkowo projektując struktury danych i algorytmy, aby „przepływ” biblioteki był brany pod uwagę od podstaw.)

Moje 2 centy.

Myślę, że łatwiej o tym pisać ogólnie niż o C / C ++. Po pierwsze, biblioteki w językach takich jak Python niekoniecznie są wykorzystywane do uzyskania korzyści w zakresie prędkości, nawet jeśli jest to konsekwencją. Myślę, że @David całkiem dobrze przedstawił przyczyny.

Biorąc to z góry, implementacja języka w pewnym stopniu decyduje o tym, do jakich bibliotek masz dostęp. Do najczęściej używanych języków w informatyce należą C, C ++, Python, Perl, Java, Fortran i R. Mniej powszechnymi przykładami mogą być Ocaml i Common Lisp. Ponieważ większość tych języków jest napisanych w C, mają naturalny interfejs funkcji obcych do C. Jednak nie jest tak łatwo wywołać, powiedzmy, bibliotekę Perl z Pythona lub odwrotnie. Więc w praktyce ludzie mają taką tendencję

1. Użyj biblioteki napisanej w języku implementacyjnym, zwykle coś, co jest częścią standardowych bibliotek lub w inny sposób powszechnie dostępne, lub

2. Wywołaj bibliotekę C / C ++ za pomocą języków FFI. Zakłada się, że opakowanie nie istnieje, ponieważ jeśli tak, nie można go łatwo odróżnić od (1).

(2) jest zwykle trudniejszy, ponieważ musisz sam zawinąć funkcję C / C ++. Ponadto musisz albo spakować bibliotekę, albo dodać dodatkową zależność. Z tego powodu ludzie częściej używają wbudowanych bibliotek językowych niż GSL, na przykład w C.

W przypadku bardzo ogólnych procedur, na przykład generowania losowych próbek z rozkładów, lub podstawowych procedur numerycznych, takich jak kwadratura całek, ponowne i proste użycie części biblioteki jest łatwe i powszechne. W miarę jak funkcjonalność, którą próbujemy wdrożyć, staje się bardziej złożona, staje się wykładniczo bardziej mało prawdopodobne, aby znaleźć dokładną funkcję, której pragnie w innej bibliotece, a nawet tak, można poświęcić dużo czasu na wyszukiwanie i wreszcie dostosowanie funkcji jako konieczne (styl / projekt kodu może na przykład stanowić problem). Jak wspomniano powyżej, można uzyskać dostęp tylko do podzbioru bibliotek. Z drugiej strony, wdrażanie samego algorytmu, jeśli jest on złożony, a nie jest głównym celem, może być zniechęcające i oczywiście trzeba poradzić sobie z tymi nieznośnymi problemami z szybkością.

Staje się to zatem problemem optymalizacji w analizie kosztów i korzyści. Z mojego doświadczenia wynika, że ​​nawet w przypadku stosunkowo standardowych technik, takich jak MCMC, zwykle kończę pisanie własnego kodu, ponieważ lepiej pasuje do tego, jak projektuję całe oprogramowanie.

Oczywiście, nawet jeśli nie użyjesz kodu, możesz uczyć się z kodu innej osoby. Nie wiem jednak, jak często naukowcy tak często to robią. Mam wrażenie, że czytanie kodu innych osób, aby się uczyć, jest raczej inżynierem oprogramowania.

Wracając do mojego drugiego kursu mechaniki, przychodzi mi do głowy, że po części dlatego, że wdrożyłem własne wersje dobrze znanych algorytmów, uczono mnie, jak to robić. Nie mogę wymyślić żadnego przykładu, w którym nauczyłem się, jak łączyć się z biblioteką i linkować do niej w ramach mojej dyplomowej fizyki. Pamiętam, jak po raz pierwszy zobaczyłem listę współrzędnych obracającej się piłki golfowej, po tym, jak samodzielnie obliczyłem rozwiązanie sprzężonych równań Newtona w FORTRAN. Pewne emocje i satysfakcja (a nawet duma) wynikają z obliczania rzeczy od zera.

Myślę, że należy w jak największym stopniu korzystać z testowanych bibliotek. Większość ludzi nie jest ekspertami w dziedzinie obliczeń numerycznych i prawdopodobnie nie będzie w stanie wdrożyć rozwiązania tak poprawnie i ostrożnie, jak to jest dostępne w dobrze przetestowanych bibliotekach. To powiedziawszy, jednak czasami zdarza się, że nie ma dostępnych bibliotek, które implementują kombinację możliwości potrzebnych w danej aplikacji. Widziałem to w dziedzinie technicznej, w której pracuję; istniejące kody nie rozwiązały wszystkich przypadków, a ktoś skończył implementować solver od zera, który to zrobił.

Podstawowym problemem jest często interfejs między aplikacją a biblioteką. Programista aplikacji ma wiedzę na temat problemu, który jest często tracony podczas przekazywania problemu (na przykład jako macierz) do biblioteki. Ta wiedza pozwala na wykorzystanie jej w większym stopniu niż przewyższa korzyści płynące ze stosowania wysoce zoptymalizowanej biblioteki. W rezultacie programista aplikacji „rzuca” własną implementację, która wykorzystuje tę wiedzę.

Tak więc naprawdę dobra biblioteka potrzebuje takiej wiedzy z aplikacji do biblioteki, aby również biblioteka mogła z niej skorzystać.

Oprócz wszystkiego, co już powiedziano powyżej, powtórzę moją odpowiedź z pytania „Fortran vs. C ++”: najcenniejszym zasobem programisty jest jej czas. Tak, zależności zewnętrzne są często niezręczne. Ale spędzanie czasu na ponownym wdrażaniu, debugowaniu i testowaniu algorytmów, które inni już zaimplementowali, jest prawie zawsze głupie, a wynik rzadko będzie tak dobry, jak kod napisany przez ekspertów na określony temat. Ponownie wykorzystaj to, co zrobili inni!

Grupa, z którą pracuję, korzysta z bibliotek w jak największym stopniu. Jestem jednym z niewielu programistów, a reszta ludzi zajęła się programowaniem w pracy. Znają wystarczająco dużo własnych ograniczeń, by wiedzieć, gdzie nie powinni się bawić. IMSL jest preferowaną biblioteką. Rzeczy takie jak GSL byłyby zabronione z powodu ograniczeń licencyjnych, nawet jeśli jest to agencja federalna i i tak rozdajemy nasze oprogramowanie.

„Ponowne użycie jest przede wszystkim zjawiskiem społecznym. Mogę korzystać z czyjegoś oprogramowania, pod warunkiem że

1. to działa
2. to jest zrozumiałe
3. może współistnieć
4. jest obsługiwany (lub jestem gotów sam go wesprzeć, w większości nie jestem)
5. jest ekonomiczny
6. Mogę to znaleźć.

„- B. Stroustrup, The C ++ Programming Language 2 ed. (1991) s. 383.

Inni podali kilka dobrych powodów, aby używać bibliotek, a także tworzyć własne procedury.

Czasami możesz przyspieszyć obliczenia dla konkretnej aplikacji, ponieważ wiesz z góry, że nigdy nie będziesz potrzebować szerokiego zakresu wartości, które obejmuje procedura biblioteczna, ani dokładności, jaką zapewniają te procedury.

Oczywiście wiele zależy od konkretnej aplikacji i tego, ile razy zostanie wywołana procedura biblioteki. Dlaczego miałbyś nazwać procedurę biblioteczną dla funkcji Bessela miliardy razy, jeśli potrzebujesz tylko kilku znaczących liczb dla małego zakresu x, a jakaś prostsza technika będzie wystarczająca dla twoich potrzeb?

Nie trzeba dodawać, musimy ponownie wykorzystywać kod, chodzi o trwałość kodu i wkład w społeczeństwo, ale to wszystko powyżej.

Powodem, dla którego nie używamy kodu ponownie jest to, że jeśli dopiero zaczynasz, programista jest trudny do zrozumienia dla innych kodów. Jest to szczególnie trudne w przypadku zaawansowanego C ++, a także możesz wykonywać pewne sztuczki w czystym C.

Bardzo często na początku rozumie się tę metodę, ale nie tak, jak jest ona zaimplementowana w bibliotece, lub po prostu jak korzystać z biblioteki z jej ogólnym interfejsem, kontrolą błędów i konwencjami, bardzo często udokumentowanymi dla doświadczonych programistów, jeśli w ogóle. Daje to złudzenie, że lepiej jest wdrożyć standardową metodę, taką jak faktoryzacja LU samodzielnie. Ponadto nowi programiści nie doceniają wartości testowania kodu, sprawdzania poprawności i przenośności dla różnych systemów operacyjnych. Ostatecznie powodem jest lenistwo, pisanie własnego kodu wygląda jak szybsze i łatwiejsze rozwiązanie.

Rzeczywistość jest taka, że ​​możemy nauczyć się więcej, używając i czytając kod niż programowanie od zera.

Lenistwo prowadzi mnie przez większość czasu, myślę też, że większość ludzi. Z tego samego powodu niektórzy piszą kod od zera, a inni korzystają z istniejących bibliotek.

Algorytmy bibliotek zapewniają w przeciwieństwie do własnych implementacji:

• Są ogólne i oparte na szablonach. Możesz później sparametryzować swoją implementację, nie martwiąc się o zmianę własnego kodu, który powinien mieć wiele ograniczeń.
• Istnieją nieczytelne i zdegenerowane przypadki danych wejściowych. Wiele algorytmów obliczeniowej geometrii, np. Wypukły kadłub, musi obsługiwać na przykład kolinearność trzech punktów. Możesz zignorować te przypadki, jeśli nigdy nie planujesz rozpowszechniać swojego kodu, a także nie chcesz często używać go w przyszłości.
• Zapewniają minimalną złożoność środowiska wykonawczego dla konfiguracji danych oczekiwanych lub w najgorszym przypadku. Algorytmy wyższego poziomu mają jako cegły konstrukcyjne często algorytmy niższego poziomu, np. Algorytmy sortowania lub specjalne typy danych. Szybkie sortowanie może być najczęstszym wyborem do sortowania danych, ale jeśli implementacja algorytmu musi gwarantować n (log (n)), nie możesz go użyć.
• Są wydajne w użyciu pamięci
• Są one dodatkowo zoptymalizowane w czasie działania
• Jeśli jest obsługiwany, zdecydowanie bardziej zamknięty, aby ogólnie był wolny od błędów, zwłaszcza jeśli pracujesz z gałęzią główną. Nic nie jest bardziej przetestowane niż dobrze rozproszona biblioteka. Nie każdy błąd ulega awarii, nie każdy błąd powoduje nieuzasadnione wyniki. Implementacja twojego algorytmu może nadal dawać akceptowalne wyniki, po prostu nie tak dobra, jak jest przeznaczona. Im mniej widoczny jest błąd, tym mniejsze jest prawdopodobieństwo, że Ty jako jedna osoba możesz go nawet wykryć.

Nadal uważam, że to dobrze, gdy wchodzisz do nowego pola, aby samodzielnie wdrożyć jedną wersję dobrze zrozumiałego algorytmu. W sumie zajmuję dużo czasu. Kupowałem i czytałem książki o imieniu Press i in. Zawsze czytam dużo teorii przed i podczas tych wdrożeń. A po zrozumieniu ogólnych koncepcji pola i doświadczeniu pułapek w praktyce nadszedł czas, aby przejść do wszystkich lepszych implementacji bibliotek. Myślę, że staniesz się lepszym użytkownikiem biblioteki, jeśli sam napiszesz algorytm „witaj świecie” w polu bibliotek.

Jeśli pracujesz w większym zespole, może to nie być twój wybór, niezależnie od tego, czy Twój zespół korzysta z konkretnej biblioteki, czy nie. Zespół podstawowy może podjąć decyzję. I może być osoba odpowiedzialna za oprawę biblioteki w twoim projekcie z jej własnymi planami czasowymi. Przepisanie jednego algorytmu, który możesz zrobić z własnym planowaniem czasu, bez polegania na decyzjach innych ludzi.

Jeśli jesteś sam i lubisz rozpowszechniać, istnieje inny problem. Uważam, podobnie jak wiele innych kodów źródłowych, za najbardziej użyteczny zasób. Zgadza się tutaj wielu informatyków. W dziedzinie stosowanej poza informatyką może być konieczne zapewnienie wstępnie skompilowanego programu możliwego do zainstalowania w systemie Windows. Pod Linuksem możesz samodzielnie stosunkowo łatwo skonfigurować rzeczy w przypadku bibliotek użytkowania open source.

Samodzielne przepisywanie algorytmu daje swobodę lisence. Twój projekt może na przykład nie obsługiwać licencji GSL na licencję GPL .

Lisence może być jedynym ograniczeniem niezależnym od punktu widzenia reseacherów.