Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > PHP: Общие вопросы > Бесконечное деление пирамиды


Автор: nepster 1.8.2012, 16:46
Значит есть такая задача сделать бесконечное деление пирамиды.  С подобной сложностью еще не сталкивался и вот хочу узнать совета у спецов, как это лучше реализовать.

Сама задача такая, есть пирамида:



Код

                              [1]
                          [2]    [3]
                      [4] [5]    [6] [7]
            [8] [9] [10] [11]    [12] [13] [14] [15]



тоесть ячейки: 1,2,4,8,16   и тд. 


когда заполняются все поля, то пирамида делится на еще 2 пирамиды и к ним в конец добавляется еще 8 ячеек.


Код

                              
                          [2]   
                        [4] [5]   
                   [8] [9]  [10] [11]   
          [-] [-] [-] [-]  [-] [-] [-] [-]   



Код

                      
                         [3]
                      [6] [7]
                [12] [13] [14] [15]
          [-] [-] [-] [-]  [-] [-] [-] [-]   



дальше, как только последние 8 ячеек (их может быть и 16, не важно) заполняются, то эти 2 пирамиды делятся еще, каждая по две 
(и так же в конец 8 ячеек )







1 пирамида 

Код

                      
                    
                      [4]                                      [5]
                  [8] [9]                                  [10] [11]
              [-] [-] [-] [-]                            [-] [-] [-] [-]   
       [-] [-] [-] [-] [-] [-] [-] [-]         [-] [-] [-] [-]  [-] [-] [-] [-]






2 пирамида 

Код

                      
                    
                      [6]                                      [7]
                  [12] [13]                                [14] [15]
              [-] [-] [-] [-]                            [-] [-] [-] [-]   
       [-] [-] [-] [-] [-] [-] [-] [-]         [-] [-] [-] [-]  [-] [-] [-] [-]



Ну и так деление пирамид и добавление ячеек до бесконечности. 


Я долго думал как это реализовать и вот появилась идея:

 1) База данных, где записи о каждой  существующей ячейке. 
 2) сами пирамиды представлены в виде массива 



К примеру мы составим массив 1 пирамиды 

Код

$data[0] = array(array('cell_id' => 1,'user_id' => 23));

$data[1] = array(
                 '0' => array('cell_id' => 2,'user_id' => 43),
                 '1' => array('cell_id' => 3,'user_id' => 233)
                );
                
$data[2] = array(
                 '0' => array('cell_id' => 4,'user_id' => 32),
                 '1' => array('cell_id' => 5,'user_id' => 343),
                 '2' => array('cell_id' => 6,'user_id' => 24),
                 '3' => array('cell_id' => 7,'user_id' => 543)
                );
                
$data[3] = array(
                 '0' => array('cell_id' => 8,'user_id' => 0),
                 '1' => array('cell_id' => 9,'user_id' => 0),
                 '2' => array('cell_id' => 10,'user_id' => 0),
                 '3' => array('cell_id' => 11,'user_id' => 0),
                 '4' => array('cell_id' => 12,'user_id' => 0),
                 '5' => array('cell_id' => 13,'user_id' => 0),
                 '6' => array('cell_id' => 14,'user_id' => 0),
                 '7' => array('cell_id' => 15,'user_id' => 0)
                );




Вид он получит такой: 

Код

Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [cell_id] => 1
                    [user_id] => 23
                )

        )

    [1] => Array
        (
            [0] => Array
                (
                    [cell_id] => 2
                    [user_id] => 43
                )

            [1] => Array
                (
                    [cell_id] => 3
                    [user_id] => 233
                )

        )

    [2] => Array
        (
            [0] => Array
                (
                    [cell_id] => 4
                    [user_id] => 32
                )

            [1] => Array
                (
                    [cell_id] => 5
                    [user_id] => 343
                )

            [2] => Array
                (
                    [cell_id] => 6
                    [user_id] => 24
                )

            [3] => Array
                (
                    [cell_id] => 7
                    [user_id] => 543
                )

        )

    [3] => Array
        (
            [0] => Array
                (
                    [cell_id] => 8
                    [user_id] => 0
                )

            [1] => Array
                (
                    [cell_id] => 9
                    [user_id] => 0
                )

            [2] => Array
                (
                    [cell_id] => 10
                    [user_id] => 0
                )

            [3] => Array
                (
                    [cell_id] => 11
                    [user_id] => 0
                )

            [4] => Array
                (
                    [cell_id] => 12
                    [user_id] => 0
                )

            [5] => Array
                (
                    [cell_id] => 13
                    [user_id] => 0
                )

            [6] => Array
                (
                    [cell_id] => 14
                    [user_id] => 0
                )

            [7] => Array
                (
                    [cell_id] => 15
                    [user_id] => 0
                )

        )

)





[cell_id]   => id ячейки пирамиды в базе 
[user_id] => id пользователя, который состоит в данной ячейке, если 0, то она пустая. 



К примеру делим пирамиду на две 


Первая пирамида будет вот такая: (последние 8 ячеек добавляются пустые, для новых юзеров, все остальные уже заполнены, так как деление происходит только тогда, когда вся пирамида заполняется.) 

Код

Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [cell_id] => 1
                    [user_id] => 23
                )

        )

    [1] => Array
        (
            [0] => Array
                (
                    [cell_id] => 2
                    [user_id] => 43
                )

        )

    [2] => Array
        (
            [0] => Array
                (
                    [cell_id] => 4
                    [user_id] => 32
                )

            [1] => Array
                (
                    [cell_id] => 5
                    [user_id] => 343
                )

        )

    [3] => Array
        (
            [0] => Array
                (
                    [cell_id] => 8
                    [user_id] => 11
                )

            [1] => Array
                (
                    [cell_id] => 9
                    [user_id] => 12
                )

            [2] => Array
                (
                    [cell_id] => 10
                    [user_id] => 13
                )

            [3] => Array
                (
                    [cell_id] => 11
                    [user_id] => 14
                )

        )

    [4] => Array
        (
            [0] => Array
                (
                    [cell_id] => 8
                    [user_id] => 0
                )

            [1] => Array
                (
                    [cell_id] => 9
                    [user_id] => 0
                )

            [2] => Array
                (
                    [cell_id] => 10
                    [user_id] => 0
                )

            [3] => Array
                (
                    [cell_id] => 11
                    [user_id] => 0
                )

            [4] => Array
                (
                    [cell_id] => 12
                    [user_id] => 0
                )

            [5] => Array
                (
                    [cell_id] => 13
                    [user_id] => 0
                )

            [6] => Array
                (
                    [cell_id] => 14
                    [user_id] => 0
                )

            [7] => Array
                (
                    [cell_id] => 15
                    [user_id] => 0
                )

        )

)




Подскажите пожалуйста, в правильном ли направлении идут мысли и как можно будет осуществить подобное деление пирамиды из массива. 

Автор: Чучмек 1.8.2012, 18:36
А если не секрет, зачем такое надо?

Автор: nepster 1.8.2012, 18:43
вероятнее всего строят финансовую пирамиду.  Мне предложили разработать для них вот такую систему. Но прежде чем браться за работу, я решил подумать действительно ли я смогу сделать подобное. Вот и собственно написал свои идеи по реализации. 

Вообще для чего и зачем меня мало волнует, мне нравится разрабатывать какие-то сложные вещи, а с таким я не сталкивался, даже интерес возник.  

Автор: Sanchezzz 1.8.2012, 18:55
скорее всего это не фин пирамида, так как если основываясь на принципах пирамиды то один человек может привести в систему от одного человека до 5-10 как тогда должна выглядить пирамида в виде лесинки
Код

                         [3]
                      [6] [7]
                [12] [13] [14] [15]
          [-] [-] [-] [-]  [-] [-] [-] [-]   

Автор: baldina 1.8.2012, 19:17
это все чрезвычайно похоже на полное двоичное дерево (которое прекрасно укладывается в одномерный массив).
"деление" двоичного дерева на пирамиды суть, как я понимаю, просто получение поддеревьев.
какие операции с этими пирамидами предусматриваются? какая информация о пирамиде(ах) должна быть доступна? от этого будет зависеть все остальное.

Автор: nepster 1.8.2012, 23:12
Цитата

какие операции с этими пирамидами предусматриваются ? 


на столько детально я не знаю. Но суть такая, что как только в пирамиде заполняются последние 8 ячеек, то она делится на 2 и к каждой добавляются еще по 8 ячеек. 


тоесть вот к примеру идет 1 пирамида 


Код

                              [1]
                          [2]    [3]
                      [4] [5]    [6] [7]
            [8] [9] [10] [11]    [12] [13] [14] [15]



хоп она разделилась на 2 

Код

                           [2]   
                        [4] [5]   
                   [8] [9]  [10] [11]   
          [-] [-] [-] [-]  [-] [-] [-] [-]   


               [3]
                      [6] [7]
                [12] [13] [14] [15]
          [-] [-] [-] [-]  [-] [-] [-] [-] 



а вот пользователь, который был в верху (тоесть юзер в ячейке 1, вообще исчезает из пирамиды). Скорее всего ему выплатили деньги и он вне игры. 



А вот как "валидно" разделить массив на 2, я еще не придумал.

Добавлено через 13 секунд
Но так понял, мыслю пока верно !? 

Автор: Fortop 2.8.2012, 00:03
Цитата(nepster @  1.8.2012,  16:46 Найти цитируемый пост)
Ну и так деление пирамид и добавление ячеек до бесконечности.

