Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #30223 > unrolled thread

Ciekawy problem iteracyjnego zwalniania głębokiego drzewa

Back to article view | Back to pl.comp.programming

Contents

  Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 15:47 +0200
    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 15:53 +0200
    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 07:12 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 16:44 +0200
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 16:48 +0200
          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 07:50 -0700
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 17:11 +0200
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 17:15 +0200
              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 17:20 +0200
              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 08:50 -0700
                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 18:56 +0200
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 11:04 -0700
                    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 23:44 +0200
                      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 15:20 -0700
                      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 18:33 -0700
                        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-15 07:59 +0200
                          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa slawek <fake@fakeemail.com> - 2017-08-15 11:58 +0200
                            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-15 12:55 +0200
                            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-15 12:25 -0700
                              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa slawek <fake@fakeemail.com> - 2017-08-15 21:27 +0200
                                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-15 15:20 -0700
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 07:49 -0700
    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-15 17:52 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 02:21 -0700
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 02:40 -0700
          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 03:08 -0700
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 03:24 -0700
              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 07:07 -0700
                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 15:31 -0700
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 16:12 -0700
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-17 02:46 +0200
                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Tomasz Kaczanowski <kaczus@poczta.onet.pl> - 2017-08-17 08:11 +0200
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-17 03:26 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-16 15:46 +0200
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 07:06 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-16 16:05 +0200
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 07:11 -0700
          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-16 16:22 +0200
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 07:42 -0700

Page 2 of 2 — ← Prev page 1 [2]

#30284

On Tuesday, August 15, 2017 at 9:28:33 PM UTC+2, slawek wrote:
> On Tue, 15 Aug 2017 12:25:59 -0700 (PDT), "M.M." <mmarszik@gmail.com> 
> wrote:
> > Nie wiem co będzie w C#. W Javie, gdy przypisze się root ==
> >  null, to
> > prędzej czy później włączy się GC, wyczy=
> > ści część lub wszystkie
> > nody, potem odda sterowanie.
> 
> FYI 
> 
> W C# jest tak samo.

Czy w C++ mogą dać podobny efekt smart-pointery?
Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30228

On Monday, August 14, 2017 at 4:44:43 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 16:12, M.M. pisze:
> > Ale pod jakim względem ciekawy? Żeby nie przekroczyć stosu przy
> > dużej ilości rekurencyjnych wywołań? Można zapamiętać wskaźniki w
> > tablicy liniowej, czyli w wektorze, a potem zwolnić pamięć na
> > podstawie wskaźników w tablicy.
> 
> A czy samo przejście drzewa aby zapamiętać wskaźniki nie spowoduje 
> przekroczenie wysokości stosu?

Sprawdź w Twoim środowisku. Jak pamięci jest dużo, to można w
kompilatorze ustawić większy rozmiar - co zapewne wiesz.
Może coś bym podpowiedział, ale nie wiem w jakich okolicznościach 
jest budowane takie drzewo, ani do czego jest potrzebne.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30285

On Monday, August 14, 2017 at 3:47:20 PM UTC+2, Borneq wrote:
> Nie patrząc już na shared_ptr i na listy,grafy cykliczne, mamy drzewko.
> Zwalniamy obiektowo tak że zwalniamy korzeń, wołany jest destructor dla 
> korzenia, potem jego dzieci itd.
> Ale co gdy drzewo zdegeneruje się niemal do listy, tak że będziemy 
> musieli rekurencyjnie zwalniać listę głębokości 100 tys i więcej?
> Samą listę można zwalniać iteracyjnie od korzenia lub końca. Ale co gdy 
> zamiast listy mamy zdegenerowane głębokie drzewo, od którego co ileś 
> odchodzą krótkie rozgałęzienia np. długości 20. Ewentualnie jest dwie 
> czy trzy gałęzi długie rzędu 100 tys.
> Oto ciekawy problem.


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.

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

@pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je 
skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.

Przesuń usuwany wierzchołek do kontenera.
Teraz całe drzewo tam siedzi, zaczepione pod ten element;-)
Niech indeks pokazuje na ten (jedyny na razie) element. int i=0; :)

Teraz w pętli:
Wszystkie dzieci wierzchołka spod 'i' przerzuć do kontenera, 
i++
Pętle konczysz, gdy i =size.

