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

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

Jak poskładać rozsypane drzewko?

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

Contents

  Jak poskładać rozsypane drzewko? Borneq <borneq@antyspam.hidden.pl> - 2016-05-17 16:15 +0200
    Re: Jak poskładać rozsypane drzewko? Borneq <borneq@antyspam.hidden.pl> - 2016-05-17 17:54 +0200
    Re: Jak poskładać rozsypane drzewko? bartekltg <bartekltg@gmail.com> - 2016-05-17 19:03 +0200
      Re: Jak poskładać rozsypane drzewko? Borneq <borneq@antyspam.hidden.pl> - 2016-05-17 19:44 +0200
        Re: Jak poskładać rozsypane drzewko? Borneq <borneq@antyspam.hidden.pl> - 2016-05-17 20:06 +0200
        Re: Jak poskładać rozsypane drzewko? bartekltg <bartekltg@gmail.com> - 2016-05-17 20:14 +0200
    Re: Jak poskładać rozsypane drzewko? "M.M." <mmarszik@gmail.com> - 2016-05-17 13:32 -0700
      Re: Jak poskładać rozsypane drzewko? bartekltg <bartekltg@gmail.com> - 2016-05-17 22:43 +0200
      Re: Jak poskładać rozsypane drzewko? bartekltg <bartekltg@gmail.com> - 2016-05-17 22:49 +0200
        Re: Jak poskładać rozsypane drzewko? "M.M." <mmarszik@gmail.com> - 2016-05-18 04:59 -0700
          Re: Jak poskładać rozsypane drzewko? bartekltg <bartekltg@gmail.com> - 2016-05-18 14:27 +0200

#28592 — Jak poskładać rozsypane drzewko?

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

[toc] | [next] | [standalone]

#28593

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?

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

#28594

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

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

#28595

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

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

#28596

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!

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

#28597

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

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

#28598

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

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

#28599

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

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

#28600

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

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

#28601

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

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

#28602

On 18.05.2016 13:59, M.M. wrote:
> 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

To też, ale to nie jest, jak sam zauważyłeś, wielkim problemem:)

pzdr
bartekltg

[toc] | [prev] | [standalone]

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

csiph-web