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

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

Szukanie najdłuższego ciągu w drzewie

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

Contents

  Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 07:59 +0200
    Re: Szukanie najdłuższego ciągu w drzewie "M.M." <mmarszik@gmail.com> - 2016-05-06 23:34 -0700
      Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 11:24 +0200
        Re: Szukanie najdłuższego ciągu w drzewie "M.M." <mmarszik@gmail.com> - 2016-05-07 04:32 -0700
          Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 14:36 +0200
      Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 11:27 +0200
        Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 11:44 +0200
          Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 13:13 +0200
          Re: Szukanie najdłuższego ciągu w drzewie Borneq <borneq@antyspam.hidden.pl> - 2016-05-07 13:15 +0200
        Re: Szukanie najdłuższego ciągu w drzewie bartekltg <bartekltg@gmail.com> - 2016-05-08 07:15 -0700

#28536 — Szukanie najdłuższego ciągu w drzewie

Ciągu root->syn->syn->syn..syn
Chodzi o to że mam drzewo bloków Bitcoina. Blok jednego ma parenta i 
wektor dzieci, zwykle jedno dziecko, raz na jakiś czas dwa, może być 
więcej. Idziemy od roota - bloku 0. Tych bloków jest ponad 400 tysięcy.
Co zrobić aby poziom rekursji nie był rzędu 400 tys, a co najwyżej 2-3 ?

[toc] | [next] | [standalone]

#28537

On Saturday, May 7, 2016 at 7:59:05 AM UTC+2, Borneq wrote:
> Ciągu root->syn->syn->syn..syn
> Chodzi o to że mam drzewo bloków Bitcoina. Blok jednego ma parenta i 
> wektor dzieci, zwykle jedno dziecko, raz na jakiś czas dwa, może być 
> więcej. Idziemy od roota - bloku 0. Tych bloków jest ponad 400 tysięcy.
> Co zrobić aby poziom rekursji nie był rzędu 400 tys, a co najwyżej 2-3 ?

Zapewne wiesz, jak wyszukać taki najdłuższy ciąg. O co naprawdę
pytasz? Jak to zrobić w najkrótszym czasie? Jeśli pytasz o
najkrótszy czas, to problem jest skomplikowany. Można
zapamiętać długość najdłuższego ciągu w każdym węźle. Niestety
przez to wstawianie i usuwanie będzie zajmowało nieco więcej
czasu, a drzewko zajmie nieco więcej pamięci. Czy się ogólnie 
opłaca, zależy od rozkładu statystycznego operacji. Jeśli
mało modyfikujesz, jeśli drzewo jest duże, jeśli często 
wyszukujesz najdłuższej ścieżki od roota do liścia, jeśli
masz zapas pamięci, to się będzie opłacało.

Swoją drogą, jak się mają bitcoiny? Idea bitcoinów rozwija
się czy upada?

Pozdrawiam

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

#28539

W dniu 07.05.2016 o 08:34, M.M. pisze:
> mało modyfikujesz, jeśli drzewo jest duże, jeśli często
> wyszukujesz najdłuższej ścieżki od roota do liścia, jeśli
> masz zapas pamięci, to się będzie opłacało.

Coś takiego: http://i.imgur.com/7XGaVEL.png
Drzewo raz utworzone i nie modyfikuję. Jak najszybciej i z małym 
zagłębieniem rekurencji chcę znaleźć ciąg

>
> Swoją drogą, jak się mają bitcoiny? Idea bitcoinów rozwija
> się czy upada?

Rozwija się, powstają inne np.Lisk. Problemem Bitcoina jest coraz 
cięższy blokchain.

Pozdrawiam

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

#28544

On Saturday, May 7, 2016 at 11:24:10 AM UTC+2, Borneq wrote:
> W dniu 07.05.2016 o 08:34, M.M. pisze:
> > mało modyfikujesz, jeśli drzewo jest duże, jeśli często
> > wyszukujesz najdłuższej ścieżki od roota do liścia, jeśli
> > masz zapas pamięci, to się będzie opłacało.
> 
> Coś takiego: http://i.imgur.com/7XGaVEL.png
> Drzewo raz utworzone i nie modyfikuję. Jak najszybciej i z małym 
> zagłębieniem rekurencji chcę znaleźć ciąg

