Spojový seznam – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Luckin
~ Anonymní uživatel
57 příspěvků
1. 11. 2012   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 89.103.156.–
Reklama
Reklama
vitamin+8
Grafoman
1. 11. 2012   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
1. 11. 2012   #3
-
0
-

#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

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
1. 11. 2012   #4
-
0
-

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

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
1. 11. 2012   #5
-
0
-

#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.

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
1. 11. 2012   #6
-
0
-

Nie ak umoznis mazanie zo stredu listu.

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
1. 11. 2012   #7
-
0
-

#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.

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
1. 11. 2012   #8
-
0
-

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

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Luckin
~ Anonymní uživatel
57 příspěvků
1. 11. 2012   #9
-
0
-

#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.

Nahlásit jako SPAM
IP: 89.103.156.–
vitamin+8
Grafoman
1. 11. 2012   #10
-
0
-

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 :)

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 57 hostů

Podobná vlákna

Spojový seznam — založil Jakub

Spojový seznam — založil lubabe

Spojový seznam — založil TarderOrtex

Spojový seznam - problém — založil Screpheep

Linearní spojový seznam — založil Rivers

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý