Je možné najít náhodný prvek Sada v konstantním čase?

hlasů
3

Tak jsem narazil na problém pro stavební sadu funkcí getRandomElement (). snadné na první pohled. Ale čím víc jsem o tom přemýšlet, tím méně si myslím, že je možné to udělat v O (1) časová náročnost. Nebyl dán požadavek na konstantní čas, ale všechny z několika sad hlavní funkce je v konstantním čase, takže mám pocit, jako by to znamenalo, že by to mělo být provedeno v konstantním čase.

Cílem souboru je pro funkci hash, který má snížit kolizím. Problém se stává, že když si prostě generování náhodných celých čísel a pokusit se zvolit indexu pomocí této náhodné číslo, budete s největší pravděpodobností narazit na „prázdný“ slot ve svém setu .... V takovém případě je nutné vygenerovat nové náhodné číslo a zkusit znovu. V podstatě tím lepší hashovací funkce, nejhorší váš getRandomElement vystoupí použití tohoto přístupu.

Tak jsem si myslel, ... jo, proč ne uložit indexy po každém vložení? Potom generovat náhodné číslo a vyberte index z této kolekce indexů. Myslel jsem, že to byl dobrý nápad, ale pak přijde problém s odstraněním prvků. Rádi bychom také muset odstranit odpovídající index z našeho seznamu indexů, stejně jako odstranění prvek sám z naší sady. Jak můžeme najít správný index odstranit rychleji než lineárního času ???

Mimochodem, dostat náhodný prvek ze sady pocit, že může být provedeno lépe než lineárního času. Btw, já manipulaci kolize řetězení. Nechci ztrácet čas se snaží dělat to, co je matematicky nemožné, ale jsem také není matematik a nechci se vzdát něčeho, co ve skutečnosti je to možné.

Položena 20/10/2018 v 12:35
zdroj uživatelem
V jiných jazycích...                            


1 odpovědí

hlasů
5

Ano, je možné vytvořit datové struktury nastavenou podobné, který podporuje O (1) provozu getRandomElement. Máte pravdu o uložení prvků v matici. Problém odstranění prvků není příliš obtížné.

Tajemství je komprimovat pole, jakmile počet děr je příliš velký (řekněme více než polovina velikosti pole). Tímto způsobem Amortizovaná doba vypuštění je stále O (1).

Při provádění getRandomElement(), jen zopakovat, dokud nenarazíte aktuální prvek. Průměrný počet opakování není větší než 2, protože pole je vždy alespoň z poloviny plná, takže máte stále svůj O (1) průměrnou dobu potřebnou pro getRandomElement().

Edit: možná jednodušší způsob mazání prvků by bylo přesunout poslední prvek na uvolněné místo.

Odpovězeno 20/10/2018 v 13:18
zdroj uživatelem

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more