Jeśli drzew nie modyfikuje się, to dlaczego nie zapamiętać 
raz znalezionego ciągu? Wyszukiwanie najdłuższego ciągu to
procedura z jednym argumentem, która zwraca jeden najdłuższy
ciąg, lub kilka gdy najdłuższych jest kilka. Ale w przypadku
drzewa idealnie zrównoważonego bedziesz miał tyle ciągów,
ile liści. Potrzebujesz jeden dowolny, czy wszystkie?

Pozdrawiam

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

#28545

W dniu 07.05.2016 o 13:32, M.M. pisze:
> Jeśli drzew nie modyfikuje się, to dlaczego nie zapamiętać
> raz znalezionego ciągu? Wyszukiwanie najdłuższego ciągu to
> procedura z jednym argumentem, która zwraca jeden najdłuższy
> ciąg, lub kilka gdy najdłuższych jest kilka. Ale w przypadku
> drzewa idealnie zrównoważonego bedziesz miał tyle ciągów,
> ile liści. Potrzebujesz jeden dowolny, czy wszystkie?

Zrobiłem, dodatkowo gdy największe będą identyczne, cofa się do wspólnej 
ścieżki


Pozdrawiam

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

#28540

W dniu 07.05.2016 o 08:34, M.M. pisze:
> najkrótszy czas, to problem jest skomplikowany. Można
> zapamiętać długość najdłuższego ciągu w każdym węźle. Niestety
> przez to wstawianie i usuwanie będzie zajmowało nieco więcej

Normalnie to bym przechodził w głąb zapisując głębokość każdego węzła i 
szukając najgłębszego. O tyle - proste.
Jednak to drzewo jest bardzo mało rozgałęzione, ale za to bardzo 
głębokie. Nie chcę rekursji z ponad 400 tys poziomów.
Chcę zapisywać na stos tylko gdy jest rozgałęzienie a ono ma być rzadko

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

#28541

W dniu 07.05.2016 o 11:27, Borneq pisze:
> Jednak to drzewo jest bardzo mało rozgałęzione, ale za to bardzo
> głębokie. Nie chcę rekursji z ponad 400 tys poziomów.
> Chcę zapisywać na stos tylko gdy jest rozgałęzienie a ono ma być rzadko

Może redukować drzewo?
http://i.imgur.com/sRfoI9o.png

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

#28542

W dniu 07.05.2016 o 11:44, Borneq pisze:
> Może redukować drzewo?
> http://i.imgur.com/sRfoI9o.png

Przykład nierekurencyjnego ze stosem znalezienia najlepszej/najdłuższej 
ściężki. Tylko że ten stos będzie zbytnio rósł?
#include "stdafx.h"
#include <stack>
#include "exception.h"
#include "Node.h"

//http://i.imgur.com/7XGaVEL.png
void makeSample0()
{
	CNode* node0 = CNode::AddRoot("0");
	CNode* node1 = node0->Add("1");
	CNode* node2 = node0->Add("2");
	CNode* node3 = node0->Add("3");
	node1->Add("4");
	node1->Add("5");
	CNode* node6 = node2->Add("6");
	node3->Add("7");
	CNode* node8 = node3->Add("8");
	CNode* node9 = node6->Add("9");
	node8->Add("12");
	CNode* node10 = node9->Add("10");
	node9->Add("11");
	node10->Add("13");
	CNode* node14 = node10->Add("14");
	node14->Add("15");
}


//Traverse tree depth-first search, pre-order, stack instead of recursion
void TreverseTree(CNode *startNode)
{
	if (startNode == NULL) throw new Exception("root == NULL");
	stack<int> treeStack;
	CNode *node = startNode;
	int nr = 0;
	while (true)
	{
		if (node->height!=0)
			throw new Exception("error");
		node->height = treeStack.size();
		cout << node->label.c_str() << " " << node->height << endl;
		while (nr >= node->childs.size())
		{
			if (treeStack.size() == 0) return;
			nr = treeStack.top();
			treeStack.pop();
			node = node->parent;
			nr++;
		}
		treeStack.push(nr);
		node = node->childs[nr];
		nr = 0;
	}
}

