Jsou konstantní čas a amortizovaný konstantní čas skutečně považovány za rovnocenné?

Amortizovaný konstantní čas lze téměř vždy považovat za ekvivalent konstantního času a bez znalosti specifik vaší aplikace a typu použití, které plánujete udělat v této frontě je velká šance, že vás pokryje.

Seznam polí má koncept kapacity , která se v zásadě rovná největší velikosti / délce / počtu položek, které kdy to bylo dosud požadováno. Co se tedy stane, je to, že na začátku se seznam polí bude stále přerozdělovat, aby se zvýšila jeho kapacita, jak do něj budete přidávat položky, ale v určitém okamžiku bude průměrný počet položek přidaných za jednotku času nevyhnutelně odpovídat průměrnému počtu položek odstraněno za jednotku času (jinak by vám nakonec stejně došlo paměť), kdy se pole přestane přerozdělovat a všechny přílohy budou splněny v konstantní době O (1).

Nicméně , mějte na paměti, že ve výchozím nastavení není náhodné odebrání ze seznamu polí O (1), je to O (N), protože seznamy polí přesouvají všechny položky za odstraněnou položkou o jednu pozici dolů, aby nahradily odstraněnou položku . Abyste dosáhli O (1), budete muset přepsat výchozí chování a nahradit odstraněnou položku kopií poslední položky seznamu matic a poté odebrat poslední položku, aby nebyly přesunuty žádné položky. Pokud to ale uděláte, už přesně nemáte frontu.

Komentáře

• Sakra, dobrá poznámka k odstranění; O tom jsem ‚ neuvažoval. A protože ‚ náhodně odstraňujeme prvky, neznamená to ‚ technicky to ‚ Už v tomto smyslu už frontu nemáte?
• Ano, znamená to, že s ní ve skutečnosti zacházíte jako s frontou. Ale nevím, jak plánujete najít položky k odstranění. Pokud váš mechanismus jejich hledání očekává, že budou přítomni ve frontě v pořadí, v jakém byly přidány, máte smůlu.Pokud vás nezajímá, zda se pořadí položek zkomolilo, pak jste v pořádku.
• Očekává se, že můj RandomQueue implementuje Queue rozhraní a pro dodanou metodu remove namísto vyskakování hlavy náhodně odstranit, takže by nemělo být ‚ nemůžeme se spoléhat na konkrétní objednávku. Myslím, že vzhledem k jeho náhodné povaze by pak uživatel neměl ‚ očekávat, že bude udržovat jakýkoli konkrétní řád. Citoval jsem zadání ve své otázce pro objasnění. Děkuji.
• Ano, zdá se, že budete v pořádku, pokud se ujistíte, že odebrání položky proběhlo způsobem, který jsem navrhl.
• Poslední věc, pokud ‚ nevadí. ‚ Už jsem to víc přemýšlel a ‚ se to nezdá ‚ Je možné mít “ true “ O (1) doplňky a “ true “ O (1) náhodné odstranění; to ‚ ll být kompromis mezi 2. Buď máte jednotlivě přidělenou strukturu (jako pole), která poskytuje odstranění, ale ne additon, nebo strukturu přidělenou chunk jako Linked- Seznam, který poskytuje doplňky, ale ne odstranění. Je to pravda? Ještě jednou vám děkuji.

Zdá se, že otázka konkrétně vyžaduje konstantní čas, nikoli amortizovaný konstantní čas . Pokud jde o citovanou otázku, ne, nejsou ve skutečnosti stejné *. Jsou však v reálných aplikacích?

Typickým problémem s amortizovanou konstantou je, že příležitostně musíte zaplatit nahromaděný dluh. Takže zatímco vložky jsou obecně konstantní, někdy musíte trpět režií opětovného vložení všeho, když je přidělen nový blok.

Kde je rozdíl mezi konstantním časem a amortizovanou konstantní dobou relevantní pro aplikaci, závisí na tom, zda tato občasná velmi pomalá rychlost je přijatelná. Pro velmi velký počet domén je to obecně v pořádku. Zejména v případě, že kontejner má efektivní maximální velikost (jako jsou mezipaměti, dočasné vyrovnávací paměti, pracovní kontejnery), můžete efektivně zaplatit, že stojí během provádění pouze jednou.

