it-swarm-eu.dev

Je big-O opravdu relevantní při práci v průmyslu?

V každém rozhovoru jsem byl v, byl jsem vyslýchán na matematickou analýzu složitosti, včetně big-O zápis.

Jak důležitá je analýza velkých O pro vývoj v průmyslu? Jak často jej opravdu používáte a jak je nutné mít k problému honosné myšlení?

66
MM01

Moje otázka zní, jak relevantní je tento test pro vývoj v průmyslu?

Pro návrh škálovatelných algoritmů, aplikací a systémů je nezbytné důkladné pochopení teorie výpočetní složitosti (např. Velké O notace). Vzhledem k tomu, že škálovatelnost je velmi důležitá pro výpočetní techniku ​​v průmyslu, je velká O notace také.

Jak často jej opakovaně používáte a jak je nutné mít pro tento problém honosnou mysl?

Závisí to, co tím myslíš „reeeally use“. Na jedné straně nikdy nedělám formální důkazy o výpočetní složitosti softwaru, který píšu. Na druhou stranu, většinu dní se musím zabývat aplikacemi, u nichž je škálovatelnost potenciálním problémem, a rozhodnutí o návrhu zahrnují výběr (například) vhodných typů kolekce na základě jejich složitosti.

(Nevím, zda je možné důsledně implementovat škálovatelné systémy bez solidní chápání teorie složitosti. Chtěl bych si myslet, že tomu tak není.)

76
Stephen C

Důvod je ten, že indikuje škálovatelnost .

Proces, který je O (n ^ 2), bude škálovat horší než ten, který je O (n log n), ale lepší než jeden v O (n ^ 3) nebo dokonce O (n!).

Pokud tyto rozdíly neznáte, a pokud se použijí, jste méně vhodní pro výběr správných implementací funkčnosti a pro extrapolaci výkonu testu na výkon výroby.


ÚPRAVA: Porovnání 48n s n ^ 3 z http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (což v tah je od Programming Pearls)

enter image description here

36
user1249

Záleží na tom, co děláte.

Pro vývojáře webu (jako je já) to obvykle hodně záleží. Chcete webové aplikace v měřítku. Pokud má aplikace úzký profil, který je v měřítku s O (n ^ 2), a myslíte si, že je to v pořádku, protože váš server dokáže zvládnout 1 000 současných uživatelů, zdá se, že vám to nemusí záležet. Jde o to, že abyste zvládli jen dvakrát tolik (což je pravděpodobné, že se stane právě přes noc), budete potřebovat čtyřnásobek výpočetní síly. V ideálním případě chcete, aby se webové aplikace škálovaly na O (n), protože hardware je levný při rozumném konstantním poměru uživatel/server.

Obecně v aplikacích, kde máte 100 000 objektů, přijde velká O a sní vás. Jste nesmírně zranitelní vůči vrcholům. Například v současné době pracuji na 3D hře, což je aplikace, která zpracovává spoustu dat. Kromě vykreslování máte kolizní kontrolu, navigaci atd. Nemůžete si dovolit jen jít zjevnou cestou. Potřebujete efektivní algoritmy, potřebujete hodně ukládání do mezipaměti, takže ty méně efektivní odepisují. A tak dále.

Pokud samozřejmě děláte něco jako vytvoření mobilní aplikace spojením grafického uživatelského rozhraní s návrhářem rozhraní, propojení s některými webovými službami a to je vše, nikdy nebudete mít problémy se složitostí. Protože webové služby, které voláte, se o to již starají.

32
back2dos

Nikdy jsem ve svém pracovním životě formálně neuplatňoval pravidlo.

S tímto konceptem však musíte být obeznámeni a použít jej intuitivním způsobem při každém návrhu algoritmu.

Pravidlo je:

Měli byste být dostatečně obeznámeni s notací, abyste mohli pro daný úkol určit, zda je nutné jej formálně vypočítat, nebo stačí to intuitivně vyhodnotit, nebo pokud jej můžete úplně přeskočit. Stejně jako mnoho jiných základních matematických konceptů.

22
Wizard79

Možná, možná vám trochu povídá, proč je to DEFINITELY IS nutný:

V projektu, na kterém jsem pracoval, existoval program zodpovědný za tisk všech druhů dokumentů (štítky, seznamy atd.). Tento program se skládal ze dvou částí, z nichž jedna četla všechna potřebná data z databáze a zapisovala je do soubor ve stylu .ini a další část, která tyto soubory čte a vyplňuje je do šablon. To fungovalo přiměřeně dobře pro štítky a malé seznamy (jen s několika poli), ale to trvalo téměř 10 minut, když muselo tisknout „velký“ seznam ~ 20 stránek. Protože přístup k těmto souborům ini vedl k O (n²) přístupovým dobám, n je počet polí k tisku.