Działająca przykąłdowa implementacja (wystarczy c++11, ale make_unique
aż się  prosi gdziniegdzie:) poniżej.

pzdr
bartekltg


#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <iterator>
using namespace std;

struct Node {
    vector<unique_ptr<Node>> children;
    int data;
    Node(int x):data(x){}
    ~Node() { cout << "destruktor "<<data<<endl;}

};
class Tree {
       unique_ptr<Node> root;
public:

    ~Tree(){
        vector <unique_ptr<Node>> vec;
        vec.push_back(move(root));
        unsigned int i=0;

        while (i<vec.size()) {
            move(vec[i]->children.begin(),vec[i]->children.end(), std::back_inserter(vec) );
            cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
            i++;
        }
    }
       void push(int x){
           if (root.get()==nullptr){
               root = unique_ptr<Node>(new Node(x));
           }else{
               Node *n=root.get();
               while( n->children.size()>0 )
                   n = (n->children[0].get());
               n->children.push_back(unique_ptr<Node>(new Node(x)));
           }

       }

/*…*/
};



int main(int argc, char *argv[])
{
    int c;

    {
    Tree tree;
    for (int k=1000;k<1004;k++)
         tree.push(k);
    }

    cout<<"bla"<<endl;

    return 0;
}
 

 
OUT:
przenosiny dzieci 0: 1000
przenosiny dzieci 1: 1001
przenosiny dzieci 2: 1002
przenosiny dzieci 3: 1003
destruktor 1000
destruktor 1001
destruktor 1002
destruktor 1003

[toc] | [prev] | [next] | [standalone]

#30286

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.

Gdy robię benczmark, i gdy sumaryczny czas zwalniania z takich
struktur jak std::set, czy QMap trwa np. 10sekund, to w moim
nadal wynosi 0.000 - tak, stoper nie zdąży się włączyć.

Drzewko na tablicy jest niby ciut wolniejsze, ale oszczędza
pamięć, bo jako indeksy można użyć int8, int16, int32, a
wskaźnik ma rozmiar 64 bity. W efekcie jest więcej trafień w
cache i drzewko jest w niektórych przypadkach 1.5 raza
szybsze. 



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


> @pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je 
> skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.
To chyba najprostsza metoda. Dwa wektory są potrzebne. Jeden ma
węzły, drugi węzły których potomków jeszcze nie dodano do pierwszej -
tak można zamienić drzewko na wektor bez rekurencji. Gdy nie trzeba 
zamieniać na tablicę, ale od razu zwalniać, to wystarczy wektor z
dziećmi których zwolniono rodziców.


> Przesuń usuwany wierzchołek do kontenera.
> Teraz całe drzewo tam siedzi, zaczepione pod ten element;-)
> Niech indeks pokazuje na ten (jedyny na razie) element. int i=0; :)
> 
> Teraz w pętli:
> Wszystkie dzieci wierzchołka spod 'i' przerzuć do kontenera, 
> i++
> Pętle konczysz, gdy i =size.
> 
> Działająca przykąłdowa implementacja (wystarczy c++11, ale make_unique
> aż się  prosi gdziniegdzie:) poniżej.

Tak, chyba o tym samym myślałem.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30287

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. 


> Drzewko na tablicy jest niby ciut wolniejsze, ale oszczędza
> pamięć, bo jako indeksy można użyć int8, int16, int32, a
> wskaźnik ma rozmiar 64 bity. 

Można, jeśli masz małe drzewo. 
Wyrównanie i tak pewnie kopnie w tyłek i będize to samo co int32.

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

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

> 
> 
> > @pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je 
> > skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.
> To chyba najprostsza metoda. Dwa wektory są potrzebne. Jeden ma

Nie. Jeden vector wystarczy. Rozwi,ązanie miałeś niżej. 

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#30288

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. 

Są różnice. Wada jest taka, że potrzebny jest duży i ciągły
obszar pamięci. W przypadku bardzo dużych drzewek może
być to problem. Gdy chcemy mieć powyżej 2^32 węzłów, to na
uint32 też nie zrobimy tego. Jeszcze jedna jest wada, po
usunięciu węzła, indeksy mogą się zdeakutalizować. Poza tym 
same zalety. Wszystkie operacje działają szybciej. Dużo 
mniej pamięci potrzeba. Można zrobić prealokację. Zwalnianie
pamięci całego(!) drzewa zajmuje mikrosekundy. 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. 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ęć. Jakie są jeszcze zalety... można w czasie O(1) wyszukać
losowy element. 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.


