On Wednesday, August 16, 2017 at 12:24:19 PM UTC+2, bartekltg wrote:
> On Wednesday, August 16, 2017 at 12:08:07 PM UTC+2, M.M. wrote:
> > On Wednesday, August 16, 2017 at 11:40:04 AM UTC+2, bartekltg wrote:
> > > On Wednesday, August 16, 2017 at 11:21:12 AM UTC+2, M.M. wrote:
> > > > On Wednesday, August 16, 2017 at 2:52:19 AM UTC+2, bartekltg wrote:
> > > >
> > > > > Facet tu mówi o tym:
> > > > > https://www.youtube.com/watch?v=JfmTagWcqoE
> > > > > Ok 16 minuty zaczyna się właściwa cześć, wcześniej konstruuje
> > > > > drzewo na mądrych wskaźnikach.
> > > > > [...]
> > > >
> > > > Ja mam pytanie, w jakich zastosowaniach naprawdę jest potrzebne
> > > > drzewo na wskaźnikach (jakichkolwiek)? Ja mam drzewka zazwyczaj
> > > > na QVectorze, ale mogę też, jako odpowiednik allocatora, szablon
> > > > drzewka sparametryzować std::vector, std::array, itd.
> > >
> > > A co za różnica. Tu masz wskaźniki, u siebie masz indeksy.
> > > Na wskaźnikach jest ciut bardziej elastyczne jeśli chodzi
> > > o zwalnianie pamięci, ale masz pierdolnik z alokacją.
> > > Jeśli zrobisz pulę obiektów, to już w ogole różnicy nie będzie.
> > Poza tym
> > same zalety. Wszystkie operacje działają szybciej.
>
> Wszytkie operacje poza dodawaniem i usówaniem działąją
> tak samo szybko. Jak się postarać, to i dodawanie/usuwanie
> nie odbiega tak bardzo.

U mnie nie działają tak samo szybko. Zrobiłem testy na
wykrywanie błędów, póki co błędów nie znalazło, ale wiecie
jak to jest z oprogramowaniem... zawsze mogę robić coś źle.
Nie obiecuję że znajdę czas, ale postaram się wrzucić
gdzieś źródło z benchmarkami.

W skrócie: gdy porównuję moją, zrobioną zresztą na kolanie,
implementację drzewka czerwono-czarnego, to wszystkie
operacje na mojej implementacji działają wyraźnie
szybciej, względem QMap i std::set. Operacja clear działa
oczywiście milion razy szybciej.

> > Dużo
> > mniej pamięci potrzeba.
>
> Dlaczego "dużo"?
> @pula obiektów.
Opisywałem to chyba. Jeszcze raz. Są trzy powody:
1) Wskaźniki mają większy rozmiar niż typ uint32, uint16 i uint8, a
często takie typy wystarczą.
2) Malloc ma narzut (chyba) 16 bajtw na każdy węzeł.
3) Allokowany jest ciągły obszar pamięci, bez dziur, co jednak także
jest wadą, bo czasami w systemie nie ma dostępnego ciągłego długiego
obszaru.

> > Można zrobić prealokację.
> Tak, w obu wersjach można zrobić prealokacje.
Ok, ale w wersji wskaźnikowej to pociąga za sobą kolejną wadę:
musi być jeszcze wektor na wskaźniki, a taki wektor zajmuje pamięć.

> > Zwalnianie
> > pamięci całego(!) drzewa zajmuje mikrosekundy.
>
> Mało istotne.
> To samo możesz zrobić korzystając z puli.
Nie wiem czy zrozumiałem.. Jeśli się nie zwalnia, to pula żyje
przez całe życie programu, wtedy dla innych programów jest
mało pamięci, no i pula zrealizowana na wektorze też zajmuje
pamięć i zwalnianie na wektorze też pochłania czas. Nie wiem
czy to na pewno nie jest istotne. Jeśli mamy dużo małych
drzewek, to clear może być robione często, a program pobiera z
systemu tylko tyle pamięci, ile w danej chwili potrzebuje.


> > Gdy mamy
> > dużo wyszukiwań w stosunku do modyfikacji (w przypadku drzew
> > poszukiwań), to można wektor posortować i szukać binarnie w
> > wektorze - a to jest już o wiele szybciej.
>
> WTF.
> Jak potem chcesz odzyskać drewo?
Hmmm... o ile czegoś nie mylę, to drzewo cały czas jest poprawnym
drzewem czerwono-czarnym i nie trzeba czasu n*log(n) aby je
odbudowywać. Muszę się zastanowić nad tym porządnie.



> > W przypadku
> > gdy mamy wiele małych drzewek, to indeksy left, right, parent,
> > mogą być typami uint8 lub uint16, to jeszcze bardziej oszczędza
> > pamięć.
>
> Już omawialiśmy.
Omawialiśmy, ale nie wiem czy zmieniłeś zdanie, że to jednak oszczędza
pamięć.



> > Jakie są jeszcze zalety... można w czasie O(1) wyszukać
> > losowy element.
>
> Nieprawda. Jeśli usuwałes z drzewa, masz wektor wypełniony
> zyjącymi wierzchołkami i syfem.
Jakim syfem?


> Ok, możesz losować do skutku,
> dla niezbyt małego stopnia wypełnienia to nadal jest O(1),
> ale musizz dodać tam informację, czy wierzchołek żyje.
Chyba masz na myśli to, że w środku wektora robią sie dziury
po operacji remove/erase. W mojej implementacji nie robią
się dziury, bo od razu dziurę zastępuję ostatnim elementem i
oczywiście uaktualniam indeksy: left, right, parent. Od razu
odparuję zarzut: nie, takie usuwanie nie działa wolniej, póki co w
benchamarkach widzę, że działa szybciej, ale tak jak mówiłem,
porządne bęczmarki (może) dopiero wrzucę.





> > Może dla Was te zalety nie mają znaczenia, ale
> > dla mnie są bardzo ważne, niektóre programy dzięki temu mogę
> > uruchomić na komputerze z mniejszą pamięcią, inne działają np.
> > o 10-30% szybciej.
>
> To, że coś jest lepsze w jakimms szczegolnym przypadku
> nijak nie oznacza, że jest lepsze. A piszłes ogólnie.

Ogólnie dla mnie oznacza tyle samo co esperancja: prawdopodobieństwo
użycia razy czas wykonania. Jeśli operacje takie jak: wstawianie,
usuwanie, przeiterowanie od początku/tyłu, wyszukiwanie, upperBound,
lowerBound, clear, działają szybciej, w dodatku drzewko do 2mlnd
elementów zajmuje mniej pamięci, to esperancja będzie o wiele mniejsza.


> > Poza tym można ustawić wyrównanie. Poza tym malloc ma narzut,
> > którego na wek
>
> To nie używaj alokacji za każdym razem ;-)
To trzeba trzymać listę allokowanych elementów wraz z informacją
który został przydzielony i ta lista zabiera pamięć. I malloc
też będzie miało narzut, ale rację trzeba przyznać, że relatywnie
mniejszy.


> malloc? w c++? ;-)
New używa malloc.


> > > > W efekcie jest więcej trafień w
> > > > cache i drzewko jest w niektórych przypadkach 1.5 raza
> > > > szybsze.
> > >
> > > Tak, jak masz małe drzewo, to jest wiecej trafień.
> > Praktyka pokazuje, że gdy mam 1-10mln elementów w drzewie, to działa
> > dużo szybciej niż QMap i std::set.
>
> Mam jakieś wątpliwości do Twoich pomiarów, jeśli na dzień dobry
> porównujesz zupełnie różne kontenery;-)

Wątpliwości też jeszcze mam, bo to napisałem na kolanie, raz
zmierzyłem czas, tyle, że jak wrzuciłem do całego programu, to
działa przyzwoicie. Ale na pewno porównuję tę samą funkcjonalność.
A że inne kontenery, to pewnie, bo po co porównywać takie same?




>
> >
> > > > > Dośc pobieżnie, i jestem niemal pewien, ze kod, który pokazuje
> > > > > jest n^2 a nie nlogn ;-) Jeśli mamy wskaźnik na parent to łatwo
> > > > > naprawić.
> > > > >
> > > > > Pomysł, by zwalniać w pętli jeśli jest jeden potomek,
> > > > > rekurencyjnie, gdy więcej, nie sprawdzi się:
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > >
> > > > > To drzewo też ma głębokość O(n), a zwalniasz je rekurencyjnie.
> > > > > (do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
> > > > > szczegolny przypadek).
> > > >
> > > > Ale ostatni potomek też iteracyjnie.
> > >
> > > Nie rozumiem.
> > Gdy jest N dzieci w węźle, to po zwolnieniu N-1 dzieci, mamy tę samą
> > sytuację, jakby węzeł od początku miał jedno dziecko, więc możemy
> > potraktować to jako rekurencję ogonową.
>
> Pomyśl nad tym głębiej.
> Nie wiesz, która gałąź jest tą długą.
Ale jest jakieś niezerowe prawdopodobieństwo że tę dłuższą zwalnia się
na koniec, poza tym o tym pisałem przy założeniu, że wiadomo która
jest dłuższa.

Pozdrawiam

do góry

On Wednesday, August 16, 2017 at 4:05:38 PM UTC+2, Borneq wrote:
> W dniu 16.08.2017 o 02:52, bartekltg pisze:
> > vector <unique_ptr<Node>> vec;
>
> A ten wektor nie jest w całości na stosie?

3 czy 4 * sizeof(size_t) siedzi na stosie, reszta na stercie.
Wiesz w ogóle, jak działa vector?

> czy lepiej vector <unique_ptr<Node>> *vec ?

A w czym to by miało pomóc?

> czy też vector tylko podstawowe elementy ma na stosie a tablicę na stogu?

Oczywiście.

> Jednak u mnie zdarzało się przepełnianie pamięci dużymi wektorami.

Mi też. Jak alokowałem 20GB majac 16 fizycznie i 13 dostępnych:)

pzdr
bartekltg

do góry

W dniu 16.08.2017 o 16:11, bartekltg pisze:
>> czy też vector tylko podstawowe elementy ma na stosie a tablicę na stogu?
>
> Oczywiście.

To wydaje mi się naturalne, zresztą raczej nie stosuje się (chyba że
przez alloca() dynamicznego przydzielania na stosie)

>
>> Jednak u mnie zdarzało się przepełnianie pamięci dużymi wektorami.
>
> Mi też. Jak alokowałem 20GB majac 16 fizycznie i 13 dostępnych:)

Zapomniałem dodać że to przepełnienie dotyczyło stosu już przy 1 MB ale
chyba problemy były czymś innym spowodowane, bo aby się upewnić testuję:
void testBigVector()
{
vector<int> vec;
for (int i = 0; i < 10000000; i++)
vec.push_back(i);
}
i przechodzi

do góry

On Wednesday, August 16, 2017 at 4:22:54 PM UTC+2, Borneq wrote:
> W dniu 16.08.2017 o 16:11, bartekltg pisze:
> >> czy też vector tylko podstawowe elementy ma na stosie a tablicę na stogu?
> >
> > Oczywiście.
>
> To wydaje mi się naturalne, zresztą raczej nie stosuje się (chyba że
> przez alloca() dynamicznego przydzielania na stosie)
>
> >
> >> Jednak u mnie zdarzało się przepełnianie pamięci dużymi wektorami.
> >
> > Mi też. Jak alokowałem 20GB majac 16 fizycznie i 13 dostępnych:)
>
> Zapomniałem dodać że to przepełnienie dotyczyło stosu już przy 1 MB ale
> chyba problemy były czymś innym spowodowane, bo aby się upewnić testuję:
> void testBigVector()
> {
> vector<int> vec;
> for (int i = 0; i < 10000000; i++)
> vec.push_back(i);
> }
> i przechodzi

Struktury w tym sensie można podzielić na dwa, albo nawet na trzy rodzaje.

Po pierwsze taka struktura jak std::vector, lub QVector. Jak Bartek już
napisał, na stosie kładą małą ilość danych. Wśród danych położonych na
stosie jest wskaźnik na "dane właściwe", czyli te przechowywane w
wektorze. Potem na tym wskaźniku są robione operacje malloc, realloc i free.

Po drugie, są struktury które w całości leżą na stosie, a szablon/klasa
tylko je obudowuje. Nie jestem pewny, czy taką strukturą jest std::array.

Po trzecie, są stuktury które, ja wyżej, w całości leżą na stosie, ale
gdy rozmiar tablicy zostanie przepełniony, to automatycznie zmieniają
swoje zachowanie na takie samo jak std::vector lub qvector. Przykładem
takiej struktury jest QVarLenthArray.

Więc o te pierwsze nie musisz się bać, że przepłnią stos. A o drugą i
trzecią nie (niekoniecznie) musisz się bać, że malloc, realloc i free
zajmą za dużo czasu.

Pozdrawiam

do góry

On Wednesday, August 16, 2017 at 4:07:30 PM UTC+2, M.M. wrote:
> On Wednesday, August 16, 2017 at 12:24:19 PM UTC+2, bartekltg wrote:
> > On Wednesday, August 16, 2017 at 12:08:07 PM UTC+2, M.M. wrote:
> > > On Wednesday, August 16, 2017 at 11:40:04 AM UTC+2, bartekltg wrote:
> > > > On Wednesday, August 16, 2017 at 11:21:12 AM UTC+2, M.M. wrote:
> > > > > On Wednesday, August 16, 2017 at 2:52:19 AM UTC+2, bartekltg wrote:
> > > > >
> > > > > > Facet tu mówi o tym:
> > > > > > https://www.youtube.com/watch?v=JfmTagWcqoE
> > > > > > Ok 16 minuty zaczyna się właściwa cześć, wcześniej konstruuje
> > > > > > drzewo na mądrych wskaźnikach.
> > > > > > [...]
> > > > >
> > > > > Ja mam pytanie, w jakich zastosowaniach naprawdę jest potrzebne
> > > > > drzewo na wskaźnikach (jakichkolwiek)? Ja mam drzewka zazwyczaj
> > > > > na QVectorze, ale mogę też, jako odpowiednik allocatora, szablon
> > > > > drzewka sparametryzować std::vector, std::array, itd.
> > > >
> > > > A co za różnica. Tu masz wskaźniki, u siebie masz indeksy.
> > > > Na wskaźnikach jest ciut bardziej elastyczne jeśli chodzi
> > > > o zwalnianie pamięci, ale masz pierdolnik z alokacją.
> > > > Jeśli zrobisz pulę obiektów, to już w ogole różnicy nie będzie.
> > > Poza tym
> > > same zalety. Wszystkie operacje działają szybciej.
> >
> > Wszytkie operacje poza dodawaniem i usówaniem działąją

ała, usuwaniem. Biję się w klawiaturę.

> > tak samo szybko. Jak się postarać, to i dodawanie/usuwanie
> > nie odbiega tak bardzo.
>
> U mnie nie działają tak samo szybko. Zrobiłem testy na
> wykrywanie błędów, póki co błędów nie znalazło, ale wiecie
> jak to jest z oprogramowaniem... zawsze mogę robić coś źle.
> Nie obiecuję że znajdę czas, ale postaram się wrzucić
> gdzieś źródło z benchmarkami.

Zauważyłeś warunek "poza dodawaniem/usuwaniem". Tu co najwyżej
rolę odegra lokalnośc, ale dla dużych drzew i tak masz same cache-miss.

>
> W skrócie: gdy porównuję moją, zrobioną zresztą na kolanie,
> implementację drzewka czerwono-czarnego, to wszystkie
> operacje na mojej implementacji działają wyraźnie
> szybciej, względem QMap i std::set. Operacja clear działa
> oczywiście milion razy szybciej.



>
> > > Dużo
> > > mniej pamięci potrzeba.
> >
> > Dlaczego "dużo"?
> > @pula obiektów.
> Opisywałem to chyba. Jeszcze raz. Są trzy powody:
> 1) Wskaźniki mają większy rozmiar niż typ uint32, uint16 i uint8, a
> często takie typy wystarczą.

A ja bym chcieł porównać to samo. Dla 256 max elementów sprawdziłbym
raczej boost flat_set.

> 2) Malloc ma narzut (chyba) 16 bajtw na każdy węzeł.

Dlatego pisałem o puli ;-)

> 3) Allokowany jest ciągły obszar pamięci, bez dziur, co jednak także
> jest wadą, bo czasami w systemie nie ma dostępnego ciągłego długiego
> obszaru.

I tu jest zaleta puli. Mogę alokowac po paczkach zadanych rozmiarów
(np najpierw rośnie *2, a potem ciągle 500MB). Moja pula jest ciut większym
obiektem, ale nigdy nie zaalokuje nic bardoz dużego.

Pamiętajmy też, że liczy się fragmentacja przestrzeni adresowej logicznej,
nie fizycznej. Nie wiem, co bym musiał robić, by sobie zdefragmentować
64bitowa przestrzeń adresową by nie móc wstawić tam paru GB:)

(pula nadal będzie alokowała kolejne fragmenty, a nie realokowała, bo
nie chemy przesówać tamtych obiektów)


> > > Można zrobić prealokację.
> > Tak, w obu wersjach można zrobić prealokacje.
> Ok, ale w wersji wskaźnikowej to pociąga za sobą kolejną wadę:
> musi być jeszcze wektor na wskaźniki, a taki wektor zajmuje pamięć.

Te obiekty już mają wskażniki. Trzymaj je jako listę ;-)

Raczej znów myślałem o puli.



> > > Zwalnianie
> > > pamięci całego(!) drzewa zajmuje mikrosekundy.
> >
> > Mało istotne.
> > To samo możesz zrobić korzystając z puli.
> Nie wiem czy zrozumiałem.. Jeśli się nie zwalnia, to pula żyje
> przez całe życie programu, wtedy dla innych programów jest
> mało pamięci, no i pula zrealizowana na wektorze też zajmuje
> pamięć i zwalnianie na wektorze też pochłania czas. Nie wiem
> czy to na pewno nie jest istotne. Jeśli mamy dużo małych
> drzewek, to clear może być robione często, a program pobiera z
> systemu tylko tyle pamięci, ile w danej chwili potrzebuje.

Z puli nie będziesz zwalniał w momencie usuwania z drzewka,
przynajmniej nie w oczywisty sposób (chyba, że zgodzisz się
na to, że erase unieważnia iteratory - przestawia fizycznie
elementy).
Ale:
-jeśli drzewko jest ciągle używane, to usuniete elementy
są uzywane ponownie, więc struktura zajmuje tyle pamięci, ile
zajęła w szczytowym momencie (+trochę, w końcu vector potrafi
zająć 2*wiecej niż ma elementów).
-Jeśli robisz clear drzewku często, to jest to sytuacja idealna.
Clear na puli, root = nullptr i jest posprzątane.
W wersji jedna pula na jedno drzewko. Alternatywnym podejsciem jesty
pula na wszytkie małe drzewka, ale wtedy znów, co prawda pamięć pomiędzy
drzewkami przekłada się ładnie, ale znów trzeba się namęczyć ze zmniejszaniem
pamięci (w tym unieważnione zostaną wskażniki)

>
> > > Gdy mamy
> > > dużo wyszukiwań w stosunku do modyfikacji (w przypadku drzew
> > > poszukiwań), to można wektor posortować i szukać binarnie w
> > > wektorze - a to jest już o wiele szybciej.
> >
> > WTF.
> > Jak potem chcesz odzyskać drewo?
> Hmmm... o ile czegoś nie mylę, to drzewo cały czas jest poprawnym
> drzewem czerwono-czarnym i nie trzeba czasu n*log(n) aby je
> odbudowywać. Muszę się zastanowić nad tym porządnie.

Masz drzewko rb, skłąda się ono z nodów, w których jest:
dane, bit o kolorze, wskaźniki do dzieci. I wszytkie nody możesz
trzymać w vector.
Jak sobie posortujesz po 'dane' to te wskaźniki pokakzują
w losowe miejsca.

No, chyba, że z tym drzewem rb to mydliłęś oczy i tak naprawdę masz
coś w rodzajju kopca/drzewa binarnego pełnego, gdzie dzieci 'i' są
na wspolrzednych 2i i 2i+1 ;-)


>
>
> > > W przypadku
> > > gdy mamy wiele małych drzewek, to indeksy left, right, parent,
> > > mogą być typami uint8 lub uint16, to jeszcze bardziej oszczędza
> > > pamięć.
> >
> > Już omawialiśmy.
> Omawialiśmy, ale nie wiem czy zmieniłeś zdanie, że to jednak oszczędza
> pamięć.

Nie zmieniłem zdania, że jest to niszowa optymalizacja dla bardzo
konkretnego zastosowania;-)

>
>
>



>
> > Ok, możesz losować do skutku,
> > dla niezbyt małego stopnia wypełnienia to nadal jest O(1),
> > ale musizz dodać tam informację, czy wierzchołek żyje.
> Chyba masz na myśli to, że w środku wektora robią sie dziury
> po operacji remove/erase. W mojej implementacji nie robią
> się dziury, bo od razu dziurę zastępuję ostatnim elementem i
> oczywiście uaktualniam indeksy: left, right, parent. Od razu
> odparuję zarzut: nie, takie usuwanie nie działa wolniej, póki co w
> benchamarkach widzę, że działa szybciej, ale tak jak mówiłem,
> porządne bęczmarki (może) dopiero wrzucę.

Ok. No to zrobiłeś dokładnie to, co ja nazywałem pulą;-)
tylko prościej zaimplementowaną, bo nie przejmujesz się tym,
by kontener miał iteratory.
Od strony wydajnościowej (dla indeksów rozmiaru wskaźników)
wydajność jest ta sama.



> > > Może dla Was te zalety nie mają znaczenia, ale
> > > dla mnie są bardzo ważne, niektóre programy dzięki temu mogę
> > > uruchomić na komputerze z mniejszą pamięcią, inne działają np.
> > > o 10-30% szybciej.
> >
> > To, że coś jest lepsze w jakimms szczegolnym przypadku
> > nijak nie oznacza, że jest lepsze. A piszłes ogólnie.
>
> Ogólnie dla mnie oznacza tyle samo co esperancja: prawdopodobieństwo
> użycia razy czas wykonania. Jeśli operacje takie jak: wstawianie,
> usuwanie, przeiterowanie od początku/tyłu, wyszukiwanie, upperBound,
> lowerBound, clear, działają szybciej, w dodatku drzewko do 2mlnd
> elementów zajmuje mniej pamięci, to esperancja będzie o wiele mniejsza.
>
>
> > > Poza tym można ustawić wyrównanie. Poza tym malloc ma narzut,
> > > którego na wek
> >
> > To nie używaj alokacji za każdym razem ;-)
> To trzeba trzymać listę allokowanych elementów wraz z informacją
> który został przydzielony i ta lista zabiera pamięć. I malloc
> też będzie miało narzut, ale rację trzeba przyznać, że relatywnie
> mniejszy.