Kdyby původní programátoři tohoto programu rozuměli O-notaci, nikdy by to neudělali. Nahrazení této hlouposti hashtableem z ní učinilo soooooooo mnohem rychlejším.

10
user281377

Big-O výkon je důležitý, ale byl z velké části internalizován.

Big-O výkon třídění a vyhledávání nezáleží, protože lidé obvykle používají systémy dodávané systémem, a ty budou stejně dobré, jak mohou být (vzhledem k tomu, že musí být obecně užitečné). Existují datové struktury, které jsou efektivnější pro různé věci, ale ty lze obvykle vybrat na obecných principech (a obvykle jsou zabudovány do moderních jazyků). Tam je nějaký smysl algoritmů, které dělají nebo nemají měřítko.

Výsledkem je, že formální otázky se v praxi vyskytují jen zřídka, ale praxe je postavena na stejných principech.

8
David Thornley

IMHO mnoho programů počítačové vědy nechává mnoho studentů putovat tam dole v plevele. Tyto programy nikdy zcela nesdělují celkový obraz toho, o čem je věda o výpočtech. Studenti vstupují do průmyslu a potýkají se s tím, jak aplikovat koncepty, které se naučili, s malým pochopením toho, jak se vztahují ke skutečnému světu.

Řekl bych, že jádrem vědy o výpočtech je schopnost uvažovat o výpočtech. Naučíte se různé metody a techniky, jak toho dosáhnout, a aplikovat je na abstrahované problémy, které jsou prototypem primitivů nalezených v mnoha problémech skutečného světa. Trik spočívá v nalezení těchto prototypických primitiv v reálném světě, a pak o důvodech, jako je korektnost, složitost, čas atd., Které, jak se můžete shodnout, jsou skutečné problémy, s nimiž se musíte obávat. Vhled do toho, jak se části chovají, vám často poskytuje vhled do toho, jak se chová celá část. A stejné obecné metody a techniky lze také použít na celek, jen ne se stejnou přísností, jakou mají menší, dobře abstrahované a dobře definované části. Ale nakonec, věda o výpočtech, vám dává schopnost dělat rozumné rozhodnutí o tom, jak zařídit výpočet, se skutečným vhledem, jak se bude chovat za různých podmínek.

7
Ziffusion

Memo pro sebe !:

Já a mnozí další se ptáme sami sebe na tuto otázku pravidelně.

Myslím, že skutečný důvod, proč se ptáme, je ten, že jsme byli líní.

Tyto znalosti nikdy nebudou randit nebo se stanou zastaralými. Nesmíte použít přímo každý den, ale budete je používat podvědomě a bude to mít pozitivní vliv na vaše rozhodnutí o návrhu. Jednoho dne vám může ušetřit hodiny i dny kódování.

Protože další problémy jsou zapouzdřeny knihovnami a nástroji třetích stran a jsou k dispozici stále více vývojářům, budete muset tyto znalosti znát, abyste se odlišili od ostatních a pomohli vyřešit nové problémy.

5
Conor

Spíš ne. V podstatě jediný čas, kdy jsem o tom přemýšlel, je při přístupu k databázi. Obvykle se podívám na kód a řeknu: „To dělá n + 1 dotazů, měli byste ho změnit tak, aby udělal jen 1 nebo 2“

Protože všechna moje data jsou čtena z databáze a zobrazena uživateli, snažím se minimalizovat množství dat, se kterými pracuji, do té míry, že rozdíl mezi lineárním a O (n ^ 2) algoritmem je dost zanedbatelný.

Pokud dojde k nějakému problému, vytvoříme profil a opravíme jej později.

5
Greg

Tři otázky, které jste položili, a myslím, že odpovědi ve formě krátkých formulářů by mohly pomoci dosud předloženým argumentům.

Jak relevantní je tento test pro vývoj v průmyslu?

Závisí na odvětví.

Kdekoli je problémem rychlost kódu nebo kódový prostor, je to zcela relevantní pro dané odvětví. Často potřebujete vědět, jak dlouho bude rutina trvat, nebo kolik paměti (on/offline) bude vyžadovat.

Jak často jej opakovaně používáte?

Závisí na odvětví.

Pokud se výkon a škálování netýkají dané úlohy, pak jen zřídka, pouze v případě vážného nedostatku výkonu. Pokud jste inženýrem pro vysoce používaný kritický systém, pravděpodobně každý den.

Jak je nutné mít pro tento problém honosnou mysl?

Je to naprosto nezbytné.

Možná budete muset použít každý den, nebo pouze za zlých okolností; ale někdy to bude potřeba. Přednostně během návrhu před přijetím problému, než zoufale profilování systému dusivek.

3
Orbling

Řekl bych, že je to velmi časté. Obecně neprokazujeme , že něco má zvláštní big-O, ale my jsme internalizovali myšlenku a zapamatovali si/seznámili se s big-O zárukami pro konkrétní datové struktury a algoritmy a pro konkrétní použití vybíráme ty nejrychlejší. Pomáhá to mít knihovnu, která je plná všech možností, jako je Java knihovna sbírek nebo C++ STL). Implicitně a přirozeně používáte big-O každý den = když se rozhodnete použít Java.util.HashMap (O(1) vyhledávání) místo Java.util.TreeMap (O(lg n) vyhledávání) a rozhodně se rozhodnete nespustit lineární hledejte v Java.util.LinkedList (O(n) lookup) něco, kde nepotřebujete tříděný přístup.

Když si někdo vybere suboptimální implementaci a někdo, kdo ví lépe, přijde a uvidí svůj kód, je to součástí našeho slovníku, který je opraví „vaše implementace zabírá kvadratický čas, ale můžeme to udělat až na n-log-n čas tím, že to uděláme tímto způsobem “tak přirozeně a automaticky, jako bychom používali anglický jazyk k objednání pizzy.

3
Ken Bloom

Ano

Možná nebudete muset dělat formální analýzy, ale alespoň rozumné pochopení pořadí složitosti algoritmů - a jak porovnat dva algoritmy kolem toho - je rozhodující, pokud chcete dělat netriviální práci a nechat ji dopadnout dobře.

Pracoval jsem na dvou různých systémech, které se v počátečním vývoji zdály v pořádku, ale hardware přišel na kolena při testování výroby, protože někdo použil algoritmus O (n ^ 2). A v obou případech šlo o triviální změnu algoritmu O(n)).

3
Bob Murphy

Pravděpodobně se používá na místech, kde vyvíjejí API pro spotřebu. C++ STL je jedno z mála API, které má na své algoritmy omezení složitosti. Ale pro každodenní pracovní programátora/programátora/designéra/architekta to moc neprochází.

1
sashang

Nezjistil jsem, že je to důležité, kromě komunikace nápadů, a pracuji v oblastech kritických pro výkon (raytracing, zpracování obrazu a sítí, částicové systémy, fyzikální motory atd.) A musel jsem vymyslet mnoho proprietárních algoritmů a datových struktur při práci ve výzkumu a vývoji. V těchto oblastech může hrst velmi efektivních datových struktur a algoritmů přinést zcela nové produkty Cut-Edge, zatímco včerejší algoritmy způsobují zastaralost stávajících produktů, takže vždy existuje snaha dělat věci efektivněji. Jako upozornění jsem však nikdy nezveřejnil žádné dokumenty o algoritmech, které jsem vymyslel. Všichni byli vlastníci. Kdybych to udělal, potřeboval bych pomoci matematika, aby formuloval důkazy atd.

Přesto se domnívám, že množství výpočetní práce na iteraci je často bezprostřednějšího zájmu než škálovatelnost algoritmu, ledaže by algoritmus skutečně špatně škáloval. Pokud někdo přijde s technikou pro řezání paprsků pro raytracing, zajímám se spíše o výpočetní techniky, jako je to, jak představují a přistupují k datům, než o algoritmickou složitost, protože v tomto konkurenčním a inovativním scénáři je již dána přiměřená škálovatelnost. Nemůžete být konkurenceschopní, když přijdete s algoritmy, které se nezmění.

Samozřejmě, pokud porovnáváte kvadratickou složitost s linearithmicem, je to obrovský rozdíl. Ale většina lidí v mém oboru je dostatečně schopná, aby se vyhnul použití algoritmu kvadratické složitosti na epický vstup. Škálovatelnost je tedy často hluboce zahrnuta a významnější a zajímavější otázky vypadají takto: „Použili jste GPGPU? SIMD? Běží paralelně? Jak jste reprezentovali data? Reorganizovali jste je pro mezipaměť? přístupové vzory? Kolik paměti zabere? Dokáže to v tomto případě spolehlivě zvládnout? Odkládáte určité zpracování nebo to děláte najednou? "

Dokonce i linearithmický algoritmus může překonat algoritmus lineárního času, pokud první z nich přistupuje k paměti optimálnějším způsobem, například, nebo je vhodnější pro vícevláknové zpracování a/nebo SIMD. Někdy dokonce lineární algoritmus může překonat logaritmický algoritmus z těchto důvodů, a přirozeně lineární-čas algoritmy překonají logaritmické pro teeny vstupy.

