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

do góry

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?

do góry

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

do góry

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

do góry

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!

do góry

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

do góry

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

do góry

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

do góry

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

do góry

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

do góry