Tablica bitów zajmuje 1/8 bajta na obiekt. Malloc trzyma size_t,
a być moze i wiecej, a do tego wyrównuje do 16.
To zawsze jest lepiej:)

>
>
> > malloc? w c++? ;-)
> New używa malloc.

To może tez pisz winapi::HeapAlloc ;-)

>
>
> >
> > >
> > > > > > Dośc pobieżnie, i jestem niemal pewien, ze kod, który pokazuje
> > > > > > jest n^2 a nie nlogn ;-) Jeśli mamy wskaźnik na parent to łatwo
> > > > > > naprawić.
> > > > > >
> > > > > > Pomysł, by zwalniać w pętli jeśli jest jeden potomek,
> > > > > > rekurencyjnie, gdy więcej, nie sprawdzi się:
> > > > > > /\
> > > > > > /\
> > > > > > /\
> > > > > > /\
> > > > > > /\
> > > > > > /\
> > > > > > /\
> > > > > > /\
> > > > > >
> > > > > > To drzewo też ma głębokość O(n), a zwalniasz je rekurencyjnie.
> > > > > > (do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
> > > > > > szczegolny przypadek).
> > > > >
> > > > > Ale ostatni potomek też iteracyjnie.
> > > >
> > > > Nie rozumiem.
> > > Gdy jest N dzieci w węźle, to po zwolnieniu N-1 dzieci, mamy tę samą
> > > sytuację, jakby węzeł od początku miał jedno dziecko, więc możemy
> > > potraktować to jako rekurencję ogonową.
> >
> > Pomyśl nad tym głębiej.
> > Nie wiesz, która gałąź jest tą długą.
> Ale jest jakieś niezerowe prawdopodobieństwo że tę dłuższą zwalnia się
> na koniec, poza tym o tym pisałem przy założeniu, że wiadomo która
> jest dłuższa.

A ja wprost napisałęm, że tego nie wiemy;>
"(do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
szczegolny przypadek). "

pzdr
bartekltg

do góry

On Thursday, August 17, 2017 at 12:31:08 AM UTC+2, bartekltg wrote:
> ała, usuwaniem. Biję się w klawiaturę.
> "poza dodawaniem/usuwaniem"
Wypowiedzi się pomieszały, kompletnie nie o to chodzilo, albo
wręcz to nie moje słowa.

Przeczytałem wszystko co napisałeś, ale widzę, że nie ma sensu
dłużej teoretycznie argumentować. Za jakiś dłuższy lub krótszy
czas wrzucę pomiary czasu.

Pozdrawiam

do góry

W dniu 17.08.2017 o 00:31, bartekltg pisze:
>> 2) Malloc ma narzut (chyba) 16 bajtw na każdy węzeł.
>
> Dlatego pisałem o puli ;-)

A co to takiego ta pula?

do góry

W dniu 2017-08-16 o 16:07, M.M. pisze:

>> malloc? w c++? ;-)
> New używa malloc.

chyba new może użyć malloca, ale niekoniecznie go używa, jest to raczej
zależne od implementacji.

--
http://kaczus.ppa.pl

do góry

On Thursday, August 17, 2017 at 8:12:15 AM UTC+2, Tomasz Kaczanowski wrote:
> W dniu 2017-08-16 o 16:07, M.M. pisze:
>
> >> malloc? w c++? ;-)
> > New używa malloc.
>
> chyba new może użyć malloca, ale niekoniecznie go używa, jest to raczej
> zależne od implementacji.
>
> --
> http://kaczus.ppa.pl

W sumie tak, tak samo jak malloc może mieć różne implementacje, i dalej
system może różnie realizować przydział pamięci.

Pozdrawiam

do góry