int main()
{
	makeSample0();
	TreverseTree(CNode::root);
     return 0;
}


--------------------------------
Node.h:
#pragma once
#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

class CNode
{
public:
	CNode();
	~CNode();
	static CNode* AddRoot(string label);
	CNode* Add(string label);
	int height;
	CNode* parent;
	vector<CNode*> childs;
	static CNode* root;
	string label;
};


--------------------------------
Node.cpp:
#include "Node.h"

CNode* CNode::root = NULL;

CNode::CNode()
{
	height = 0;
}


CNode::~CNode()
{
}

CNode* CNode::AddRoot(string label)
{
	root = new CNode();
	root->label = label;
	root->parent = NULL;
	root->height = 0;
	return root;
}

CNode * CNode::Add(string label)
{
	CNode *elem = new CNode();
	elem->label = label;
	elem->parent = this;
	childs.push_back(elem);
	return elem;
}

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

#28543

W dniu 07.05.2016 o 11:44, Borneq pisze:
> W dniu 07.05.2016 o 11:27, Borneq pisze:
>> Jednak to drzewo jest bardzo mało rozgałęzione, ale za to bardzo
>> głębokie. Nie chcę rekursji z ponad 400 tys poziomów.
>> Chcę zapisywać na stos tylko gdy jest rozgałęzienie a ono ma być rzadko
>
> Może redukować drzewo?
> http://i.imgur.com/sRfoI9o.png
>
A może dopuszczę do tak dużego stosu: 400 tys intów to 1.6 MB, stos 
maszynowy się nie zwiększa,
a dla pamięci to w dzisiejszych czasach niewiele.

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

#28547

On Saturday, May 7, 2016 at 11:27:08 AM UTC+2, Borneq wrote:
> W dniu 07.05.2016 o 08:34, M.M. pisze:
> > najkrótszy czas, to problem jest skomplikowany. Można
> > zapamiętać długość najdłuższego ciągu w każdym węźle. Niestety
> > przez to wstawianie i usuwanie będzie zajmowało nieco więcej
> 
> Normalnie to bym przechodził w głąb zapisując głębokość każdego węzła i 
> szukając najgłębszego. O tyle - proste.

I tak zrób...

> Jednak to drzewo jest bardzo mało rozgałęzione, ale za to bardzo 
> głębokie. Nie chcę rekursji z ponad 400 tys poziomów.

To nie używaj rekursji. Przechodzenie drzewa w głąb/w szerz
bez rekursji, ale za pomocą stosu/kolejki (struktury denych choćby
z stl) to podstawowa technika. Pierwszy rozdział Algorytmy struktury
 danych Diksa/rytra. W Cormenia też musi być. 

O, i nawet przez aero mi przeciekło, że w wiki jest:
https://en.wikipedia.org/wiki/Depth-first_search#Pseudocode
 
A non-recursive implementation of DFS:[6]

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop()
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Tylko zamiast indeksu wierzchołka "pushuj" parę indeks 
<wierzchołka, głebokosc> 

Złożonośc pamięciowa O(wysokość drzewa).

Pseudokod jest dla DSF dowolnego grafu, więc nawet możesz
linijkę 7 (i znaczniki w wierzchołkach) pominać

> Chcę zapisywać na stos tylko gdy jest rozgałęzienie a ono ma być rzadko

Nadal możęsz to zrobić (w 7 linijce while "jeden potomek"  to 
v:= syn v; glebokosc++, Po zrobieniu POP i tak odczytasz wysokość
ze stosu.) ale nadal masz pamieciowo O(wysokosć),
przykładem jest drzewo, gdzie każdy lewy syn nie ma potomków,
a każdy (poza ostatnim) prawy syn ma 2 potomków

/\
 /\
  /\
   /\
    /\

 pzdr
bartekltg

[toc] | [prev] | [standalone]

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

csiph-web