Кто сказал что это деление пирамид?

Добавлено через 1 минуту
Куда исчезает ячейка №1 после вашего "деления"?
Куда исчезают ячейки №2 и №3 на втором цикле? Ну и т.д.

Автор: nepster 2.8.2012, 01:33
к примеру есть юзер  Вася, он стоит в ячейке номер 1. 
Когда Вася пригласит всех людей и пирамида заполнится,  скорее всего он получит выплату или что то там получит и больше не является участником системы. Тоесть исчезает из пирамиды. А пирамида делится на 2 части. Где  юзеры Иванов и Петров с ячейками 2 и 3  стали вместо него.  И так же само, когда пирамиды заполнятся, то они выйдут из системы и пирамиды разделятся. 

Автор: baldina 2.8.2012, 02:02
используйте двоичное дерево. оно будет расти само как надо, просто добавляйте в конец. для удаления корней (и "деления") просто помечайте узлы, что они не активны. узлы, у которых родитеь удален (неактивен), будут являться вершинами ваших пирамид.

Добавлено через 8 минут и 3 секунды
если пирамиды заполняются равномерно, и дерево полное, все удаленные узлы будут находиться в начале массива. т.е. найти все пирамиды можно будет легко, найдя первый активный узел и посчитав по дороге на каком уровне начинаются активные: если первый активный узел имеет индекс $i, то мы имеем $n = 2*$i пирамиды, корни которых находятся в соседних ячейках. восстановить пирамиду можно пользуясь фактом, что дочерние узлы узла $k находятся в ячейках 2*$k и 2*$k+1, далее рекурсивно.

Добавлено через 10 минут и 46 секунд
Цитата(nepster @  1.8.2012,  23:12 Найти цитируемый пост)
 Скорее всего ему выплатили деньги и он вне игры. 

Скорее всего его где-то прикопали, и он вне игры. Деньги из пирамид не уходят)))

Автор: nepster 2.8.2012, 02:22
Цитата

Скорее всего его где-то прикопали, и он вне игры. Деньги из пирамид не уходят)))


НУ это уже как говориться не мои проблемы =)



Я примерно вас понял, завтра попробую начать разрабатывать дерево.  Вот тут есть еще 1 момент. 

К примеру на верхушке пользователь Вася,  а пользователь иванов в 3 ячейке к примеру. 

Когда иванов заходит в свой профиль, он видит пирамиду Васи, так как Вася на верхушке.  А вот когда пирамида делится и Иванов становится на верхушке и скажем после 10 таких делений, будет уже за 20  пирамид, то каждый юзер должен попадать в свою пирамиду.  Вот тут я еще не придумал как для нужного юзера воспроизводить его пирамиду.  Вероятно каждая пирамидка должна бегать с массивов, где хранятся все ее ячейки !? 

Автор: MoLeX 2.8.2012, 06:37
 smile 
Я точно такой же заказ доделываю) Все пирамиды осуществлены. Там два дерево должно быть, для того чтобы не мучаться в дальнейшем

nepster, стукни в личку/асю - поговорим)

Автор: baldina 2.8.2012, 09:00
Цитата(MoLeX @  2.8.2012,  06:37 Найти цитируемый пост)
Там два дерево должно быть

второе зачем?
ТС не огласил задачу, ибо сам не знает. пока очевидно только, что пирамиды нужно идентифицировать.

Цитата(nepster @  2.8.2012,  02:22 Найти цитируемый пост)
Когда иванов заходит в свой профиль, он видит пирамиду Васи, так как Вася на верхушке.  А вот когда пирамида делится и Иванов становится на верхушке и скажем после 10 таких делений, будет уже за 20  пирамид, то каждый юзер должен попадать в свою пирамиду.  Вот тут я еще не придумал как для нужного юзера воспроизводить его пирамиду.  Вероятно каждая пирамидка должна бегать с массивов, где хранятся все ее ячейки !? 

можно переформулировать проблему так: найти корень дерева, в которую входит ячейка с известным индексом $i.
идем от $i вверх пока не встретится неактивная ячейка.
Код

while ($i>0 and is_active ($tree[$i])) {
  $rem = $i%2;
  $i = (int)($i/2);
}
$my_root=2*$i+$rem;

Автор: MoLeX 2.8.2012, 09:27
Все придумано уже давно, не лепите огород. Берем обычное Nested Sets дерево, немного модернизируем его и все

Автор: baldina 2.8.2012, 09:52
давно придумано много чего. например, стрелять из пушки по воробьям

Автор: Fortop 2.8.2012, 11:18
Солидарен с baldina.
И вообще не понимаю, как можно вразумительно сделать задачу не понимая ее условий.
Хорошо если задачу вам ставил тим-лид, который знает что нужно...
А если это был клиент?

Добавлено через 2 минуты и 15 секунд
Цитата(nepster @  2.8.2012,  01:33 Найти цитируемый пост)
Тоесть исчезает из пирамиды. А пирамида делится на 2 части.

Ничего никуда не исчезает и ничего не делится.
Другой вопрос, что статусы могут меняться. И таки, как и писал выше baldina, бинарное дерево полностью подходит под эти намеки.

Автор: nepster 2.8.2012, 15:18
как вы думаете, сколько бы стоила разработка скрипта финансовой пирамиды ? 

Автор: baldina 2.8.2012, 17:04
а задача уже поставлена? огласите весь список, пожалуйста

Добавлено через 6 минут и 57 секунд
операции на основе двоичных деревьев займут строк 20.
если запихнуть это в класс и добавить комментарии - может до 100-150 вырасти.
а уж что бы решить всю задачу (про которую мы так ничего и не знаем) может и 1000, и 10000 придется написать.
Вы определяете сколько взять с заказчика? Сначала определитесь с требованиями к скрипту.
ЗЫ: Можно заделать на основе Nested Sets, там одних скриптов на sql строк 500 будет))

Добавлено через 12 минут и 3 секунды
Цитата

— За сколько сделаешь?
— За день сделаю.
— А за два?
— Ну… За… Сделаем и за два.
— А за пять дней?
— Ну, ежели постараться — можно и за пять.
— А за десять?
— Ну, барин, ты задачи ставишь! За десять дён одному не справиться, тут помощник нужен — хомо сапиенс!

Автор: nepster 3.8.2012, 03:05
пирамида пользователей. Подтвердить пользователя, удалить пользователя их пирамиды. 
История пирамид. К примеру юзер выбыл, но он пожет посмотреть свою пирамиду и пирамиды тех кого пригласил. Тоесть можно воспроизводить пирамиды определенного юзера.  Все это модуль к джумле( джумла - это не моя идея =) ).

Собственно вот. Как думаете какая будет цена данной работы ? 

Видел классы, там сайт автора не работает, при том тут нет порядка вложенности. Сегодня почти доделал скрипт воспроизведения пирамиды (html таблице) из массива данных.  Как доделаю кину на заценить =).

Автор: baldina 3.8.2012, 11:36
Цитата(nepster @  3.8.2012,  03:05 Найти цитируемый пост)
Видел классы, там сайт автора не работает, при том тут нет порядка вложенности. 

переведи

Добавлено через 2 минуты и 59 секунд
Цитата(nepster @  3.8.2012,  03:05 Найти цитируемый пост)
История пирамид. К примеру юзер выбыл, но он пожет посмотреть свою пирамиду и пирамиды тех кого пригласил.

это как может быть? согласно предыдущему разговору они либо в одной пирамиде, либо тот кто пригласил уже вне пирамид, неактивен (прикопан=).
если последнее, то все так же просто, т.к. ничего не удаляется, а просто помечается, т.е. историю можно восстановить 

Автор: Чучмек 3.8.2012, 21:55
Должно быть два массива: массив  users и массив верхушек пирамид tops

Массив users в виде дерева:
                                                                                                     [0]
                                                  [1]                                                                                                   [2]
                         [3]                                              [4]                                                [5]                                               [6]
            [7]                    [8]                      [9]                    [10]                   [11]                    [12]                  [13]                     [14]
    [15]      [16]      [17]      [18]       [19]      [20]       [21]      [22]      [23]       [24]       [25]      [26]      [27]       [28]      [29]       [30]
[31][32][33][34][35][36][37][38][39][40][41][42][43][44][45][46][47][48][49][50][51][52][53][54][55][56][57][58][59][60][61][62]

Очевидно что уровень n - будет содержать  2^n элементов
Индекс 1го элемента на уровне n ,будет (I+1)*2^n-1 где I-индекс вершины
Так если вершина - элемент с индексом 10
То на 0 уровне  (10+1)*1-1=10
    на 1 уровне   (10+1)*2-1=21
    на 2  уровне  (10+1)*4-1=43

Перебор элементов пирамиды
Код

//$I - содержит индекс вершины
//$ncount - содержит число уровней в пирамиде
for ($n=0;$n<$ncount;$n++)
 {
 $lcount=1 << $n;
 $i0=($I+1)* $lcount-1;
 for($il=$i0;$il<$i0+$lcount;$il++)
   {
   //что-нибудь делаем с $users[$il]
   }
 }  


Определение пирамиды(индекс вершины) , к которой принадлежит элемент с индексом $i
Код

$I=$i;
while (!in_array($I,$tops))
  {
  $I= ($I-1) >>1;
  } 

По заполнении пирамиды индекс ее вершины удаляется из $tops, а индексы ее элементов  с уровня 1 добавляются в конец $tops

