tree traversal se systima typou MLM

Σε αυτή την περιοχή μπορείτε να βρείτε ή να αναζητήσετε πληροφορίες σχετικές με την PHP

Συντονιστές: WebDev Moderators, Super-Moderators, PHP Moderators

Απάντηση
mgiota
Δημοσιεύσεις: 190
Εγγραφή: 15 Σεπ 2009 13:11
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

tree traversal se systima typou MLM

Δημοσίευση από mgiota » 10 Απρ 2012 10:32

Θα ήθελα τη γνώμη σας πάνω σε ένα σύστημα που φτιάχνω τύπου MLM.

Είναι ένα δίκτυο συνεργατών, όπου ο κάθε συνεργάτης εγγράφει κάποιον άλλο, ο οποίος με τη σειρά του κάνει το ίδιο, και στο τέλος υπολογίζονται με βάση μια συγκεκριμένη εξίσωση οι προμήθειες του κάθε συνεργάτη.

Όπως καταλάβατε, με νοιάζει να δημιουργήσω μια ιεραρχική δομή, έτσι ώστε όταν ένας συνεργάτης μπαίνει στο σύστημα να βλέπει το δίκτυο του (αυτούς που είναι κάτω του αλλά μέχρι βάθος 3).

Έχω βάλει μια στήλη parent στη βάση και έχω καταφέρει να δημιουργήσω έναν multidimensional array of parent > child. Ο πίνακας αυτός κρατάει από το id που θέλω και κάτω όλη τη δενδρική μορφή, και μετά με κάποιον τρόπο στην εμφάνιση ελέγχω και εμφανίζω μέχρι το 3ο επίπεδο. Νόμιζα ότι τα είχα καταφέρει, αλλά όταν βάζω το pagination βλέπω έχω πρόβλημα, γιατί ως σύνολο εγγραφών θεωρεί από το id που του λέω μέχρι το τέλος και όχι μέχρι το βάθος που θέλω. Χρησιμοποιώ το pagination που έχει έτοιμο το CodeIgniter, μια και το στήνω με αυτό.

σκέφτηκα να επέμβω στο pagination, αλλά άρχισα να ψάχνω στο google και έπεσα στην έννοια των nested sets.

Αυτό που ήθελα να ρωτήσω είναι αν ενδείκνυνται για αυτήν την περίπτωση. Διαφορετικά είναι εφικτό από τον array που έχω να πάρω ένα συγκεκριμένο κομμάτι που θέλω μέχρι το 3ο level? μου κάνει νομίζω περίπλοκο, γι' αυτό και στράφηκα σε άλλη κατεύθυνση.


Παραθέτω και 2 links που βρήκα

http://www.sitepoint.com/hierarchical-data-database/

http://codeigniter.com/wiki/Nested_sets

Άβαταρ μέλους
cpulse
Script Master
Δημοσιεύσεις: 1527
Εγγραφή: 21 Μαρ 2006 19:30
Τοποθεσία: Αθήνα village
Επικοινωνία:

tree traversal se systima typou MLM

Δημοσίευση από cpulse » 10 Απρ 2012 17:43

Γνωρίζεις οτι αυτά τα πράγματα λέγονται πυραμίδες και οτι είναι παράνομα;

mgiota
Δημοσιεύσεις: 190
Εγγραφή: 15 Σεπ 2009 13:11
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

tree traversal se systima typou MLM

Δημοσίευση από mgiota » 10 Απρ 2012 17:51

σαφέστατα δεν το φτιάχνω αυτό για μένα. ως freelancer αν καταφέρω να το φτιάξω καλά θα είναι. προγραμματιστικά και μόνο με ενδιαφέρει. όποιος μπορεί να πει την άποψήη του θα ήταν βοηθητικό για μένα.

ευχαριστώ

Άβαταρ μέλους
cpulse
Script Master
Δημοσιεύσεις: 1527
Εγγραφή: 21 Μαρ 2006 19:30
Τοποθεσία: Αθήνα village
Επικοινωνία:

tree traversal se systima typou MLM

Δημοσίευση από cpulse » 10 Απρ 2012 18:02

Πέρα της παρανομίας.. δεν σε ενοχλεί να ξέρεις οτι θα χάσει κόσμος τα λεφτά του εξ αιτίας σου; Και μάλιστα σε καιρό που όλοι ψάχνουν να κρεμμαστούν από μια ελπίδα.

mariosal
Honorary Member
Δημοσιεύσεις: 1473
Εγγραφή: 09 Νοέμ 2007 23:55

tree traversal se systima typou MLM

Δημοσίευση από mariosal » 12 Απρ 2012 15:44

Απ' ό,τι έχω καταλάβει το πρόβλημά σου μπορεί να αναχθεί σε Θεωρία Γράφων που προϋποθέτει γνώση αλγορίθμων. Αν δεν έχεις ασχοληθεί με αλγορίθμους θα σου φανεί δύσκολο, αλλά δε με εκπλήσσει διότι θες να κάνεις κάτι πολύ custom.

Αυτό που ψάχνεις λέγεται Graph Traversal και μπορεί να γίνει με τον αλγόριθμο BFS( Breadth-First Search ).

Σημαντικές για την υλοποίηση των δύο αλγορίθμων θα σου φανούν οι διαφάνειες του μαθήματος "Εισαγωγή στην Επιστήμη των Υπολογιστών" των Στ. Ζάχου, Ά. Παγουρτζή, Δ. Φωτάκη.

Επίσης πρέπει να γνωρίζεις θεωρητικά τις ακόλουθες δομές δεδομένων, δε χρειάζεται να ξέρεις να τις υλοποιείς μιας και υπάρχουν έτοιμες στις περισσότερες γλώσσες: LET'S GO! :D

Μέσω BFS μπορούμε να αποθηκεύσουμε κάθε κόμβο που είναι προσβάσιμος από ένα συγκεκριμένο source. Όμως με κάποιον τρόπο πρέπει να αποκλείσουμε όσα έχουν βάθος >3.

Στην ουρά εκτός από το id του επομένου κόμβου προσθέτουμε επίσης και το βάθος του, οπότε έχουμε την εξής ιδέα: Ο πρώτος κόμβος δηλαδή το source θα έχει βάθος 0 και όταν είμαι σε έναν κόμβο v με βάθος d, βάζω όλους τους γείτονες του v στην ουρά με βάθος d + 1 υπό την προϋπόθεση ότι d + 1 < 3.

Αρχικά δημιουργούμε την αναπαράσταση του γράφου με Adjacency List, μετά ορίζουμε το source που είναι η ρίζα του δένδρου και το μέγιστο επιτρεπόμενο βάθος. Υπενθυμίζω ότι για $maxDepth = 0 ο μόνος αποδεκτός κόμβος είναι το source. Έπειτα τρέχουμε το bfs και τυπώνουμε τους αποδεκτούς κόβμους.

Κώδικας: Επιλογή όλων

<?php
    function bfs&#40; $G, $src, $maxDepth &#41; &#123;
        $qLen = 0;
        $front = array&#40;&#41;;
        $marked = array&#40;&#41;;
        $q = array&#40;&#41;;

        array_push&#40; $marked, $src &#41;;
        array_push&#40; $q, array&#40;
            'id' => $src,
            'depth' => 0
        &#41; &#41;;
        ++$qLen;
        while &#40; $qLen &#41; &#123; 
            $front = array_shift&#40; $q &#41;;
            --$qLen;

            foreach &#40; $G&#91; $front&#91; 'id' &#93; &#93; as $it &#41; &#123; 
                if &#40; $front&#91; 'depth' &#93; + 1 <= $maxDepth &#41; &#123; 
                    if &#40; !in_array&#40; $it, $marked &#41; &#41; &#123; 
                        array_push&#40; $marked, $it &#41;;
                        if &#40; $front&#91; 'depth' &#93; + 1 < $maxDepth &#41; &#123; 
                            array_push&#40; $q, array&#40;
                                'id' => $it,
                                'depth' => $front&#91; 'depth' &#93; + 1 
                            &#41; &#41;;
                            ++$qLen;
                        &#125;   
                    &#125;   
                &#125;   
            &#125;   
        &#125;   

        return $marked;
    &#125;   

    // Adjacency List
    $G = array&#40;
        1 => array&#40; 2, 3 &#41;,
        2 => array&#40; 4, 5 &#41;,
        3 => array&#40; 5, 6 &#41;,
        4 => array&#40; 7, 8 &#41;,
        5 => array&#40; 8, 9 &#41;,
        6 => array&#40; 9, 10 &#41;
    &#41;;  
    $src = 1;
    $maxDepth = 3;
    $marked = bfs&#40; $G, $src, $maxDepth  &#41;;  

    // Print vertices with depth <= $maxDepth
    echo count&#40; $marked &#41;, "\n";
    foreach &#40; $marked as $it &#41; &#123; 
        echo $it, ' ';
    &#125;   
    echo "\n";
?>
Φυσικα η Adjacency List σου δεν θα περιέχει ids, όπως η δική μου, αλλά τα ονόματα των συνεργατών σε strings, οπότε θα χρειαστεί να σκεφτείς πώς θα το μετατρέψεις, παρά ταύτα η bfs() μένει η ίδια.

Τώρα όσον αφορά την πολυπλοκότητα χαλάνε τα πράγματα. Με πρόχειρους υπολογισμούς βλέπω Ο( |V|² ). Αυτό οφείλεται κυρίως στο ότι η in_array() και η array_push() μέσα στη while της bfs() κοστίζουν γραμμικό χρόνο, O( |V| ). Όμως μπορούμε με λίγο κώδικα χρησιμοποιώντας Binary Search να μειώσουμε την αναζήτηση σε O( log|V| ), εφόσον ο πίνακας παραμένει ταξινομημένος! Αυτό το επιτυγχάνουμε βρίσκοντας με Binary Search που θα 'πρεπε να μπει στο νέο στοιχείο και μετά γραμμικά το εισάγουμε πηγαίνοντας κάθε στοίχειο μια θέση δεξιά.

Οπότε η τελική bfs() μπορεί να γίνει ως έξης.

Κώδικας: Επιλογή όλων

<?php
    function search&#40; $a, $val, $start, $end &#41; &#123;
        $mid = 0;
        while &#40; $start <= $end &#41; &#123;
            $mid = &#40; int &#41;&#40; &#40; $start + $end &#41; / 2 &#41;;

            if &#40; $a&#91; $mid &#93; < $val &#41; &#123;
                $start = $mid + 1;
            &#125;
            else if &#40; $a&#91; $mid &#93; > $val &#41; &#123;
                $end = $mid - 1;
            &#125;
            else &#123;
                return true;
            &#125;
        &#125;
        return false;
    &#125;
    function insert&#40; &$a, $end, $val &#41; &#123;
        $start = 0;
        $mid = 0;
        $pos = 0;
        while &#40; $start <= $end &#41; &#123;
            $mid = &#40; int &#41;&#40; &#40; $start + $end &#41; / 2 &#41;;

            if &#40; $a&#91; $mid &#93; < $val &#41; &#123;
                $pos = $mid + 1;
                $start = $mid + 1;
            &#125;
            else if &#40; $a&#91; $mid &#93; > $val &#41; &#123;
                $pos = $mid;
                $end = $mid - 1;
            &#125;
        &#125;

        array_splice&#40; $a, $pos, 0, array&#40; $val &#41; &#41;;
    &#125;

    function bfs&#40; $G, $src, $maxDepth &#41; &#123;
        $qLen = 0;
        $markedLen = 0;
        $front = array&#40;&#41;;
        $marked = array&#40;&#41;;
        $q = array&#40;&#41;;

        array_push&#40; $marked, $src &#41;;
        ++$markedLen;
        array_push&#40; $q, array&#40;
            'id' => $src,
            'depth' => 0
        &#41; &#41;;
        ++$qLen;
        while &#40; $qLen &#41; &#123;
            $front = array_shift&#40; $q &#41;;
            --$qLen;

            foreach &#40; $G&#91; $front&#91; 'id' &#93; &#93; as $it &#41; &#123;
                if &#40; $front&#91; 'depth' &#93; + 1 <= $maxDepth &#41; &#123;
                    if &#40; !search&#40; $marked, $it, 0, $markedLen - 1 &#41; &#41; &#123;
                        insert&#40; $marked, $markedLen - 1, $it &#41;;
                        ++$markedLen;
                        if &#40; $front&#91; 'depth' &#93; + 1 < $maxDepth &#41; &#123;
                            array_push&#40; $q, array&#40;
                                'id' => $it,
                                'depth' => $front&#91; 'depth' &#93; + 1
                            &#41; &#41;;
                            ++$qLen;
                        &#125;
                    &#125;
                &#125;
            &#125;
        &#125;

        return $marked;
    &#125;
?>
Ελπίζω να πιάσουν τόπο όλα αυτά που έχω γράψει :P
Τελευταία επεξεργασία από το μέλος mariosal την 12 Απρ 2012 16:02, έχει επεξεργασθεί 1 φορά συνολικά.

mgiota
Δημοσιεύσεις: 190
Εγγραφή: 15 Σεπ 2009 13:11
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

tree traversal se systima typou MLM

Δημοσίευση από mgiota » 12 Απρ 2012 15:52

Σ' ευχαριστώ πολύ για την απάντησή σου!

Μ' αρέσουν πολύ οι αλγόριθμοι και οι δομές δεδομένων (στο προπτυχιακό τα έκανα αυτά), απλά δε έτυχε να εφαρμόσω κάτι τέτοιο στην πράξη πέρα από κλασικά custom CMS.

Θα τα διαβάσω προσεχτικά και πιστεύω να βγει. Αν έχω κάποια απορία, θα ποστάρω.

Σ'ευχαριστώ πολύ:-)

Απάντηση

Επιστροφή στο “PHP Προγραμματισμός”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες