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 ?

do góry

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

do góry

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

do góry

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

do góry

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

do góry

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;
}

do góry

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.

do góry

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

do góry

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

do góry

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#Pse
udocode

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

do góry