V kritických aplikacích mohou být tyto časy nepřijatelné. Pokud je od vás požadováno splnění krátkodobé záruky obratu, nemůžete se spolehnout na algoritmus, který jej občas překročí. Na takových projektech jsem pracoval již dříve, ale jsou mimořádně vzácné.

Záleží také na tom, jak vysoké jsou tyto náklady. Vektory mají tendenci podávat dobrý výkon, protože jejich náklady na realokaci jsou relativně nízké. Pokud však přejdete na hashovací mapu, může být realokace mnohem vyšší. I když pro většinu aplikací je to pravděpodobně v pořádku, zejména servery s delší životností s horní hranicí u položek v kontejneru.

* Tady je ale trochu problém. Aby bylo možné vytvořit jakýkoli univerzální kontejner být konstantní čas pro vložení jedné ze dvou věcí musí platit:

• Kontejner musí mít pevnou maximální velikost; nebo
• můžete předpokládat, že alokace paměti jednotlivých prvků je konstantní čas .

Komentáře

• “ jaterní server “ se zde jeví jako podivné fráze. Myslíte snad “ živý server “ snad?

Záleží – na tom, zda optimalizujete propustnost nebo latenci:

• Latence- citlivé systémy vyžadují konzistentní výkon. U takového scénáře musíme zdůraznit chování systému v nejhorším případě. Příkladem jsou měkké systémy v reálném čase, například Hry, které chtějí dosáhnout konzistentní snímkové rychlosti, nebo webové servery, které musí poslat odpověď v určitém krátkém časovém rámci: plýtvání cykly CPU je lepší než zpoždění.
• Systémy optimalizované na propustnost se nestarají příležitostné stánky, pokud lze z dlouhodobého hlediska zpracovat maximální množství dat. Zde se primárně zajímáme o amortizovaný výkon. To je obecně případ křupání čísel nebo jiných dávkových úloh zpracování.

Všimněte si, že jeden systém může mít různé komponenty, které musí být kategorizovány odlišně. Např. moderní textový procesor by měl vlákno uživatelského rozhraní citlivé na latenci, ale vlákna optimalizovaná propustností pro jiné úkoly, jako je kontrola pravopisu nebo export PDF.

Také algoritmická složitost často nezáleží na tom, jak moc bychom mohli přemýšlejte: Když je problém vázán na určitý počet, pak jsou skutečné a měřené výkonnostní charakteristiky důležitější než chování „pro velmi velké n “.

Komentáře

• Bohužel mám velmi malé zázemí.Otázka končí: “ Operace add (x) a remove () v RandomQueue by měly běžet v konstantním čase na operaci „.
• @Carcigenicate, pokud nevíte, že je systém citlivý na latenci, použití amortizované složitosti k výběru datové struktury by mělo být naprosto dostačující.
• Mám dojem, že by to mohlo být programovací cvičení nebo test. A určitě ne snadný. Absolutně pravda, že na tom záleží jen velmi zřídka.

Pokud budete požádáni o „amortizovaný konstantní čas“ algoritmus, může váš algoritmus někdy trvat dlouho. Například pokud použijete std :: vector v C ++, takový vektor může mít přidělený prostor pro 10 objektů, a když přidělíte 11. objekt, přidělí se místo pro 20 objektů, zkopíruje se 10 objektů a 11. se přidá, což trvá hodně času. Pokud ale přidáte milion objektů, můžete mít 999 980 rychlých a 20 pomalých operací, přičemž průměrný čas je rychlý.

Pokud budete požádáni o algoritmus „konstantního času“, musí být váš algoritmus vždy rychlý pro každou jednotlivou operaci. To by bylo důležité pro systémy v reálném čase, kde můžete potřebovat záruku, že každá jednotlivá operace je vždy rychlá. „Konstantní čas“ není často nutný, ale rozhodně není stejný jako „amortizovaný konstantní čas“.