eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programming › Jak poskładać rozsypane drzewko?
Ilość wypowiedzi w tym wątku: 11

  • 1. Data: 2016-05-17 16:15:05
    Temat: Jak poskładać rozsypane drzewko?
    Od: Borneq <b...@a...hidden.pl>

    (w C++)
    Mam elementy drzewka typy (klucz, klucz parenta), root ma własny klucz i
    klucz parenta==NULL. Są umieszczone w pliku losowo, można do
    optymalizacji założyć że nie całkiem losowo.
    Zabrałem się to tego tak:
    klucz jest haszem - stringiem
    biorę mapę unordered_map<string, CChainNode*> map;
    następnie pierwsza faza:
    pętla po wszystkich elementach przy założeniu że trochę jest po kolei:
    szukanie parenta i te, które nie znaleziono, dodawane do wektora:
    for (int j = 1; j < vecAllElems.size(); j++)
    {
    CChainNode *elem = vecAllElems[j];
    unordered_map<string, CChainNode*>::const_iterator iter =
    map.find(elem->strHashPrevBlock);
    if (iter == map.end())
    {
    vecNotFound.push_back(elem);
    }
    else
    {
    CChainNode *parent = iter->second;
    map[elem->strHashBlock] = elem;
    parent->Add(elem);
    }
    }

    Następnie próbowałem, ale to mi nie wychodzi, bo bardzo długo oblicza:
    while (foundInRund>0)
    {
    int j = 0;
    foundInRund = 0;
    while (j < vecNotFound.size())
    {
    CChainNode *elem = vecNotFound[j];
    unordered_map<string, CChainNode*>::const_iterator iter =
    map.find(elem->strHashPrevBlock);
    if (iter == map.end())
    j++;
    else
    {
    CChainNode *parent = iter->second;
    map[elem->strHashBlock] = elem;
    vecNotFound.erase(vecNotFound.begin() + j);
    foundInRund++;
    parent->Add(elem);
    break; //from beginning
    }
    }
    }
    Skoro jest while (foundInRund>0), to powinien znaleźć wszystkie , choć
    to może długo trwać, ale dla niektórych danych znajduje coś za mało.

    Jak zrobić? może tworzyć wiele (tysięcy nawet) osobnych niepowiązanych
    drzewek, a potem łączyć je w jedno?
    Problemem jest to, że często najpierw w pliku występuje child a potem
    parent.


  • 2. Data: 2016-05-17 17:54:10
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 17.05.2016 o 16:15, Borneq pisze:
    > Jak zrobić? może tworzyć wiele (tysięcy nawet) osobnych niepowiązanych
    > drzewek, a potem łączyć je w jedno?
    > Problemem jest to, że często najpierw w pliku występuje child a potem
    > parent.

    Jest jakiś znany algorytm do tego, co wyszukać w Google?


  • 3. Data: 2016-05-17 19:03:07
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: bartekltg <b...@g...com>

    On 17.05.2016 16:15, Borneq wrote:

    Uwaga językowa.

    > CChainNode *elem = vecAllElems[j];

    > CChainNode *parent = iter->second;

    > CChainNode *parent = iter->second;

    Nie używaj tak wskaźników.
    Nie dość, że można sobie tym palca odstrzelić,
    to jeszcze zmniejsza czytelność i _wydajność_!

    W drugim i trzecim przypadku używasz parent tylko raz.
    W ogole to nie ejst potrzebne.

    > CChainNode *parent = iter->second;
    > map[elem->strHashBlock] = elem;
    > parent->Add(elem);

    ->

    map[elem->strHashBlock] = elem;
    iter->second->Add(elem);

    Referencja... Lepiej, ale też nie jest jakimś szczegolnie dobrym
    rozwiązaniem do wskazywania na obiekt typu vecAllElems[j].

    Ja bym pisał vecAllElems[j]. Kompilator to sobie zoptymalizuje.
    W ogolnym przypadku, jeśli jesteś pewien, że _nigdy_ w tym
    fragmencie kodu nie zmodyfikujesz kontenera, dla większenia
    kompaktowośći tekstu użyj (prosząc w komentarzu o wybaczenie) referencji.


    Ale nie w tym przypadku:

    > for (int j = 1; j < vecAllElems.size(); j++)
    > {
    > CChainNode *elem = vecAllElems[j];

    Aż się prosi o

    for (auto itelem = begin(vecAllElems); itelem!=end(vecAllElems); itelem)
    {
    Czytelniej, mniej zmiennych dla zmylenia porzeciwnika...

    Albo wręcz (tylko nieśredniowieczne kompilatory):

    for(auto&& elem: vecAllElems)
    {
    ...
    }
    tu "elem" jest referencją do kolejnych elementów kontenera.





    Problem polega na tym, zę liniowy problem rozwiązujesz kwadratowo!
    (find dla każdego elementu).
    >
    > Jak zrobić? może tworzyć wiele (tysięcy nawet) osobnych niepowiązanych
    > drzewek, a potem łączyć je w jedno?
    > Problemem jest to, że często najpierw w pliku występuje child a potem
    > parent.


    Jajpierw wczytaj wszystkie (tak, abyś miał powiązanie klucz->obiekt).
    Doraczałbym raczej <klucz, indeks> niż <klucz, wskaźnik>.

    Przelatujesz vecAllElems, patrząc na każdym miejscu j na wartość
    klucza K. Tworzysz sobie unordered_map klucz -> indeks w vecAllElems,
    (od biedy wskaźnik, ale to odstrzli palucha) z elementami j->k

    Przelatujesz drugi raz, tym razem patrząc na parent każdego obiekty.
    Ale masz słownik, więc wiesz, pod króym indeksem jest parent.

    Całość jest linioiowa, dwa przebiegi.


    pzdr
    bartekltg










  • 4. Data: 2016-05-17 19:44:13
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 17.05.2016 o 19:03, bartekltg pisze:
    > map[elem->strHashBlock] = elem;
    > iter->second->Add(elem);
    >> for (int j = 1; j < vecAllElems.size(); j++)
    >> {
    >> CChainNode *elem = vecAllElems[j];
    >
    > Aż się prosi o
    >
    > for (auto itelem = begin(vecAllElems); itelem!=end(vecAllElems); itelem)


    void buildForest()
    {
    unordered_map<string, size_t> map;
    //dwa przebiegi
    for (int i = 0; i < allnodes.size(); i++)
    {
    map[allnodes[i]->strHash] = i;
    }
    for (int i = 0; i < allnodes.size(); i++)
    {
    unordered_map<string, size_t>::const_iterator iter =
    map.find(allnodes[i]->strHashParent);
    iter->second->Add(allnodes[i]);
    }
    }

    Nie zrobiłem for (auto itelem = begin(vecAllElems);
    itelem!=end(vecAllElems); itelem) ponieważ potrzebowałem indeks.

    Ale w linii iter->second->Add(allnodes[i]); jest błąd:

    Error C2227 left of '->Add' must point to class/struct/union/generic type
    Error (active) expression must have pointer type

    Mimo że w programie dało się to skompilować...


  • 5. Data: 2016-05-17 20:06:00
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 17.05.2016 o 19:44, Borneq pisze:
    > Ale w linii iter->second->Add(allnodes[i]); jest błąd:
    Pytanie nie byłe. Przecież second to teraz indeks!


  • 6. Data: 2016-05-17 20:14:07
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: bartekltg <b...@g...com>

    On 17.05.2016 19:44, Borneq wrote:
    > W dniu 17.05.2016 o 19:03, bartekltg pisze:
    >> map[elem->strHashBlock] = elem;
    >> iter->second->Add(elem);
    >>> for (int j = 1; j < vecAllElems.size(); j++)
    >>> {
    >>> CChainNode *elem = vecAllElems[j];
    >>
    >> Aż się prosi o
    >>
    >> for (auto itelem = begin(vecAllElems); itelem!=end(vecAllElems); itelem)
    >
    >
    > void buildForest()
    > {
    > unordered_map<string, size_t> map;
    > //dwa przebiegi
    > for (int i = 0; i < allnodes.size(); i++)
    > {
    > map[allnodes[i]->strHash] = i;
    > }
    > for (int i = 0; i < allnodes.size(); i++)
    > {
    > unordered_map<string, size_t>::const_iterator iter =
    > map.find(allnodes[i]->strHashParent);
    > iter->second->Add(allnodes[i]);
    > }
    > }
    >
    > Nie zrobiłem for (auto itelem = begin(vecAllElems);
    > itelem!=end(vecAllElems); itelem) ponieważ potrzebowałem indeks.

    Nie we fragmencie, który wtedy pokazałeś;-)


    > Ale w linii iter->second->Add(allnodes[i]); jest błąd:

    Nie są istotne błędy, nikt kodu nie analizował.
    Masz błąd koncepcyjny na poziomie metody rozwiązania problemu.
    Nie odniosłeś się do tego.

    pzdr
    bartekltg





  • 7. Data: 2016-05-17 22:32:59
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: "M.M." <m...@g...com>

    On Tuesday, May 17, 2016 at 4:15:07 PM UTC+2, Borneq wrote:
    > (w C++)
    > Mam elementy drzewka typy (klucz, klucz parenta), root ma własny klucz i
    > klucz parenta==NULL. Są umieszczone w pliku losowo, można do
    > optymalizacji założyć że nie całkiem losowo.
    Zależy od zastosowania. Ja bym nie 'składał drzewka', tylko zrobił
    indeks do szybkiego wyszukiwania elementów.



    > Zabrałem się to tego tak:
    > klucz jest haszem - stringiem
    > biorę mapę unordered_map<string, CChainNode*> map;
    No, dobrze, ale dzięki unordered mam możesz już szybko wyszukiwać, więc
    po co dalej składać drzewko?


    Pozdrawiam


  • 8. Data: 2016-05-17 22:43:24
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: bartekltg <b...@g...com>

    On 17.05.2016 22:32, M.M. wrote:
    > On Tuesday, May 17, 2016 at 4:15:07 PM UTC+2, Borneq wrote:
    >> (w C++)
    >> Mam elementy drzewka typy (klucz, klucz parenta), root ma własny klucz i
    >> klucz parenta==NULL. Są umieszczone w pliku losowo, można do
    >> optymalizacji założyć że nie całkiem losowo.
    > Zależy od zastosowania. Ja bym nie 'składał drzewka', tylko zrobił
    > indeks do szybkiego wyszukiwania elementów.


    Większość zadań do zrobienia na drzewie wymagać będzie
    jednak listy potomków danego wierzchołka.

    W danych wejściowych amy jedynie informacje o ojcu.

    "Poskłądanie drzewa" = przypisanie każdemu wierzchołkowi
    listy potomków.



    >> Zabrałem się to tego tak:
    >> klucz jest haszem - stringiem
    >> biorę mapę unordered_map<string, CChainNode*> map;
    > No, dobrze, ale dzięki unordered mam możesz już szybko wyszukiwać, więc
    > po co dalej składać drzewko?

    Bo np chcę zrobić DFS.

    pzdr
    bartekltg



  • 9. Data: 2016-05-17 22:49:13
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: bartekltg <b...@g...com>

    On 17.05.2016 22:32, M.M. wrote:
    > On Tuesday, May 17, 2016 at 4:15:07 PM UTC+2, Borneq wrote:
    >> (w C++)
    >> Mam elementy drzewka typy (klucz, klucz parenta), root ma własny klucz i
    >> klucz parenta==NULL. Są umieszczone w pliku losowo, można do
    >> optymalizacji założyć że nie całkiem losowo.
    > Zależy od zastosowania. Ja bym nie 'składał drzewka', tylko zrobił
    > indeks do szybkiego wyszukiwania elementów.
    >
    >
    >
    >> Zabrałem się to tego tak:
    >> klucz jest haszem - stringiem
    >> biorę mapę unordered_map<string, CChainNode*> map;
    > No, dobrze, ale dzięki unordered mam możesz już szybko wyszukiwać, więc
    > po co dalej składać drzewko?

    Jeszcze inaczej, co moze odpowiedzieć na pytanie 'co googlać':)

    Oryginalne:

    >>>>> Mam elementy drzewka typy (klucz, klucz parenta),
    >>>>> Są umieszczone [...] losowo
    >>>>> Jak poskładać rozsypane drzewko?

    można przetłumaczyć jako:
    Mam listę (skierowanych) krawędzi w drzewie, jak na jej podstawie
    zbudować drzewo.



    pzdr
    bartekltg



  • 10. Data: 2016-05-18 13:59:20
    Temat: Re: Jak poskładać rozsypane drzewko?
    Od: "M.M." <m...@g...com>

    On Tuesday, May 17, 2016 at 10:49:14 PM UTC+2, bartekltg wrote:
    > On 17.05.2016 22:32, M.M. wrote:
    > > On Tuesday, May 17, 2016 at 4:15:07 PM UTC+2, Borneq wrote:
    > >> (w C++)
    > >> Mam elementy drzewka typy (klucz, klucz parenta), root ma własny klucz i
    > >> klucz parenta==NULL. Są umieszczone w pliku losowo, można do
    > >> optymalizacji założyć że nie całkiem losowo.
    > > Zależy od zastosowania. Ja bym nie 'składał drzewka', tylko zrobił
    > > indeks do szybkiego wyszukiwania elementów.
    > >
    > >
    > >
    > >> Zabrałem się to tego tak:
    > >> klucz jest haszem - stringiem
    > >> biorę mapę unordered_map<string, CChainNode*> map;
    > > No, dobrze, ale dzięki unordered mam możesz już szybko wyszukiwać, więc
    > > po co dalej składać drzewko?
    >
    > Jeszcze inaczej, co moze odpowiedzieć na pytanie 'co googlać':)
    >
    > Oryginalne:
    >
    > >>>>> Mam elementy drzewka typy (klucz, klucz parenta),
    > >>>>> Są umieszczone [...] losowo
    > >>>>> Jak poskładać rozsypane drzewko?
    >
    > można przetłumaczyć jako:
    > Mam listę (skierowanych) krawędzi w drzewie, jak na jej podstawie
    > zbudować drzewo.

    Ja myślałem, że rozsypane to jest takie, w którym nie ma adresów
    potomków, ale są ich klucze :D

    Pozdrawiam

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: