eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzukanie najdłuższego ciągu w drzewie
Ilość wypowiedzi w tym wątku: 10

  • 1. Data: 2016-05-07 07:59:02
    Temat: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

    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 ?


  • 2. Data: 2016-05-07 08:34:11
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: "M.M." <m...@g...com>

    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





  • 3. Data: 2016-05-07 11:24:09
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

    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


  • 4. Data: 2016-05-07 11:27:07
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

    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


  • 5. Data: 2016-05-07 11:44:24
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

    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



  • 6. Data: 2016-05-07 13:13:52
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

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


  • 7. Data: 2016-05-07 13:15:46
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

    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.


  • 8. Data: 2016-05-07 13:32:17
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: "M.M." <m...@g...com>

    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


  • 9. Data: 2016-05-07 14:36:40
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: Borneq <b...@a...hidden.pl>

    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



  • 10. Data: 2016-05-08 16:15:15
    Temat: Re: Szukanie najdłuższego ciągu w drzewie
    Od: bartekltg <b...@g...com>

    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

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: