Czy wygładzoną analizę stosuje się poza środowiskiem akademickim?

24

Czy wygładzona analiza znalazła zastosowanie w analizie głównego strumienia algorytmów? Czy projektanci algorytmów często stosują wygładzoną analizę do swoich algorytmów?

algorithms complexity-theory algorithm-analysis Gilles „SO- przestań być zły”
źródło
11
Czy ludzie stosują jakąkolwiek analizę złożoności swoich algorytmów poza środowiskiem akademickim?
Dave Clarke
2
Co mówi @DaveClarke; może powinien poprosić o rygorystyczne (lub nietrywialne) analizy. Oczekuję, że wielu praktyków spojrzy na swoje algorytmy, policzy głębokość zagnieżdżenia pętli i powie: „To !”. O(n3))
Raphael
3
Szukając jakiegokolwiek zastosowania wygładzonej analizy innej niż Simplex, znalazłem listę wyselekcjonowaną przez jednego z facetów, którzy odkryli tę technikę.
Raphael
1
@DaveClarke co powiesz na osoby pracujące w IBM, HP lub NTT? Czy nie powinni używać tego rodzaju analiz?
Marcos Villagra
1
@DaveClarke I tak.
Kevin

Odpowiedzi:

12

Mogę się mylić, ale uważam, że wygładzona analiza jest sposobem na wyjaśnienie praktycznego zachowania algorytmów, które mają złe gwarancje teoretyczne (simpleks, k-średnie itd.). Nie jestem pewien, co to znaczy stosować wygładzoną analizę w praktyce, poza usprawiedliwieniem użycia określonej heurystyki o złej wydajności w najgorszym przypadku („Moja heurystyka ma bla bla bla najgorsze zachowanie, ale wygładzona analiza wskazuje, że będzie radzić sobie dobrze w praktyce itp. ”)

Suresh
źródło
2
Problem polega na tym, że do tej pory wielkie sukcesy w zakresie wygładzania analiz polegały na wyjaśnianiu obecnej praktyki, więc praktykujący mogliby po prostu zareagować, mówiąc „dobrze, że wszystko, co robiłem, może mieć sens” :). Nie wiem, czy ktoś zdecydował się na użycie mniej znanego heurystycznego PONIEWAŻ wygładzonej analizy.
Suresh,
Formalna wygładzona analiza jest bardzo trudna, nie ma powodu, dla którego nikt nie w teorii powinien ją ćwiczyć. Z drugiej strony, jeśli uważasz, że jest to heurystyka używana do analizy algorytmu (mianowicie dane wejściowe są pół losowe), to prawdopodobnie jest używana cały czas.
Yuval Filmus
3

Sposób, w jaki ludzie analizują algorytmy w prawdziwym świecie, znacznie różni się od środowiska akademickiego. Podczas gdy w środowisku akademickim celem jest znalezienie możliwej do udowodnienia górnej granicy czasu działania, w prawdziwym życiu celem jest zrozumienie, jak działa algorytm i jakie poprawki mogą poprawić czas działania. Istnieją dwie główne metody, które są zakazane w środowisku akademickim, ale stosowane w praktyce:

  • Metoda aproksymacji. Tutaj używasz wielu uproszczonych założeń, aby spróbować prognozować czas działania algorytmu. Podobne do tego, co robią fizycy teoretyczni.
  • Eksperymentowanie. Uruchamiasz algorytm i mierzysz kilka statystyk - ile czasu poświęcono każdej części, ile razy została wywołana każda funkcja, jak często uruchamiano każdą gałąź itd. Informacje te można wykorzystać do optymalizacji algorytmu. Eksperymentowanie służy również do ustalenia, czy niektóre przybliżenia dokonane podczas analizy algorytmu działają w praktyce, czy nie.

To powiedziawszy, nie sądzę, że analiza algorytmu w praktyce jest bardzo powszechna poza dodawaniem tekstu uzupełniającego w powiązanej publikacji akademickiej. Nacisk kładziony jest na inżynierię oprogramowania lub optymalizację niskiego poziomu, w zależności od przedmiotu.

Wreszcie, wygładzona analiza jest heurystyką, którą można wykorzystać do wyjaśnienia, dlaczego algorytmy działają lepiej w praktyce, niż sugerowałby ich najgorszy przypadek - mianowicie, ponieważ niektóre dane wejściowe są w pewnym sensie „losowe”. Tę heurystykę można wykorzystać do przybliżenia zachowania algorytmu, jeśli stosuje się metodę aproksymacji.

Yuval Filmus
źródło
„Podczas gdy w środowisku akademickim celem jest znalezienie provably-poprawna górna granica w czasie jazdy” - czyli cel, nie cel. Przeciętna analiza przypadków jest również bardzo pracochłonna, nawet jeśli przeciętny student CS może jej nie zobaczyć (ponieważ jest to stosunkowo trudne). „Zrozumienie, jak działa algorytm” jest prawdopodobnie podstawą wszystkich algorytmów w środowisku akademickim.
Raphael