> > Drzewko na tablicy jest niby ciut wolniejsze, ale oszczędza
> > pamięć, bo jako indeksy można użyć int8, int16, int32, a
> > wskaźnik ma rozmiar 64 bity. 
> 
> Można, jeśli masz małe drzewo. 
> Wyrównanie i tak pewnie kopnie w tyłek i będize to samo co int32.
Nie, bo są trzy indeksy: left, right i parent, zakumulują się.
Poza tym można ustawić wyrównanie. Poza tym malloc ma narzut,
którego na wek 

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


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


> > > @pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je 
> > > skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.
> > To chyba najprostsza metoda. Dwa wektory są potrzebne. Jeden ma
> 
> Nie. Jeden vector wystarczy. Rozwi,ązanie miałeś niżej. 
Do samego zwolnienia wystarczy jeden, wspomniałem o tym poniżej.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30289

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.

> Dużo 
> mniej pamięci potrzeba. 

Dlaczego "dużo"?
@pula obiektów.

> Można zrobić prealokację. 
Tak, w obu wersjach można zrobić prealokacje. 


> Zwalnianie
> pamięci całego(!) drzewa zajmuje mikrosekundy.

Mało istotne. 
To samo możesz zrobić korzystając z puli.

> 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?


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

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

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


> 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 ;-)
malloc? w c++? ;-)


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

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

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30293

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

[toc] | [prev] | [next] | [standalone]

#30336

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

[toc] | [prev] | [next] | [standalone]

#30338

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 

[toc] | [prev] | [next] | [standalone]

#30339

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?

[toc] | [prev] | [next] | [standalone]

#30340

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

[toc] | [prev] | [next] | [standalone]

#30342

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

[toc] | [prev] | [next] | [standalone]

#30290

W dniu 16.08.2017 o 02:52, bartekltg pisze:
>         unique_ptr<Node> root;
>          while (i<vec.size()) {
>              move(vec[i]->children.begin(),vec[i]->children.end(), std::back_inserter(vec) );
>              cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
>              i++;
>          }

a gdyby nie było unique_ptr? albo było shared_ptr?

[toc] | [prev] | [next] | [standalone]

#30292

On Wednesday, August 16, 2017 at 3:46:41 PM UTC+2, Borneq wrote:
> W dniu 16.08.2017 o 02:52, bartekltg pisze:
> >         unique_ptr<Node> root;
> >          while (i<vec.size()) {
> >              move(vec[i]->children.begin(),vec[i]->children.end(), std::back_inserter(vec) );
> >              cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
> >              i++;
> >          }
> 
> a gdyby nie było unique_ptr? albo było shared_ptr?


"A gdyby nie słoń?"

Jakby zbudować drzewo inaczej, trzeba by zrobić jego kasowanie inaczej;-)
Jak, zależy od tego, jak to drzewo budujesz. Co robić na gołych wskaźnikach
masz w każdym podręczniku:) 
Chocby robisz recznie rekurencyjnie: w procedurze usuwania usuwasz
dzieci, a potem to, na co wskazujesz. jest to odkładnie to, co automatycznie
robi unique_ptr, wiec ma ten sam "problem" ze stosem/
  
unique_ptr są o tyle lepsze, że kasowanie masz za darmo i ciezko
zrobić wyciek, a nie dają nakładu 
Shared_ptr to liczenie referencji, do drzew niepotrzebnie i relatywnie
kosztowne. 

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#30291

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?
czy lepiej vector <unique_ptr<Node>> *vec ?
czy też vector tylko podstawowe elementy ma na stosie a tablicę na stogu?
Jednak u mnie zdarzało się przepełnianie pamięci dużymi wektorami.

[toc] | [prev] | [next] | [standalone]

#30294

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

[toc] | [prev] | [next] | [standalone]

#30295

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

[toc] | [prev] | [next] | [standalone]

#30296

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

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | pl.comp.programming

csiph-web