Záleží mi tedy na tom, co někteří lidé nazývají „mikrooptimalizace“, jako jsou reprezentace dat (rozložení paměti, přístupové vzorce s rozdělením na horké/studené pole atd.), Multithreading, SIMD a občas GPGPU. V oblasti, kde je každý již dostatečně schopný používat slušné algoritmy pro řezání Edge pro všechno s novými publikovanými novinami, vaše konkurenční Edge v bitvě s algoritmickými průvodci nepochází ze zlepšení algoritmické složitosti natolik, aby byla přímější výpočetní účinnost.

V mém oboru dominují brilantní matematici, ale ne vždy ti, kteří znají výpočetní náklady na to, co dělají, nebo mnoho triků na nižší úrovni, aby urychlili kód. To je obvykle moje Edge nad nimi při vymýšlení rychlejších a přísnějších algoritmů a datových struktur, přestože moje je mnohem méně sofistikovaná. Hraju to, co se hardwaru líbí, směrem k bitům a bajtům a dělám každou iteraci práce mnohem levnější, i když dělám několik dalších iterací práce než skutečně sofistikovaný algoritmus - práce v mém případě je drasticky levnější. Kód, který píšu, je také mnohem jednodušší. Pokud si lidé myslí, že mikrooptimalizované verze přímých algoritmů a datových struktur je obtížné pochopit a udržovat, zkuste porozumět a udržovat sbírku exotických algoritmů a datových struktur souvisejících s exotickými sítěmi, které nikdy předtím v oboru neviděli, s 20stránkovými papíry, které matematicky popisují jejich kroky .

Jako základní příklad jsem přišel s jednoduchou strukturou mřížky, která nakonec překonala strom KD v naší společnosti pro detekci kolizí a odstranění nadbytečných bodů. Moje hloupá hrubá mřížka byla mnohem méně sofistikovaná algoritmicky a já jsem mnohem hloupější matematicky a algoritmicky než ten, kdo implementoval strom KD svým novým způsobem, jak najít střední bod, ale právě jsem vyladil využití mřížky a přístupové vzorce a to stačilo k překonání něčeho mnohem sofistikovanějšího.

Další hrana, která mi umožňuje přežít v oblasti, ve kterém dominují lidé mnohem chytřejší než já, je opravdu pochopení toho, jak uživatel pracuje, protože používám software, který vyvíjím stejným způsobem. To mi dává nápady na algoritmy, které se opravdu okamžitě přizpůsobí zájmům uživatelů. Jako základní příklad se většina lidí snaží zrychlit věci, jako je detekce kolizí, pomocí prostorového indexování. Téměř před několika desítkami let jsem udělal jednoduché pozorování, které formovalo kariéru, u organických modelů, které, například, pokud postava položí ruce na obličej, by struktura prostorového indexování chtěla rozdělit uzly a provést drahé aktualizace, pokud by postava pak sundal ruku z obličeje. Pokud místo toho rozdělujete oddíly spíše na základě údajů o připojení než na vrcholných pozicích, můžete skončit se stabilní hierarchickou strukturou, která se aktualizuje velmi rychle a nikdy není třeba strom rozdělit nebo znovu vyvážit (pouze musí ohraničující pole aktualizovat každý snímek animace). .. věci jako tohle - algoritmy, s nimiž by dítě bez těžkého matematického zázemí mohlo přijít, kdyby rozumělo pouze základnímu konceptu, ale těm, které matematikům unikly, protože nemysleli na věci tak blízko k tomu, jak uživatelé pracoval a příliš přemýšlel jen o vlastnostech geometrie a ne o tom, jak byla geometrie běžně používána. Vycházím dostatečně dobře tím, že se opírám spíše o obecné výpočetní znalosti a uživatelské znalosti než o algoritmické kouzlo. Takže jsem opravdu nenašel, že je důležité soustředit se na algoritmickou složitost.

1
user204677

Nikdy nemyslím na velké O v matematické perspektivě, nikdy na velké O vůbec nepřemýšlím, pokud se nás to nezeptá. Vidím jen algoritmus v hlavě a můžu říct, jestli je to špatné, protože to dělá více smyček v paměti pro každý N, nebo jestli se dělí a dobývá nebo něco podobného. V případě potřeby to dokážu přeložit do velké O notace za pár sekund, ale pro mě je jednodušší vědět, jak algoritmus/kontejner pracuje s pamětí, než přemýšlet o matematické perspektivě.

0
Coder

Ano, v tomto odvětví je složitost důležitá. Pokud skončíte navrhováním něčeho, kde se kritická cesta změní na N-kvadrát (zdvojnásobení počtu něco způsobí, že systém bude čtyřikrát načten), zasáhnete váš problém se škálováním mnohem rychleji, než kdybyste měli něco, co by se škálovalo na N.

Obvykle se však neprovádí jako řádný, formální, důkaz, že něco je v dané složitosti, takže dobrá intuice pro to, jak složitá je struktura operací, je dobrým začátkem.

0
Vatine