Jak poskładać rozsypane drzewko?

Path	csiph.com!goblin2!goblin.stu.neva.ru!news.nask.pl!news.nask.org.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail
From	Borneq <borneq@antyspam.hidden.pl>
Newsgroups	pl.comp.programming
Subject	Jak poskładać rozsypane drzewko?
Date	Tue, 17 May 2016 16:15:05 +0200
Organization	ATMAN - ATM S.A.
Lines	57
Message-ID	<nhf91a$pgp$1@node2.news.atman.pl> (permalink)
NNTP-Posting-Host	91.239.205.105
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	8bit
X-Trace	node2.news.atman.pl 1463494506 26137 91.239.205.105 (17 May 2016 14:15:06 GMT)
X-Complaints-To	usenet@atman.pl
NNTP-Posting-Date	Tue, 17 May 2016 14:15:06 +0000 (UTC)
User-Agent	Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0
X-Mozilla-News-Host	news://news.atman.pl:119
Xref	csiph.com pl.comp.programming:28592

Show key headers only | View raw

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

Back to pl.comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web