Diskuze: Speciální druh kolekce

Petr Šťastný

Tvůrce

Petr Šťastný:2.11.2017 23:39

Ahoj, napadl mě jeden velmi rychlý algoritmus, který bych rád zužitkoval ve svých programech, ale problém je, že potřebuje k fungování poměrně specifický druh kolekce. Kolekce musí umět:

Rychle skákat na index (jako klasické pole)
Přidávat prvky mezi určité pozice (jako linkedlist)

Napadl mě list, ale do toho se přidávají prvky strašně pomalu. U linkedlistu zase nemůžu rychle skákat na index.
Zatím jsem to obcházel polem, které bylo strašně velké. Do něj jsem házel na určité pozice prvky a prázdné pozice potom vymazal. Ale pole bylo strašně veliké a maximální velikost prostě nestačila. Vím, že bych si mohl naprogramovat mnohem větší pole, ale to by nepomohlo, protože velikost pole musí být x! + 1, kde x je počet prvků, které do pole naházím.

Nevíte o nějaké kolekci, která by to, co chci, umožňovala? Našel jsem kolekce unrolled linked list a skip list, používali jste je někdy? Myslíte, že se na to skip list hodí?

Tl;dr:
Potřebuji kolekci s rychlým přístupem na index a s rychlým vkládáním. Co třeba skip list? Nebo něco jiného?

Díky, Petr

Odpovědět

2.11.2017 23:39

Martin Dráb

Tvůrce

Martin Dráb:3.11.2017 10:11

Přidávat prvky mezi určité pozice (jako linkedlist)

Když vložíš prvek mezi nějaké dva indexy, tyto indexy se posunou (resp. jeden z nich)?

Pokud bys těmi indexy vyjadřoval něco jako pořadí prvků, posloužil by ti strom (v C# by to mohl být nějaký druh slovníku, jestli tam je třeba SoftedDictionary).

Nahoru Odpovědět

3.11.2017 10:11

2 + 2 = 5 for extremely large values of 2

Petr Šťastný

Tvůrce

Petr Šťastný:3.11.2017 13:13

Díky, díval jsem se na to, ale nevím, jak to mám použít. Mě jde o tohle:

-6 1 2 8 10 //prvky
// pridam cislo 5
-6 1 2 5 8 10 //prvky

Potřebuji, aby čísla měla nějaké indexy, které sice nemusí jít nutně za sebou (tedy mohou existovat indexy bez hodnot), ale aby vše šlo za sebou.

index	0	1-11	12	13-119	120
hodnota	-6	(nic)	4	(nic)	5

Indexy mohou jít normálně po sobě, ale kdyby nešly, nemusím je přehazovat až budu mezi ně něco vkládat. Na druhou stranu bych musel nechávat mezi indexy velké mezery. Jestli jsem to spočítal správně, maximální velikost objektu (klíče, indexu) by měla stačit až do čísla 2^22000000 . To znamená, že kdybych měl mezi indexy mezery, mohl bych počítat s maximálně asi 1.17429x10⁶ prvky, což není mnoho.

Jestli indexy mezery mít nebudou (čehož bych chtěl dosáhnout), index by se musel při každé změně posouvat, což by pravděpodobně mělo velký dopad na rychlost.

Ideálně tedy

index	0	1	2
hodnota	-6	4	5

Pridam cislo

index	0	1	2	3
hodnota	-6	0	4	5

Tedy ano, potřebuji:

Rychle vkládání na index
Rychlý přístup na index

Akce nemusí být okamžité, ale nechci něco jako list, kdy se po přidání prvků tvoří nový a trvá to strašně dlouho.

Editováno 3.11.2017 13:16

Nahoru Odpovědět

3.11.2017 13:13

Petr Šťastný

Tvůrce

Petr Šťastný:3.11.2017 13:28

Teď mě napadlo, ale nevím, jestli by to fungovalo:

Vytvořil bych si vlastní kolekci s indexem, v podstatě List.

Jakmile bych někam insertnul prvek (třeba mám prvky 0-5, chci nový insertnout do pozice 3), tak by se reálně přidal na konec kolekce (rychlé) a někam bych si uložil informaci, že všechny indexy od pozice 3 jsou posunuté o 1 a zároveň kdybych se dotazoval na index 3, měl bych uloženou, že reálně to je na pozici 6. Fungovalo by to dost rychle?

Pracovalo by to takhle:

MujList<int> list = new MujList<int>();
// naplnim list -> hodnoty 1 3 5

// Pred index 1 pridam hodnotu 2
list.InsertBefore(1, 2);
// hodnoty, jak to vypada -> 1 2 3 5
// hodnoty, jak jsou ulozene -> 1 3 5 2
// pravidla: - Kdyz se dotazujes na index [1], skoc na index [3]
//           - Kdyz se dotazujes na index 2+ az do indexu 3, realny index je posunuty o -1

Ale asi by mi to moc nepomohlo? Složitost přístupu na index by byla v nejhorším případě O(2n), kde [n] je počet insertů.

Nahoru Odpovědět

3.11.2017 13:28

Neaktivní uživatel

Člen

Neaktivní uživatel:3.11.2017 17:24

Jak to tady popisuješ, tak mi to trochu připomíná binární strom (binary tree). Zkus si o tom něco zjistit. Nejspíš bude ještě nutné si to upravit podle potřeby.

Nahoru Odpovědět

3.11.2017 17:24

Neaktivní uživatelský účet

Martin Dráb

Tvůrce

Martin Dráb:3.11.2017 18:41

Lehce modifikovaný n-ární strom ti dovolí provádět dost rychle následující dvě operace (je jich víc, ale další podle mě nejsou pro tebe důležité):

nalezení n-tého nejmenšího/největšího prvku v kolekci (tohle může suplovat ten tvůj přístup přes index, n je index prvku),
přidávání (klidně doprostřed) kolekce.

Aby to ale fungovalo, musí být data ve stromě porovnatelná (musíš být schopen rozhodnout, která položka je větší než která). Měla by asi dodržovat lineární uspořádání, ale možná by stačilo něco slabšího. například čísla takovou věc splňují. Řetězce, řadíš-li je podle abecedy třeba, také.

Termín dost rychle zde znamená O (log N), kde N je počet prvků v kolekci a log je logaritmus, jehož základ se rovná aritě stromu. Není to sice konstantní časová složitost, ale i logaritmus je hodně fajn.

Lehká modifikace toho stromu spočívá v tom, že si u každého uzlu musíš pamatovat počet prvků v jeho podstromu (např.).

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

3.11.2017 18:41

2 + 2 = 5 for extremely large values of 2

Petr Šťastný

Tvůrce

Petr Šťastný:3.11.2017 19:47

Dobře, díky podívám se na to :-) Podívám se jak s tím pracovat a dneska večer nebo zítra ti označím odpověď.

Nahoru Odpovědět

3.11.2017 19:47

Petr Šťastný

Tvůrce

Petr Šťastný:4.11.2017 19:51

Díky, přesně to jsem hledal

Jenom mi řekni, je dobrý nápad to udělat tak, že root node bych vybral jako prvek z pole, který jen nejbližší průměru všech prvků pole? Třeba dostanu pole intů a jako horní node vyberu to číslo, které je nejbližší průměru toho pole.

Nahoru Odpovědět

4.11.2017 19:51

Martin Dráb

Tvůrce

Martin Dráb:4.11.2017 22:11

Pokud tím chceš zajistit, aby ten strom byl vyvážený (tzn. že cca polovina prvků bude v levém a polovina v pravém podstromě), tak si tím moc nepomůžeš.

Pokud máš ale pole intů a chceš z nich vytvořit vyvážený binární vyhleávací strom, tak jsi na správné cestě. Do kořene dáš prostřední prvek, jeho levý syn bude prvek, který je v jedné čtvrtině pole (v polovině levé části), jeho pravý syn je prvek ve třech čtvrtinách pole (v polovině pravého intervalu). A takhle můžeš pokračovat rekurzivně dál (půlí se intervaly v poli a jejich prostředky se vkládají do stromu). Tohle ale nemůžeš udělat, pokud dopředu ta data neznáš.

Pokud ta data, která do toho stromu budeš vkládat, jsou náhodná, tak bych se nevyvážení zas tolik nebál. Náhodnost dat ti zajistí +- logaritmickou hloubku. Jiná by situace byla, kdybys do toho stromu vkládal třeba rostoucí posloupnost čísel, to by nemuselo dopadnout vůbec dobře.

Samozřejmě tu pak máš možnost použít njaké samovyvažovací varianty stromů, ať už ty, které vyvažují okamžitě, když vznikne nerovnováha, která porušuje určité podmínky (AVL, červenočerné), nebo relaxované (tzn. neděláš vyvažování hned, ale až po nějaké době v domnění, že to bude méně pracné, než napravovat každé porušení vyvážení separátně).

Samozřejmě u těch modifikovaných stromů musíš pamatovat na to, že vyvažování mění jejich strukturu, takže budeš muset podle toho měnit i ta čísla udávající počet prvků v podstromech (abys mohl rychle najít n-tý nejmenší/největší prvek, jak potřebuješ).

Nahoru Odpovědět

4.11.2017 22:11

2 + 2 = 5 for extremely large values of 2

Naučíme tě pracovat na home-office.

Zjistit více...

Naučíme tě pracovat na home-office.

Více info »

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 9 zpráv z 9.