Spojový seznam – C / C++ – Fórum – Programujte.com

Zdravím. Snažím se vytvořit šablonu třídy pro spojový seznam. Každý prvek seznamu je objekt obsahujicí data a pointer na následující prvek, vytvoření probíha tak že se vezme první objekt, jemu se příkazem new alokuje paměť a pak smyčkou for se vždy přes předchazející prvek alokuje operátorem new paměť pro další. Blok smyčky obsahuje pouze dva příkazy pro přiřazení a vytvoření objektu operátorem new. Všechno funguje jak má ale je to na můj vkus neuvěřitelně pomalé. Vytvoření seznamu o 10 milionech prvcích trvá cca 3 vteřiny. Došel jsem k závěru že alokace jednotlivého objektu operátorem new trvá daleko déle než jsem si myslel, jelikož bez tohoto příkazu proběhne cyklus v podstatě okamžitě i při mnohem větším počtu průchodů. Rád bych tedy věděl jestli existuje nějaký efektivnější (rychlejší) způsob jak vytvořit spojový seznam. Napadlo mě vytvořit celý blok paměti pomocí new[] a pak každému objektu přiřadit adresu jednotlivých prvků tohoto bloku. Potíž ale je v dealokaci protože pokud vím tak jednotlivé prvky bloku vytvořeného operátorem new[] nejdou dealokovat operátorem delete. Předem děkuji za rady.

Riesenie je napr take ze list bude alokovat elementy listu po blokoch (ako pole char, pripadne pomocou malloc() nech sa nevolaju konstruktory) a alokovani konkretneho elementu listu pouzies pretazeny operator new ktory "odkusne" s predtym alokovanej pamete(a az teras sa zavola konstruktor). Samozrejme musis pretazit aj delete ktore miesto dealokacie pamete tu pamet vrati spet (zrejme ju budes uchovavat v dakej statickej premennej). Kedze takato pamet sa bude fragmentovat, tak jej sprava nie je trivialna, alebo mozu vznikat velke bloky nepouzivanej pamete ak sa na jej spravu vykasles.

#2 vitamin
Pokud to chápu správně tak tak po vytvoření seznamu by se měl alokovat blok o řekněme 1000 prvcích a z něj  by se měly přiřazovat jednotlivé prvky do seznamu. Pokud počet prvků přesáhne 1000 vytvoří se další blok. Ty bloky by mohli mít různou velikost, záleží na tom jaký chci mít poměr mezi rychlostí alokace a spotřeby paměti, tohle by teoreticky mohlo být nastavitelné. Chápu to správně? :D

Ano, ale je tu ten problem s fragmentaciou pamete pri mazani prvkov zo zoznamu. 

#4 vitamin
Teoreticky stačí když změním pointer na poslední prvek, přepíšu počet prvků a kdyz počet prvků klesne pod danou hranici tak dealokuju celý blok.

Nie ak umoznis mazanie zo stredu listu.

#6 vitamin
To by se dalo vyřešit funkcí memcpy která by zkopírovala paměť tak aby se posunula a konce se spojily. Jako největší problém se mi jeví vyřešit aby se kopírovala správná paměť na správné místo.

Radsej sa na to vykasli, nakoniec zistis ze rezia na spravu pamete bude vecsia ako rezia pri alokacii po jednom prvku :)

#8 vitamin
Otázka je jak moc neefektivní by bylo ukládat pointery na jednotlivé bloky do dvojrozměrného pole. (První rozměr bloky, druhý rozměr prvky bloků). Pak by to spojování nebylo tak složité.

Kdybych měl něco lepšího na práci tak bych s tím ani nezačínal. Nemám co dělat a na tomhle se aspoň něco naučím. Nikdy jsem spojový seznam nepsal.

Ak mas napr blok o velkosti 64 * sizeof( list_element ) tak mozes pouzit 'uint64_t mask' ako masku kde bude kazdy bit urcovat ci sa dany element pouziva (napr 1 znacit pouzivany element a 0 volny element). Akonahle bude mat blok hodnotu masky rovnu 0, tak ho mozes zmazat. Problem je ako zistit do ktoreho bloku patri mazany element. Mozes prehladavat vsetky bloky a podla adresy mazaneho elementu mozes zistit do ktoreho bloku patri. Ak nebude blokov moc vela tak to moze byt mozno rychlejsie. Otazne je ci to iste nerobi OS (pripadne ci to neroby efektivnejsie).

Aspon vidis preco je alokacia na heape pomalsia ako alokacia na lokalnom stacku :)