1. Куча / Говнокод #19450

    −148

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    https://habrahabr.ru/post/276673/
    
    Какой-то пыхапист плачет что не может в элементарные алгоритмы. А весь хабр его утешает.
    Ко-ко-ко! Зачем мне дерево в жизни обходить! Мне это не понадобится!
    Куд-кудах! Я фронтэндщик и никогда даже массивы не сортировал. Ку-ка-реку!

    Запостил: nihau, 12 Февраля 2016

    Комментарии (219) RSS

    • а ведь он прав, процентов 90 современных задач не требуют, алгортимов сложнее чем обход массив циклом фор
      Ответить
      • как по мне, если решил задачу - даже если и Г - то уже +1.

        есть разрабы которые умеют проблемы решать. есть разрабы которые из говна конфетки умеют делать. разрабы всякие нужны, разрабы всякие важны. садишь их вместе - и будет тебе щасце.
        Ответить
        • ну тогда пусть этот разраб, который не может решить примитивнейшую задачу, не жалуется на хуевый оклад.
          Ответить
          • > примитивнейшую

            все относительно.

            > не жалуется на хуевый оклад.

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

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

              Не давно столкнулся с таким, продукт продается премии, повышенные оклады менеджерам это же они продают. Продажи софта падают давайте снизим ЗП программистам они делают хуевый продукт его не кто не хочет покупать.
              Вот, что сказать таким людям?
              Ответить
              • нечего говорить. два варианта: в манагеры лезть или работу менять. я лично такие халтуры в принципе избегаю. потому что даже если в манагеры лезть, то нужно слишком много жоп целовать, к чему у меня не только таланта нету, но в добавок я еще имею привычку вещи своими именами называть.
                Ответить
            • >относительно
              Если он не будет уметь складывать 2+2 ты тоже скажешь что всё относительно?
              Ответить
              • не надо перегибать. это не машины - это люди.

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

                а так типично на новичков сваливают дерьмовую работу которую сениоры сами не хотят делать. как нанимают - хотят гениев. но даже если нашли гения - все равно какой тупой байдой мозги атрофируют, а потом жалуются что блин почему то гений какой захерелый.
                Ответить
                • Гений - это относительное. Что бы стать стать действительно мастером своего дела нужно постоянно расти. Если юное дарование понимает что он гений (в смысле чувствует что способен на большее, а не считает себя пупом земли ) то он и сам уйдет из этой говноконторы.
                  И вообще гений отличается от обычного человека тем, что обычный человек довольствуется каким то одним уровнем, а гений идет вверх вечно
                  Ответить
              • Может, умеет, но либо уже давно подобные примеры без калькулятора/компьютера не решал, либо в стрессовой ситуации сбойнул.
                google://ректор+мгу+проценты
                Ответить
    • Math.pow(2, level)


      Aaaaaaa
      Ответить
    • > Ко-ко-ко! Зачем мне дерево в жизни обходить!
      Я не знаю подходящего алгоритма обхода дерева для решения, покажите. Пока что вижу единственный способ:
      1) инициализируем массив нод корневым элементом
      2) соединяем ноды
      3) заполняем новый массив нод детишками старого
      4) новый массив нод пустой? выход
      5) свапаем старый массив с новым
      6) гоуту(2)
      Ответить
      • Ты давай "асимптотически оптимальный", который O(1) по памяти и O(n) по скорости. Иначе не подходишь.
        Ответить
        • 1) асимптотически оптимально инициализируем массив нод корневым элементом
          2) соединяем за O(n) по скорости ноды
          3) заполняем новый массив нод детишками старого, расходуя O(1) по памяти
          4) новый массив нод пустой? асимптотически отптимально выходим жрать элитный доширак, ибо работа явно наша
          5) свапаем старый массив с новым за O(1) по скорости (быстрее ограничения задания!)
          6) гоуту(2)
          Ответить
          • >2) соединяем за O(n) по скорости ноды
            ...
            >6) гоуту(2)

            Количество итераций зависит от N.

            Отптимально выходите с собеседования на улицу.
            Ответить
            • Там O(n) во втором пункте - не от всех подряд нод, а только от текущего слоя. Т.е. весь алгоритм в O(N) влезет.
              Ответить
        • > O(1) по памяти
          Такое ведь только для "дерева-в-массиве"?
          Это, как минимум, уже другой случай (как "массив" и "отсортированный массив").
          Ответить
          • Ну-ка, х..к-х..к и в продакшн. Написал сразу после того, как отправил комментарий, на который отвечаю. Не проверял.
            function Node(child1, child2) {
              this.child1 = child1;
              this.child2 = child2;
              this.prev = null;
              this.next = null;
            }
            
            function processTree(tree) {
              var nodesLists = [];
            
              (function traverse(node, level) {
                if(nodesLists.length < level)
                  nodesLists.push([]);
                nodesLists[level].push(node);
                traverse(node.child1, level + 1);
                traverse(node.child2, level + 1);
              })(tree, 0);
              
              nodesLists.forEach(function(list) {
                for(var i=1; i<list.length-1; ++i) {
                  list[i].prev = list[i-1];
                  list[i].next = list[i+1];
                }
                if(list.length > 1) {
                  list[0].next = list[1];
                  list[list.length-1].prev = list[list.length-2];
                }
              });
            }
            Ответить
            • Годно, классическая ошибка: рекурсия не остановится.
              -    traverse(node.child1, level + 1);
              -    traverse(node.child2, level + 1);
              +    if(node.child1) traverse(node.child1, level + 1);
              +    if(node.child2) traverse(node.child2, level + 1);
              Ответить
            • Если есть рекурсия, то это уже не О(1)
              Ответить
              • У меня O(n) по памяти и по времени. Проверял, что можно быстренько выдавить из себя.
                Ответить
          • Нет, там для исходного дерева O(1) по памяти, и в комментах есть и уже ниже написали. Массив же не нужен если ноды и так список образуют.
            Ответить
      • Я бы как то так сделал. Может говно, но все же

        static public void FillNeighbors(Node root)
                    {
                        AddNeighbors(root, 0, new List<Node>());
                    }
        
                    private static void AddNeighbors(Node currentNode, int i, List<Node> neighbors)
                    {
                        if (neighbors.Count == i)
                        {
                            neighbors.Add(currentNode);
                        }
                        else
                        {
                            neighbors[i].Neighbor = currentNode;
                            neighbors[i] = currentNode;
                        }
                        if (currentNode.Left != null)
                            AddNeighbors(currentNode.Left, i + 1, neighbors);
                        if (currentNode.Right != null)
                            AddNeighbors(currentNode.Right, i + 1, neighbors);
                    }
        Ответить
        • O(высота) по памяти? Красота. Кратко и ясно.
          Ответить
          • ну или как то так без доп массива

            .           static void FillNeighbors2(Node currentNode)
                        {
                            Node nextIterStart, currentChild ;
                            // ищем первую ноду на след уровне
                            while (currentNode != null)
                            {
                                if (currentNode.Left != null)
                                {
                                    nextIterStart = currentNode.Left;
                                    break;
                                }
            
                                if (currentNode.Right != null)
                                {
                                    nextIterStart = currentNode.Right;
                                    currentNode = currentNode.Neighbor;
                                    break;
                                }
            
                                currentNode = currentNode.Neighbor;
                            }
                            //Если ее нет = давай, дасвиданья
                            if (nextIterStart == null) return;
            
                            currentChild = nextIterStart;
                            // иначе - идем и цепляем в змейку все ноды не следующем уровне
                            while (currentNode != null)
                            {
                                if (currentNode.Left != null)
                                {
                                    currentChild.Neighbor = currentNode.Left;
                                    currentChild = currentNode.Left;
                                }
            
                                if (currentNode.Right != null)
                                {
                                    currentChild.Neighbor = currentNode.Right;
                                    currentChild = currentNode.Right;
                                }
            
                                currentNode = currentNode.Neighbor;
                            }
                            // и в глубь
                            FillNeighbors2(nextIterStart);
                        }
            Ответить
            • Можно ещё оба цикла совместить. Типа
              if (nextIterStart)
                  nextIterStart = currentChild;
              Ответить
              • ну это будет не так наглядно, и куча лишних ифов не радует

                Хотя ифов тут и так выше крыши
                Ответить
                • Используй функции, Люк...
                  void LinkNode(Node node, ref Node head, ref Node tail) {
                      if (node == null)
                          return;
                      node.Neighbor = null;
                      if (head == null)
                          head = node;
                      else
                          tail.Neighbor = node;
                      tail = node;
                  }
                  
                  void LinkTree(Node root) {
                      root.Neighbor = null;
                      Node nextLayerHead = root;
                      Node nextLayerTail = root;
                      while (nextLayerHead != null) {
                          Node current = nextLayerHead;
                          nextLayerHead = null;
                          nextLayerTail = null;
                          while (current != null) {
                              LinkNode(current.Left, nextLayerHead, nextLayerTail);
                              LinkNode(current.Right, nextLayerHead, nextLayerTail);
                              current = current.Neighbor;
                          }
                      }
                  }
                  P.S. Сейчас меня сишкоблядью обзовут, за такой то код в LinkNode...
                  Ответить
                  • Ну это не самое страшное

                    при вызове тоже нужно ref писать

                    LinkNode(current.Left, ref nextLayerHead, ref nextLayerTail);


                    Что бы программист всегда был предупрежден && вооружен
                    Ответить
                    • > при вызове тоже нужно ref писать
                      И это хорошо.

                      P.S. Не заманивай меня на этот ваш c#
                      Ответить
                      • Да, я тоже так думаю
                        Ответить
                      • С# не мой, я только код разместил

                        Да я скорее для себя решить пытаюсь, нужны мне плюсы или шарпа достаточно
                        Ответить
                        • Дались тебе эти плюсы? Лучше какой-нибудь питон выучи для быстро-грязно-поскриптовать и няшную сишку для лоу-левел.
                          Ответить
                          • дваждую за си. зачем тебе шаблоноебля?
                            Ответить
                          • А чистая сися катируется? В смысле если пойти работать на си то по любому там будут плюсы и все 33 удовольствия с ними связаные

                            Почему питоныч из скриптовых, а не экма например?
                            Ответить
                            • > а не экма
                              Потому что с экмой тебя затянет в веб. А ты же этого не хочешь?

                              > по любому там будут плюсы
                              Не факт. Но часто - да, странный кентавр под названием C/C++, которым так любят хвастаться в резюме...
                              Ответить
                  • Ответить
                  • > Используй функции, Люк...

                    Кмк, тут и без функций прекрасно можно обойтись. Мой вариант:
                    // http://ideone.com/cMFkBF
                    template <typename T>
                    struct Node {
                        T value;
                        Node<T> *left, *right, *next_sibling;
                    };
                    
                    template <typename T>
                    void link_siblings(Node<T> *root) {
                        //   * -> * <upper
                        // /   \
                        // * -> * <lower
                        // ^ level_start
                        Node<T> *upper = root, *lower = nullptr, *level_start = nullptr;
                        while (upper) {
                            Node<T> *children[2] = {upper->left, upper->right};
                            for (auto child : children) {
                                if (child) {
                                    if (lower) lower->next_sibling = child;
                                    else       level_start         = child;
                                    lower = child;
                                }
                            }
                    
                            if (upper->next_sibling) {
                                upper = upper->next_sibling;
                            } else {
                                upper = level_start;
                                level_start = lower = nullptr;
                            }
                        }
                    };
                    Ответить
                    • Ну да. В общем-то и в старых крестах будет работать...
                      for (int i = 0; i < 2; ++i) {
                          Node<T> *child = i == 0 ? upper->left : upper->right;
                          // ...
                      }
                      Ответить
      • > покажите

        Специально сходил проверил - его уже в комментах написали. На самом деле это классическая задачка для унылых индусособесов, таких на geeksforgeeks.com полно.
        https://habrahabr.ru/post/276673/#comment_8765101
        http://www.geeksforgeeks.org/connect-nodes-at-same-level-with-o1-extra-space/
        Ответить
        • спасибо, поразглядываю
          вроде, мысль понятна - использовать созданный список слоя сверху для продвижения по слою снизу, если я правильно понял идею алгоритма
          Ответить
        • Боже, какой лютый трешак в этом коде на geeks-4-geeks...
          Ответить
          • Да, пиздец еще тот. Проще самому написать. А может на то и расчет?
            Устранить конкурентов, выложив такой вот код
            Ответить
          • > Боже, какой лютый трешак в этом коде на geeks-4-geeks...

            Код на сишке/плюсах там лучше вообще не смотреть. Зато можно почерпнуть интересные идеи для решения задач на собесах. Всегда лучше писать код самому. В целях подготовки к собесам - на бумажке.

            P.S. Я тут года два назад читал API Design for C++, ужаснулся, как книжку с таким кодом вообще в печать выпустили. Дословно не помню, было что-то вроде
            Stack<int> *stack = new Stack<int>;
            if (stack) {
                // do something with stack
                delete stack;
            }
            Ответить
            • > Stack<int> *stack = new Stack<int>;
              Книгу писал джавист?

              Хотя... судя по if (stack) и delete stack - походу сишник, который даже не знал, что new не вернётся при недостатке памяти...
              Ответить
              • Может и крестовик, но в тёмное достандартное время, когда исключений не было, а new работал как new (nothrow).
                Ответить
    • Это пиздец, слов нет. Какой-то цирк уродов.
      Ответить
    • Давайте реализацию fizzbuzz что ли обсудим.
      Ответить
      • Это просто задание нетворческое какое-то, вот ровно 100 говнокодов назад было тоже задание в принципе на деревья, а стонов было меньше: http://govnokod.ru/19350
        Ответить
    • Лол, без ИДЕ жить не может.
      Ответить
    • void LinkTreeWithoutNils (Node* node)
      {
        if (!node) 
          return;
        Node *left = node->left, *right = node->right;
        LinkTreeWithoutNils(left);
        LinkTreeWithoutNils(right);
        while (left)
        {
          left->next = right;
          left = left->right;
          if (right) right = right->left;
        }    
      }
      
      void LinkTree (Node* node)
      {
        LinkTreeWithoutNils(node);  
        Node* right = node;
        while (right)
        {
          right->next = null_ptr;
          right = right->right;
        }
      }
      Ответить
      • как ты написал это без интеллисенса? а как же живая компиляция? а как ты рефакторишь без иде?
        Ответить
        • Да я динозавр кокойта походу.
          Однажды на собеседовании меня спосили, какие паттерны я знаю. Я сказал, что надо ПИСАТЬ КОД БЛЕАТЬ, а не забивать голову паттернами. Собеседование продлилось минут 10 от силы. Меня не взяли.
          Думаю, ТС с хабра знает много паттернов и прочих красивых слов.
          Ответить
          • >> Думаю, ТС с хабра знает много паттернов и прочих красивых слов.

            так сейчас универы таких и готовят. Много умных слов, всяких терминов, особого видения проблемы. А обычный алгоритм закодить - ну не царское это дело.

            помню однокурсник в универе на полном серьезе спорил со мной на тему - "нахуя писать все эти сортировки, рандомизаторы и длинную арифметику если они уже давно в стандартных либах есть?"
            Ответить
            • пехепешнику вот и не надо. Я как похепешник это заявляю.
              Ответить
            • И действительно, нахуя? Более того, прикладнику в массе реализовывать свои структуры данных противопоказано, надо лишь знать как она устроена чтобы помнить классы сложности.
              Ответить
              • +1. Даже системщикам противопоказано.
                Ответить
                • Вспоминаю дос винды флудом рендомными мак адресами, там наверняка хуйня вроде обычного списка была.
                  Ответить
                  • Да там и сам ARP протокол дизайнили в расчёте на добрых и пушистых соседей... Никто ж не думал, что в локалке крыса заведётся. Он дырявый как решето, даже если реализация нормальная (см. ARP spoofing).

                    А источник кривых пакетов найти весьма сложно (сетевухи вполне спокойно отправляют любой треш, не обязательно со своим MAC'ом). Приходится порты по одному отключать, а если коммутатор дешёвый - так вообще бегать и дёргать кабели...
                    Ответить
                    • Какие-то фиксы на ARP poisoning вообще есть? В эпоху wifi это еще актуальнее.

                      Это, конечно, не ответ на вопрос "а почему вы взяли хуйню вместо структуры данных". Видимо, когда это все разрабатывалось, вопрос it безопасности мало кого ебал.

                      Кстати, а когда ms уже похоронит (NT)LM?
                      Ответить
                      • > фиксы на ARP poisoning
                        Емнип, только включать DHCP и покупать коммутатор подороже, с соотв. защитой. На самих компах не лечится. Со статическими айпишками тоже не лечится.

                        > не ответ на вопрос "а почему вы взяли хуйню вместо структуры данных"
                        Ну работало же, если целенаправленной атаки нету ;)
                        Ответить
                        • А на wifi точках?

                          2. Видимо, когда это разрабатывалось, структуры себе писал каждый сам.
                          Ответить
                          • > А на wifi точках?
                            Надо конкретные железки смотреть, если ты про свою сеть. Ну и не пускать туда кого попало.

                            Ну а паблик вайфай в кафешках и прочих местах лучше по-дефолту считать скомпрометированным...
                            Ответить
                            • А если паблик с ms vpn, как в немецких вузах?
                              Ответить
                              • ms vpn это PPTP поверх вафли? Ну в теории норм, ты же напрямую тогда с локалкой не общаешься, только с VPN сервером. Ну это если подлинность сервера как-то проверяется ;) Потому что сервер тебе точно так же могут спуфнуть или вообще левую точку доступа поднять...
                                Ответить
                                • >Ну это если подлинность сервера как-то проверяется ;)
                                  Там еще аутентификация challenge-response, ловишь - и сразу можно брутать. В крайнем случае митмом.
                                  Ответить
                • Вы таки предлагаете вообще лабораторные взять и отменить?
                  Ответить
      • http://ideone.com/sjwxOz

        У ноды с val = 1 некорректно линк проставил. Перепиливай :)
        Ответить
        • оуч,
          left = left->right ? left->right : left->left;
          Ответить
          • http://ideone.com/Mm0I70
            Ответить
            • ну кароч правого так же
              Ответить
              • Ну да, вечером ещё подумаю.
                Ответить
                • Да можно слева в другой подветке висячий узел сделать, короче тогда будет жопа, без доп памяти O(высота) уже нельзя будет ничё расставить.
                  Ответить
                  • Ну можно ещё попытаться выбираться из таких тупиков через верх, но это всю сложность запорет, т.к. будет пробегаться по всему полудереву....

                    Короче из рабочих вариантов, походу, остаётся только поиск в ширину, который выше написан.
                    Ответить
                  • Кстати, а если рекурсивный вызов будет возвращать самый правый элемент на обработанном им уровне?

                    P.S. А не, тож не вариант, нам же все уровни надо пролинковать, а не только верхний.
                    Ответить
      • Чет твое решение заставило меня задуматься и написать свое.
        static void Snakify()
        {
            root.Next = root.Left;
            Link(root);
        }
        
        static void Link(Node n)
        {
            if (n == null)
                return;
        
            if (n.Left != null)
                n.Left.Next = n.Right;
        
            if (n.Right != null)
                n.Right.Next = n.Next.Left;
        
            Link(n.Left);
            Link(n.Right);
        }
        Ответить
        • Дерево неполное может быть. Вот посмотри на мой пример комментом выше. Там как раз у ноды 4 нет правого линка. Что твой код в этом случае сделает?
          Ответить
          • http://ideone.com/tmfRgt

            Console.Write("\r\n");

            мне было очень лень жать ctrl+space в своей теплой и ламповой VS

            Когда уже урлы запилят?!
            Ответить
            • Не работает твой код, иди чисти: http://ideone.com/dua3Zl

              P.S. "ну тогда пусть этот разраб, который не может решить примитивнейшую задачу, не жалуется на хуевый оклад"
              Ответить
              • >который не может решить примитивнейшую
                А главное не нужную, для пыхаря - уж точно, задачу
                Ответить
              • Знатный обосрамс вышел. Пойду попрошу начальника урезать мне з\п.
                Ответить
    • По-моему, тут все элементарно: рекурсивно обходим дерево, в функцию передаем уровень в дереве, а дальше делаем nodes[level].append(node), нужно только, чтобы дерево обходилось слева направо. Все это будет за O(количество узлов)

      И да, под стрессом вполне можно начать городить какую-то хуйню.
      Ответить
      • Можно и так, вообще обычно просят сделать без создания доп массива
        Ответить
        • Ну это уже приебки какие-то. И в задаче этого кстати нет. А как без массива делать связи между узлами без общего родительского узла?
          Ответить
        • И кстати "рекурсия" и "без внешней памяти" как-то не сочетается, смысл в чем?
          Ответить
          • Там можно сделать и без рекурсии и без внешней памяти. См. мой код где-то вверху.

            Нахуя - это уже другой вопрос. Меня бы и твоё решение за O(N) по памяти и асимптотическое O(N) по времени устроило. По крайней мере, его написать и проверить легко.
            Ответить
            • За O(сколько)?

              Один я разучился читать что-то сложнее форича?
              Ответить
              • Ты про мой код? O(1) по памяти, O(N) по времени.
                Ответить
            • >> Меня бы и твоё решение за O(N) по памяти и асимптотическое O(N) по времени устроило.

              Имхо достаточно убедиться что у человека есть мозг и он работает. По идее хватило бы и словесного описания работы алгоритма
              Ответить
            • Почему асимптотическое O(N) по времени, там ровно O(N) в любом случае.
              Ответить
              • Потому что ты заранее не знаешь, сколько у тебя уровней/нод на уровне. Массивы/хешмапы будут реаллочиться, поэтому асимптотическое.
                Ответить
                • Эта дурацкая запись с N. Выше http://govnokod.ru/19450#comment313133 писал - будет за O(количество узлов)
                  Ответить
                  • > nodes[level].append(node)

                    nodes[level] - вот это растягиваться будет, т.к. ты не знаешь сколько у тебя уровней
                    .append(node) - и вот это тоже будет растягиваться. Или там связные списки?

                    Поэтому по времени выйдет асимптотическое O(количество узлов).
                    Ответить
                    • Эта строка выполнится (количество узлов) раз, и?
                      Ответить
                      • И при этом несколько раз сработает реаллок, блджад.

                        P.S. Или я гоню про асимптотику...
                        P.P.S. Амортизированное, слова спутал.
                        Ответить
                        • Ну worst case у списка (2 или 3) * len, так что не страшно, но 1 конечно же лучше. Другое дело что так ебаться из-за разовой задачи нельзя, но это никого не ебет :)
                          Ответить
                      • так ты не знаешь сколько слоев, его реалочить будет
                        Ответить
                        • Ну вот тут хуй знает, я тупить чё-то начал. При вставке в тот же хешмап у нас на каждую вставку амортизированное O(1) (т.к. во время каких-то вставок будет реаллок/рехеш). Но вот если я вставляю туда N элементов, то амортизированное O(N) или просто O(N)?
                          Ответить
                          • Ты тупишь, да. Причем тут хешмеп, и nodes, и содержимое - arraylist, хотя если nodes сделать хешмепом, то вероятность рехеша от ключей - подряд идущих целых крайне мала.
                            Ответить
                            • > arraylist
                              Ну он тоже изредка реаллокаться будет, т.к. длина изначально неизвестна. Или там не один сплошной блок, а список из страничек, как в крестоблядском std::deque?
                              Ответить
                              • в шарпе - сплошной.
                                Ответить
                              • В жавке он увеличивается в 2 раза, поэтому я и написал, макс. расход памяти - 2*len, при этом 3 *len записей (для len = граница ресайза + 1)
                                Ответить
                                • Да я ж не про расход памяти говорю, а про время. Ну по времени тоже раза в 2 и выйдет, т.к. растёт вдвое. Т.е. ок, можно считать, что O(количества узлов). А амортизированность всё-таки к отдельным вставкам относится, а не к задаче в целом...
                                  Ответить
                                  • Имхо слово "амортизированное" или еще какое-то лишнее, т.к. у тебя все равно не меняется класс сложности.
                                    Ответить
                                • (oldCapacity * 3) / 2 + 1.
                                  Ответить
                                • И снова неправда. 2* (len-1) памяти и 2*len - 1 операций для len = граница ресайза + 1
                                  Ответить
                          • По идее - просто O(N)
                            Ответить
      • Ну, кто-нибудь, прокомментируйте мой алгоритм.
        Ответить
      • Можно оптимизировать до O(количество уровней) - хранить для каждого уровня только последний встретившийся узел, но и первое пришедшее в голову тоже не так уж и плохо.
        Ответить
        • Ну. Остаётся ещё чуть-чуть оптимизнуть - поюзать поиск в ширину. Тогда тебе нужно будет только 2 уровня - текущий и следующий. И получится за O(1) по памяти.
          Ответить
          • Ахах, да, действительно. Ты так и написал? Я этот высер http://govnokod.ru/19450#comment312962 тупо осилить не могу http://govnokod.ru/19450#comment313172
            Ответить
            • > Ты так и написал?
              Ну у меня там ещё рекурсия выкинута (код бежит по уже построенному слою когда строит следующий).
              Ответить
              • Все хорошо и экономно, но не читаемо нихуя.
                Ответить
                • Ну.
                  Ответить
                • хм. Вполне читаемо. Для меня
                  Ответить
                  • Ну я бы на ревью не пропустил.
                    Ответить
                    • почему?
                      Ответить
                      • Комментов к функциям нету, инвариант (tail != null) == (head != null) из кода не очевиден (это у вас в шарпиках NPE кинется, а на сишке/крестах, особенно без операционки и защиты памяти, это может закончится очень грустно)...
                        Ответить
                        • Ну комменты - дело пары минут.

                          Вообще мне код показался годным. Для шарпа. С точки зрения плюсов оценить не могу
                          Ответить
                          • > показался
                            Креститься надо.
                            Ответить
                            • В крестах он не годный?
                              Ответить
                              • Не особо. head проверен на null, а tail - нет. Из кода первой функции не очевидно, почему tail не может быть null при head != null. В итоге приходится изучать обе функции одновременно. А это трудно и вообще не айс.
                                Ответить
                                • >Вообще мне код показался годным.
                                  >Креститься надо.
                                  >В крестах он не годный?
                                  Ответить
                  • http://govnokod.ru/19450#comment313172
                    Ответить
    • bintree([Left, Val, Right], bt(Left1, Val, Right1)) :-
          bintree(Left, Left1), bintree(Right, Right1).
      bintree(Val, bt(Val)).
      
      %%         1            -------------- Level 0
      %%       /    \
      %%     2        3       -------------- Level 1
      %%    / \      /  \
      %%   4   5    6    7    -------------- Level 2
      %%  / \           / \
      %% 8   9        10   11 -------------- Level 3
      
      nodes([[[8, 4, 9], 2, 5], 1, [6, 3, [10, 7, 11]]]).
      
      build_tree(Tree) :- nodes(Nodes), bintree(Nodes, Tree).
      
      %% ?- build_tree(X).
      %% X = bt(bt(bt(bt(8), 4, bt(9)), 2, bt(5)), 1, bt(bt(6), 3, bt(bt(10), 7, bt(11))))


      Или я чего-то не понял?
      Ответить
      • А теперь переведи свынячу мову на нормальный язык.
        Ответить
        • двійковедерево([Лівий, Кількість, Правий], дд(Лівий1, Кількість, Правий1)) :-
              двійковедерево(Лівий, Лівий1), двійковедерево(Правий, Правий1).
          двійковедерево(Кількість, дд(Кількість)).
          
          %%         1            -------------- Рівень 0
          %%       /    \
          %%     2        3       -------------- Рівень 1
          %%    / \      /  \
          %%   4   5    6    7    -------------- Рівень 2
          %%  / \           / \
          %% 8   9        10   11 -------------- Рівень 3
          
          вузли([[[8, 4, 9], 2, 5], 1, [6, 3, [10, 7, 11]]]).
          
          посадити_дерево(Дерево) :- вузли(Вузли), двійковедерево(Вузли, Дерево).
          
          %% ?- посадити_дерево(Х).
          %% Х = дд(дд(дд(дд(8), 4, дд(9)), 2, дд(5)), 1, дд(дд(6), 3, дд(дд(10), 7, дд(11))))
          Ответить
          • Что такое ведерево? Bintree это корзинадерево, кстати.

            Перескажи своими словами пост.
            Ответить
            • >> Bintree это корзинадерево, кстати.

              Скорее бинарное дерево
              Ответить
            • > Что такое ведерево?

              Хотел сначала написать «бінарне дерево», потом решил применить славянский термин.

              > Перескажи своими словами пост.

              Статья со звёздочкой в помощь:
              https://de.wikipedia.org/wiki/Prolog_(Programmiersprache)

              А теперь своими словами.

              Программа описывает четыре факта.

              Факт №1:
              Условие bintree с парой аргументов [Left, Val, Right] и bt(Left1, Val, Right1)) выполняется, если выполняется условие bintree с парой аргументов Left и Left1 и при этом выполняется условие bintree с парой аргументов Right и Right1.

              Факт №2:
              Условие bintree с парой аргументов Val и bt(Val) истинно.

              Факт №3:
              Условие nodes выполняется, когда его аргумент равен [[[8, 4, 9], 2, 5], 1, [6, 3, [10, 7, 11]]].

              Факт №4:
              Условие build_tree с аргументом Tree выполняется, если выполнено условие nodes с аргументом Nodes и выполнено условие bintree с парой аргументов Nodes и Tree.

              Требуется: найти аргумент, удовлетворяющий build_tree.

              *****

              Разбор задачи.

              Последние два факта можно сократить до одного:
              build_tree(Tree) :- bintree([[[8, 4, 9], 2, 5], 1, [6, 3, [10, 7, 11]]], Tree).


              Что такое bt, я не знаю.
              Ответить
              • Ух ты, умничка, дал ссылку на немецкую педию. Я правда один хер на русском читаю, если конечно статья не полное днище. И нахуй мне этот пролог в 16м году?

                >потом решил применить славянский термин.
                И по-украински эот будет двiйкове?
                Ответить
                • https://goo.gl/XbhnU8
                  https://goo.gl/tmZdqR
                  Ответить
                • Я дал ссылку на ту статью, которая со звёздочкой. С жёлтой звёздочкой статья на нидерландском языке, её лучше не упоминать во избежание политических срачей. Думаю, серая звёздочка тоже сойдёт.

                  > И нахуй мне этот пролог в 16м году?

                  Я вообще не умею писать на декларативных ЯП. Но это же не означает, что декларативные ЯП не нужны?

                  > И по-украински эот будет двiйкове?

                  https://uk.wikipedia.org/wiki/Двійкова_система_числення

                  https://uk.wikipedia.org/wiki/Двійкове_дерево
                  Ответить
                  • Ну значит не зря минула меня чаша сия (обучение на мове) :)
                    Ответить
                  • Ты и по-немецки не умеешь читать, но это не значит что немецкий не нужен? Давай я на немецком буду писать? Мысль ясна?
                    Ответить
      • > Или я чего-то не понял?
        True. Прежде, чем писать код, обычно нужно как следует разобраться в задаче.
        Ответить
      • www, где ты раскопал пролог? Тебе его при совке преподдавали?
        Ответить
        • Ну у нас в институте был...
          Ответить
          • govnotify?

            Я же заводил тред про ращкаобразование, что ж ты тогда молчал. И нах он нужен? Или пережиток СССР?
            Ответить
            • Ну как минимум - для развития головного моска
              Ответить
              • И чем он лучше какого-нибудь пхп или питона?
                Ответить
                • Он ближе к SQL, чем к перечисленной тобой императивщине.
                  Ответить
                  • >чем лучше
                    Ответить
                    • Он не лучше. Он другой
                      Ответить
                      • Что он такого даст что мне пригодится и что нельзя с большей пользой заменить чем-то другим? Блин,все тебе приходится расписывать.
                        Ответить
                        • Когда на завод привезли новые фигурные стамески Семен долго не мог понять для чего они нужны. Он прочитал инструкцию и пытался наблюдать за работой других мастеров, но не мог ничего понять. Казалось весь мир сошел с ума. В порыве отчаяния Семен лизнул фигурную стамеску, и тут же порезал язык о острое лезвие. Это стало последней каплей
                          - Петрович, что за дела? Зачем нам эти новые кривые стамески? - спросит он у начальника цеха после очередной утренней пятиминутки
                          - Семен, сколько можно! Новые станки тебе ненравятся, заготовки из красного дерева тебе ненравятся, техника безопасности тебе ненравится! Тебе хоть что нибудь нравится?
                          Семен поступил взгляд. Он чувствовал себя смущенным и виноватым, но ничего не мог с собой поделать.
                          - вот чем они лучше обычных плоских? Я всегда только плоскую...
                          - тьфу ты ну ты! - воскликнул в сердцах Петрович и зашагал прочь
                          Ответить
                          • Дай угадаю, семен - это преподы в рашке, новые стамески - это жава с питоном, а старые - это паскаль, пролог и прочая хуйня? А где же ты? А ты - лишь тупой ретранслятор того, что в тебя вдолбили преподы. Ты закончил или еще учишься, я забыл?
                            Ответить
                        • Чем SQL лучше питона? Чем CSS лучше жавы?

                          Если на пальцах - пролог это что-то типа базы данных, в которой ты записываешь факты и правила, по которым из них можно вывести новые. А потом можешь задавать ему вопрос, а он пытается построить ответ на основе тех самых фактов.

                          Какую это пользу принесет конкретно тебе - думай сам. Скорее всего никакую, т.к. реляционок хватит.
                          Ответить
                          • Чем prolog полезнее питона? А если его изучение не окупается, то пусть господин www перестанет говорить на свынячей мове и перейдет на понятный другим язык.
                            Ответить
                            • Есть две крайние доктрины программирования: императивная и декларативная.

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

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

                              Теоретически ты можешь перевести программу с декларативного ЯП (типа Пролога) на императивный (типа Си), но для этого понадобятся услуги математика. Приходится выбирать, ебаться самому с математическими выводами (чтобы получить программу на императивном языке) или доверить их машине (тупо вбив условия исходной задачи на декларативном языке).
                              Ответить
                            • > Зачем нужен Пролог?
                              - Пролог описывает логические формулы, и хорошо подходит для описания отношений и ограничений. Например, на нем можно легко выразить задачи из психотестов типа "У Васи есть питбуль, Сема живет в желтом доме, Петя живет справа от Васи, а у Петиной бабушки на окнах занавески" и т.д.
                              - Пролог не только лучше это может выразить чем, например, Питон, но в нем еще есть и инструменты для решения таких задач.

                              > Чем Пролог лучше Питона
                              - У Пролога более гибкий синтаксис (программист может вводить новые синтаксические конструкции).
                              - В Прологе меньше встроенных сущностей (т.е. язык сам по-себе меньше).
                              - В Прологе проще семантика (за очень редким исключением, программы не используют изменяемое состояние).
                              - Практически все реализации Пролога компилируются либо в натив, либо в оптимизированый байткод.

                              > Чем Пролог хуже Питона
                              - Нету стандартной хеш-таблицы и массива.
                              - Мало библиотек и мало пользователей.

                              > Чем Пролог хуже других
                              - Инструменты разработки не на высоте.
                              - Пролог не очень подходит для описания многопоточности / многозадачности.
                              Ответить
                              • А ещё пролог может просто зависнуть даже на корректной программе.

                                В общем, забавный язычок для написания брутфорсов.

                                Интересно, у меня одного бомбит от того, что в SWI-шелле можно только вопросы задавать, факты добавлять нельзя?
                                Ответить
                                • > А ещё пролог может просто зависнуть даже на корректной программе.
                                  Это все могут.
                                  Делал как то обход файлов на пхп в одном из каталогов наткнулся на линк на каталог выше уровнем.
                                  Ответить
                                  • > на линк на каталог выше уровнем.

                                    Программа не корректная, раз не проверяет такие вещи.
                                    Ответить
                                • Ну это как бы особенность Тьюринг-полных языков. Тут как бы ничего не поделать.
                                  SWI как бы хорошая реализация с одной стороны (вотличие от ГНУ Пролог), но чем-то же коммерческие реализации должны быть лучше, если они существуют. Сикстус может быть не зависает, там где не нужно?
                                  В SWI можно добавлять факты в шелле, эту возможность у пролога отобрать нельзя (ну, по крайней мере у стандарнтых реализаций). Просто нужно не сам-по себе факт писать а asssert(Term).
                                  Ответить
                                • > брутфорсов
                                  Угу. А какие-нибудь оптимизации и индексы в современные прологи завезли? Или всё тот же тупой поиск в глубину, как в старом добром турбо прологе?
                                  Ответить
                                  • Это SAT в смысле? Ну как бы это зона очень активного поиска быстрых алгоритмов. Это же первая проблема на которой продемонстрировали NP-complete класс. Естесственно, что тут исследование очень серьезное...
                                    Ответить
                              • >- Нету стандартной хеш-таблицы и массива.
                                >- Мало библиотек и мало пользователей.
                                Подумаешь, недостатки.
                                Ответить
                                • Упор на "стандартные". Массивы и хеш-таблицы есть, но они не описаны в стандарте.
                                  В ПХП например, нет массивов. В ж.скрипте - тоже нет, в Луа - тоже, но это не особенно им мешает. В Сишке нет хеш-таблиц, и опять же.
                                  В Питоне есть массивы, но никто ими не пользуется.
                                  Ответить
                                  • Стандартные = искоробочные? Подумаешь, основные структуры данных.

                                    У тебя нету ни массивов ни хешмепов. В луа и рнр одно заменяет другое.

                                    > В Сишке нет хеш-таблиц, и опять же.
                                    А сишку кроме как для системного программирования мало кто юзает.

                                    >В Питоне есть массивы, но никто ими не пользуется.
                                    Есть списки и кортежи, они заменяют массивы, ими очень часто пользуются.
                                    Ответить
                                    • Нет, стандартные = описаные в стандарте. Это значит, что если я сейчас воспользуюсь хеш-таблицой из реализации в SWI, то в реализации GNU Prolog таких предикатов может не быть (и скорее всего не будет). Это как многопоточность в Си: в стандарте нет примитивов многопоточности, и поэтому код написаный с использованием, например pthreads не запустится на Виндовсе.

                                      А почему ты решил, что хеш-таблицы не нужны в системном программировании? Очень даже нужны, и поэтму в Си есть 100500 самодельных реализаций хеш-таблиц: http://stackoverflow.com/questions/1138742.

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

                                      Про Луа и ПХП я не понял, расшифруй, чего у меня нету?
                                      Ответить
                                      • Про pthreads зря. Если речь о библиотеке, то её портировали уже подо всё, даже под DOS.
                                        Ответить
                                        • Даже под джаву :) У неё мониторы прям как в птредах.
                                          Ответить
                                          • Если у нее такие же мониторы то это обязан быть pthreads? Напоминает высеры о том что Powershell слизан с баша из-за команды ls.
                                            Ответить
                                          • > У неё мониторы прям как в птредах.

                                            Я вот чего не могу понять: в питредах принято сигнались в condvar после того, как отпустил мутекс, и в целом понятно, почему.
                                            А вот почему в жабе надо обжект.нотифаить с зохваченным монитором?
                                            Ответить
                                            • > с зохваченным монитором
                                              Да поди очередь ожидающих тредов защищена только самим монитором.
                                              Ответить
                                            • Ну и для передачи владения вроде как логичнее - notify вызывается под мутексом, а wait возвращается под ним. Можно не захватывать мутекс заново...
                                              Ответить
                                              • псевдокод есть? не понял идею
                                                Ответить
                                                • Да я гоню... The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object.
                                                  Ответить
                                      • >Очень даже нужны, и поэтму в Си есть 100500 самодельных реализаций хеш-таблиц
                                        Если бы они так нужны - в нормальном языке были бы стандартные. Но си древний как гавно мамонта и юзается в основном для системного программирования, ему можно простить (а треды - околосистемная вещь), а пролог вроде ЯВУ же?

                                        В луа и пхп есть гибрид списка и хешмепа, ты не в курсе был?
                                        Ответить
                                  • > В Сишке нет хеш-таблиц

                                    В сишке нет языкового механизма для объявления параметризованных типов контейнеров, потому и универсальных хэш-таблиц вы там не найдёте.

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

                                    "Стандартная" сишная хэш-таблица, которая бы устроила почти всех, просто не может существовать.

                                    В C++ такое вполне возможно благодаря шаблонам.
                                    #include <unordered_map>
                                    Ответить
                                    • >У разных сишкопроектов совершенно разные требования к производительности, разные стратегии выделения памяти, и куча других нюансов.

                                      >"Стандартная" сишная хэш-таблица, которая бы устроила почти всех, просто не может существовать.

                                      >В C++ такое вполне возможно благодаря шаблонам.


                                      Нет, невозможно. http://stolyarov.info/guestbook#comment-606

                                      Структуры данных не бывают универсальными, за исключением самых простых (массивов и списков), но использование контейнеров для массивов и списков заведомо бессмысленно — за более чем сомнительный выигрыш во времени кодирования мы при этом вынуждены расплачиваться феерическими приключениями во время отладки и сопровождения, причём ставки там приблизительно неделя (проигрыша) за пять минут (экономии); ну а более сложные структуры данных должны, естественно, проектироваться под каждую конкретную задачу (не под проект, а именно под каждую возникающую задачу), и generic они быть не могут — как следствие, ни о каком применении шаблонов при построении сложных (проблемно-ориентированных) структур данных не может быть никакой речи.

                                      Плюсы - говно!
                                      Ответить
                                      • Мммм, какая жирнота, я вздрочнул немного даже.
                                        Ответить
            • > Или пережиток СССР?

              Ты, наверное, не знаешь немецкий или поленился прочитать статью. Пролог изобретён французом.
              Ответить
              • Все проще. Он пидар.
                Ответить
              • Поленился, вы же объяснили, нахуй сегодня нужен пролог. А причем тут немецкий, когда у вас до сих пор практически нет нормального IT образования?
                Ответить
                • >не объяснили
                  фикс
                  Ответить
                  • Выше я объяснил, для чего нужны декларативные языки. Требуется ещё и объяснить, для чего нужен конкретно Пролог и чем он лучше других декларативных ЯП?
                    Ответить
                    • Ты не объяснил как для меня окупится его изучение.
                      Ответить
                      • У некоторых и затраты на высшее образование не окупаются, поэтому ничего гарантировать нельзя.
                        Ответить
                        • Ну приведи примеры тех, для кого изучение пролога окупилось, ёпта. Желательно хотя бы в последние 10 лет.
                          Ответить
                          • Ебань всякая в банках (дать не дать кредит) делается на прологе. Ну вообще все что касается оценки рисков тоже на нем делается. Это мне тут один интернет знакомый сообщил.
                            Ответить
                            • Ну я ни в банке ни в бутылке не работаю. Еще примеры?
                              Ответить
                              • Ты кусок биомассы живешь на пособие. Что теперь приводить примеры работы с порносайтов?
                                Ответить
                                • Приведи примеры с которыми ты лично сталкивался, пыхомакака.
                                  Ответить
                                  • >Ну я ни в банке ни в бутылке не работаю. Еще примеры?
                                    Какая разница? С теми примерами ты также не сталкивался.
                                    Ответить
                                  • >пыхомакака
                                    ахахаха
                                    Ответить
    • У поста -109

      Так вот почему сайт изредка ложится. Кто-то ддосит.
      Ответить
      • Ты слишком хорошего мнения об этом сайте. Думаю, он и сам упасть может.
        Ответить

    Добавить комментарий