Автор: Fortop 4.8.2012, 03:17
Цитата(Чучмек @  3.8.2012,  21:55 Найти цитируемый пост)
Должно быть два массива: массив  users и массив верхушек пирамид tops


Цитата(Чучмек @  3.8.2012,  21:55 Найти цитируемый пост)
о заполнении пирамиды индекс ее вершины удаляется из $tops, а индексы ее элементов  с уровня 1 добавляются в конец $tops

Блин, а зачем?

Кто мешает хранить атрибут сразу вместе с элементом?
Выбрать любой произвольный элемент с его иерархией можно простой итерацией.

Автор: nepster 4.8.2012, 03:21
тут просто так походу перебирать и удалять не получится, так как везде должна быть история. У меня идея сейчас такая:

таблица users и pyramid 

pyramid

Код

+--------+----------+---------+------+
| id | top_user | set     | status | 
+--------+----------+---------+------+
| 0  | 23           | json   | 1           |       
| 1  | 26           | json   | 0           |       
| 2  | 12           | json   | 1           |       
| 3  | 76           | json   | 0           |       
+--------+----------+---------+------+



top_user  - id пользователя, который на верху 
         set  - json со списком юзеров 
    status  - 1 пирамида в действии, 0 - закончена. 


json данные будут выглядеть примерно так 

Код

[[{"cell_id":2,"user_id":43}],[{"cell_id":4,"user_id":32},{"cell_id":5,"user_id":343},{"cell_id":5,"user_id":343}],[{"cell_id":8,"user_id":11},
{"cell_id":9,"user_id":12},{"cell_id":10,"user_id":13},{"cell_id":11,"user_id":14},{"cell_id":11,"user_id":14},{"cell_id":11,"user_id":14},
{"cell_id":11,"user_id":14},{"cell_id":11,"user_id":14},{"cell_id":11,"user_id":14}],[{"cell_id":8,"user_id":0},{"cell_id":9,"user_id":0},
{"cell_id":10,"user_id":0},{"cell_id":11,"user_id":0},{"cell_id":12,"user_id":0},{"cell_id":13,"user_id":0},{"cell_id":14,"user_id":0},{"cell_id":15,"user_id":0},
{"cell_id":15,"user_id":0},{"cell_id":16,"user_id":0},{"cell_id":17,"user_id":54},{"cell_id":18,"user_id":0},{"cell_id":19,"user_id":0},{"cell_id":20,"user_id":0},
{"cell_id":21,"user_id":0},{"cell_id":22,"user_id":0},{"cell_id":23,"user_id":0},{"cell_id":24,"user_id":0},{"cell_id":25,"user_id":0},{"cell_id":26,"user_id":0},
{"cell_id":27,"user_id":0},{"cell_id":28,"user_id":0},{"cell_id":29,"user_id":0},{"cell_id":30,"user_id":0},{"cell_id":31,"user_id":0},{"cell_id":32,"user_id":0},
{"cell_id":33,"user_id":0}]]





Теперь как мы делаем,  если нужно показать пирамиду  пользователя, который номер 1 в ней,  мы достаем запись где top_user равен указанному id достаем json данные декодируем их в массив и передаем в класс, который сгенерирует нам нашу пирамидку. 

Единственное, что вижу проблему, как мы думаете:

Если нужно показать пирамиду юзера, который скажем не 1, а где то в центре пирамиды. Тоесть его id мелькает в json данных, как скрипт справиться примерно с такой задачей: 

  - достать все  записи из таблицы Пирамида 
  - открыть циклы, который проходится по каждой записи и достает данные json 
  - еще 1 цикл, который проходится в данных json и ищет нужный id. 

На глаз примерно так:

нужно найти этого юзера (id 54), он где то залез в джейсоне

Код


SELECT * FROM pyramid WHERE status = 1; // получаем, все действующие пирамиды пусть они будут в переменной $data

foreach ($data as $item){ // пройдемся по всем записям 
 
    $item['set'] = json_decode($item['set'] ,true); // декодируем джейсон в массив 
   // массивчик у нас многомерный


   for($i=1; $i<count($item['set'] ); $i++) { // пробираемся по все уровням массива (их 4). 1 уровень это 1 юзер, 2 уровень это 3 юзера, 3 уровень это 9 юзеров и 4 уровень 27 юзеров. (заданице немного поменяли на "троичную пирамиду" ). Поставим даже $i =1 , что бы 1 уровень не проверять. 

       // ну а тут мы бегаем уже по юзерам, которые в уровне 
        for($z=0; $z<count($item['set'][$i]); $z++) {

            if(id нужного нам юзера == $item['set'][$i][$z]['user_id']) {
                     
                   // юзера нашли, ставим метку и выходим из циклов. 
                   break; 
           }

       }


  }
    

}




Конечно это будет функция к примеру если юзер найдет она возвращает id записи, если нет то false. Как думаете, логично будет использовать такой вариант ?   

Автор: Чучмек 4.8.2012, 11:06
Цитата(Fortop @  4.8.2012,  03:17 Найти цитируемый пост)
Кто мешает хранить атрибут сразу вместе с элементом?

Объем данных +50% При неиндексированном статусе замедлится поиск на несколько порядков, при индексированном - еще +50%.
Mеняем tops (количество элементов = количестово пирамид) на индекс (количество элементов=количество пользователей)
Цитата(nepster @  4.8.2012,  03:21 Найти цитируемый пост)
Теперь как мы делаем,  если нужно показать пирамиду  пользователя, который номер 1 в ней,  мы достаем запись где top_user равен указанному id достаем json данные декодируем их в массив и передаем в класс, который сгенерирует нам нашу пирамидку. 

А какой механизм добавления нового пользователя в пирамиду? 

Автор: nepster 4.8.2012, 14:35
об этом я еще не думал, но на вскидку такой: 

 к примеру есть пирамида она заполнена вся кроме последнего юзера. Тоесть на 4 уровне заполнено 26 ячеек из 27. 
 есть пользователь Вася, который хочет пригласить друга. Вот он приглашает друга, друг становится на 27 место. 

 к примеру каждый раз когда мы добавляем юзера, мы проверяем сколько мест осталось. 



Код

if(оставшихся мест == 0) {
         // тут запустим класс, который завершит пирамиду статусом 0
         // создаст еще 3 записи в таблицу pyramid, это и будут наши новые 3 мирамиды. 
         // так же еще 1 скрипт сгенерирует нужной json,  для поля set
}


Добавлено через 41 секунду
на самом деле интересненькое такое заданице. 

Автор: Чучмек 4.8.2012, 14:45
Придется обновить данные всех пользователей составляющих пирамиду, перераспределить их между двумя новыми пирамидами. В моем варианте нужно лишь обновить массив вершин.
  

Автор: nepster 5.8.2012, 00:12
я не понял, а как мы в вашем варианте воспроизведем пирамиду определенного юзера ? 

Автор: Чучмек 5.8.2012, 08:36
Таблица users
Код

+------+----------+
| ind  |  user_id |
+------+----------+ 

ind - индекс в дереве
Получаем индекс пользователя по user_id 
Код

$query='SELECT ind FROM users WHERE user_id='.$user_id; 


Таблица tops
Код

+---------+-------------+
| status  | users_ind   |
+---------+-------------+

status, например, 1 (not_full)- не заполненная пирамида, 0(full) -  заполненная пирамида
Получаем пирамиду  пользователя (вершину) по индексу
Код

if ($list=$ind)
  {
  do
    {
    $ind=($ind-1)>>1;
    $list.=','.$ind;
    }while($ind);
  }
$query='SELECT users_ind FROM tops WHERE status=1 AND  users_ind IN ('.$list.')';


Получаем всех пользователей из пирамиды
Код

$list='ind='.$ind;
for ($n=1;$n<$ncount;$n++)
 {
 $lcount=1 << $n;
 $i0=($ind+1)* $lcount-1;
 $list.=' OR ind BETWEEN '.$i0.' AND '.($i0+$lcount-1);
 }  
$query='SELECT * FROM users WHERE '.$list;

Автор: Fortop 5.8.2012, 09:39
Цитата(Чучмек @  4.8.2012,  11:06 Найти цитируемый пост)
Объем данных +50% При неиндексированном статусе замедлится поиск на несколько порядков, при индексированном - еще +50%.
Mеняем tops (количество элементов = количестово пирамид) на индекс (количество элементов=количество пользователей)

Как ты думаешь, что такое твой второй массив вершин и что в нем окажется?

Автор: Чучмек 5.8.2012, 09:46
Цитата(Fortop @  5.8.2012,  09:39 Найти цитируемый пост)
Как ты думаешь, что такое твой второй массив вершин и что в нем окажется?

Если из него  заполненные  не удалять, а помечать, то (при условии равномерного заполнения дерева) count(tops) * 2^n = count(users) , где n - число уровней в пирамиде.

Автор: nepster 5.8.2012, 14:36
Чучмек


Код

Получаем всех пользователей из пирамидыкод PHP

$list='ind='.$ind;
for ($n=1;$n<$ncount;$n++)
 {
 $lcount=1 << $n;
 $i0=($ind+1)* $lcount-1;
 $list.=' OR ind BETWEEN '.$i0.' AND '.($i0+$lcount-1);
 }  
$query='SELECT * FROM users WHERE '.$list;



Как я понял на выходе мы получим массив со всеми id пользователей для какой-то пирамиды.

Тогда в любом случае нам нужно собрать ее в массив, что бы передать классу, который соберет массив в таблицу и оформит дизайн. 
+ мы можем не восстановить нужный порядок пользователей в пирамиде, и на каком уровне пользователь. 

Автор: Чучмек 5.8.2012, 17:30
Восстанавливаем часть массива users, соответствующую выбранной пирамиде
Код

 $mColInd=array();
 $ColCount=0;
 while ($ColName=@mysql_field_name($result,$ColCount))
  {
  $mColInd[$ColName]=$ColCount++;  
  }
 $users=array();
 while ($mas=mysql_fetch_row($result))               
    {
    $users[$mColInd['ind']]=$users[$mColInd['user_id']];
    }

Получим, например для пирамиды с индексом вершины 4  
Код

Array
(
    [4]  => xxx
    [9]  => xxx
    [10] => xxx
    [19] => xxx
    [20] => xxx
    ...
    ...
)

Далее, если уж так необходимо
Код

$pyramid=array();
reset($users);
$I=key($users);
for ($n=0;$n<$ncount;$n++)
 {
 $pyramid[$n]=array();
 $lcount=1 << $n;
 $i0=($I+1)* $lcount-1;
 for($il=0;$il<$lcount;$il++)
   {
   if (isset($users[$i0+$il]))
       {
       $pyramid[$n][$il]=$users[$i0+$il];
       }
   }
 }  
 

Автор: Fortop 5.8.2012, 23:47
Цитата(Чучмек @  5.8.2012,  09:46 Найти цитируемый пост)
Если из него  заполненные  не удалять

А как вы при удалении собираетесь просматривать историю?

А если не удалять, то в чем разница-то?

Автор: nepster 6.8.2012, 01:21
Еще момент если есть скажем пользователи в 4 уровне 


Array
(
    [1]  => xxx
    [2]  => xxx
    [3] => xxx
    [4] => xxx
    [5] => xxx
    [6] => xxx
    [7] => пусто для новых
    [8] =>  пусто для новых
)

админ может деактивировать юзера скажем 4 и будет 


Array
(
    [1]  => xxx
    [2]  => xxx
    [3] => xxx
    [4] => пусто для новых
    [5] => xxx
    [6] => xxx
    [7] => пусто для новых
    [8] =>  пусто для новых
)


но по заданию нужно в любом случае поместить пустые ячейки в конец. 

Array
(
    [1]  => xxx
    [2]  => xxx
    [3] => xxx
    [4] => xxx
    [5] => xxx
    [6] => пусто для новых
    [7] => пусто для новых
    [8] =>  пусто для новых
)


тоесть порядковые номера немного собьются и походу в любом случае придется перезаписывать пол базы. 

Автор: Fortop 6.8.2012, 03:55
Цитата(nepster @  6.8.2012,  01:21 Найти цитируемый пост)
но по заданию нужно в любом случае поместить пустые ячейки в конец. 

В конец чего?

Т.е. подписанный под одного человека пользователь резко переместится под другого?
Ну не бред ли?

Автор: baldina 6.8.2012, 09:23
Цитата(nepster @  4.8.2012,  03:21 Найти цитируемый пост)
везде должна быть история

что входит в историю? достаточно ли для истории просто уметь строить набор пирамид в хронологическом порядке?

и вообще, какие операции с пирамидами и их элементами должны быть предусмотрены? из длинного разговора выклевываются некие удаления/перемещения пользователей, но всё это пока очень мутно.

nepster, Чучмек, вы уже написали немало кода (мне не очень понятного концептуально), однако один пытается решить задачу, про которую ТС говорит
Цитата(nepster @  4.8.2012,  14:35 Найти цитируемый пост)
об этом я еще не думал


пока задача не будет поставлена конкретно и полностью, все эти разговоры, куски кода и структуры базы имхо лишены смысла.
пока в некоторых местах разговор о задаче имеет противоречия (например на которые указывал Fortop).
в постановку также надо добавить предполагаемые объемы обрабатываемых данных.
 

Автор: Чучмек 6.8.2012, 10:57
Цитата(nepster @  6.8.2012,  01:21 Найти цитируемый пост)
 придется перезаписывать пол базы

Придется перезаписывать данные пользователей одной пирамиды

Цитата(Fortop @  5.8.2012,  23:47 Найти цитируемый пост)
А если не удалять, то в чем разница-то? 


Цитата(Чучмек @  5.8.2012,  09:46 Найти цитируемый пост)
count(tops) * 2^n = count(users)

Пускай 6000000 пользователей и 4 уровня в пирамиде.
Есть разница между дополнительным индексированным полем в таблице на 6*10^6 и таблицей из двух полей 4*10^5 ???
 
Цитата(baldina @  6.8.2012,  09:23 Найти цитируемый пост)
пока задача не будет поставлена конкретно и полностью, все эти разговоры, куски кода и структуры базы имхо лишены смысла

+

Автор: baldina 6.8.2012, 11:39
Цитата(Чучмек @  6.8.2012,  10:57 Найти цитируемый пост)
Есть разница между дополнительным индексированным полем в таблице на 6*10^6 и таблицей из двух полей 4*10^5 ???

неправильно считаете. разница есть, но кроме памяти (весьма нынче дешевой) есть и другие факторы. 
задачу надо, а не "если бы да кабы"

Автор: Fortop 6.8.2012, 12:30
Цитата(Чучмек @  6.8.2012,  10:57 Найти цитируемый пост)
Пускай 6000000 пользователей и 4 уровня в пирамиде.
Есть разница между дополнительным индексированным полем в таблице на 6*10^6 и таблицей из двух полей 4*10^5 ???

Или я что-то упускаю из виду, или  у вас число топов = N/2 (где N - общее число узлов/пользователей в структуре)

У вас 4 уровня для каждого конкретного топа. Но кто сказал что 2,3,4й уровни не могут быть топами в свою очередь для кого-то другого?

Т.е. для 6000000 пользователей у вас будет 3000000 топов.
Вот и вся ваша экономия.

Автор: Чучмек 6.8.2012, 13:09
Цитата(Fortop @  6.8.2012,  12:30 Найти цитируемый пост)
Но кто сказал что 2,3,4й уровни не могут быть топами в свою очередь для кого-то другого?


Цитата(Чучмек @  5.8.2012,  09:46 Найти цитируемый пост)
(при условии равномерного заполнения дерева) 


При равномерном(относительно равномерном) заполнении, активные топы(верхушки еще не  заполненных/не разделенных пирамид)будут находится примерно на одном уровне дерева. В двоичном дереве каждый последующий уровень содержит элементов столько же, сколько все предыдущие.
Число уровней в tops будет на n(число уровней в пирамиде) меньше чем число уровней в users
Отсюда для n=4 разница в 16 раз.
Конечно это крайний случай. Другая крайность - всегда заполняется ТОЛЬКО ОДНА из вновь образующихся пирамид. Тогда count(tops)=count(users) - 2^n

Автор: Чучмек 6.8.2012, 13:25
Кроме того в tops можно хранить информацию не имеющую отношения к конкретному пользователю
Время создания/заполнения пирамиды, историю изменения ее состава.

Автор: nepster 6.8.2012, 16:02
на днях реализую пол задания и все вылажу, для дальнейших дискуссий. Тема интересная =) 

По поводу дерева. тут идет как: 

1 уровень  - это 1 пользователь 
2 уровень -  это 3 пользователя 
3 уровень -  это 9 пользователей 
4 уровень -  это 27 пользователей 

Всего в пирамиде 40 человек. Как только пирамида полностью заполняется, тоесть в ней стоят 40 человек, она делится еще на 3 пирамиды. 
Сама же получает статус 0 и существует только для истории. 


1,2 и 3 уровень они всегда заполнены. На самом первом этапе в самой 1 пирамиде эти 13 человек, как бы спонсоры проекта. Для приглашения существует только 4 уровень. Если 1 пользователь на 1 уровне пригласит кого-то, то приглашенный попадает на 4 уровень, любой  пользователь пирамиды кого-то приглашает, то он попадает на 4 уровень. Тоесть тут нет как бы порядка вложенности и иерархии. Эта иерархия показана только в дизайне, не более. 

Автор: baldina 7.8.2012, 10:32
Цитата(nepster @  6.8.2012,  16:02 Найти цитируемый пост)
Как только пирамида полностью заполняется, тоесть в ней стоят 40 человек, она делится еще на 3 пирамиды. 

кто-то при этом выбывает? кто в какую пирамиду попадает при делении?

Автор: nepster 7.8.2012, 16:24
нет, к примеру нумерация ячеек идет по порядку и при делении первая треть попадает в 1 пирамиду, вторая треть во вторую и третья треть в третью пирамиду. 

Автор: baldina 7.8.2012, 17:11
и при этом нужна история, кто в какой когда был?

Автор: nepster 7.8.2012, 20:29
все верно

Автор: baldina 7.8.2012, 23:17
удаления из пирамиды возможны? а перемещения в другую пирамиду? нужна ли история по этим действиям? если удаления быть могут, возможно ли замещение освободившихся мест и соответствующая история?
до ответа на этот вопрос остаюсь при своём мнении, что наиболее просто и эффективный путь - двоичное дерево в массиве, ибо деление и история воспроизводятся элементарно
Цитата(nepster @  7.8.2012,  16:24 Найти цитируемый пост)
к примеру

если Вы можете манипулировать заданием, подгоните его под удобный способ обработки.
т.е. требования должны быть полными, но минимально возможными

Добавлено через 1 минуту и 53 секунды
каково предполагаемое максимальное число участников пирамиды? какие операции производятся часто, какие изредка?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)