1. Python / Говнокод #26046

    +2

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    >>> from heapq import heappush, heappop
    >>> heap = []
    >>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
    >>> for item in data:
    ...     heappush(heap, item)
    ...
    >>> ordered = []
    >>> while heap:
    ...     ordered.append(heappop(heap))
    ...
    >>> ordered
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> data.sort()
    >>> data == ordered
    True

    В «Python» есть стандартный модуль «heapq» с процедурками, которые делают из обычного листа очередь с приоритетом: https://docs.python.org/3.8/library/heapq.html. Всё просто, понятно, удобно и без этих ваших «классов» с «наследованиями». Именно поэтому я за «Python».

    Запостил: gost, 26 Ноября 2019

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

    • Ведь как сделает обычная заедушная ООП-анскиллябра? Наверняка какую-нибудь хуету с «class Heapq» или и того хуже: «class Heapq(list)»! А тут сразу видно, что писали умные люди. Возможно даже олимпиадники.
      Ответить
      • нет, у олимпиадников было бы так:
        for S in j:
            add3(q, F2) if z


        Но в целом пафос разделяю. Как бишь там? Явное лучше неявного, да?
        Ответить
      • В с++ тоже процедурный интерфейс для кучи, кстати
        Ответить
        • Это не процедурный интерфейс. Это превращение объекта класс list в элегантные шорт а кстати, где в плюсах такая куча-очередь?
          Ответить
      • >без этих ваших «классов» с «наследованиями»

        Во-первых, кто сказал что «классы» и «наследования» это хорошо?
        Во-вторых, Цари пишут несколько разных версий сортировки, попутно штудируя Кнута, после чего выбирают оптимальный алгоритм в райтайме.

        А заедушные петушки только и могут что использовать тормозную, глючную и неспециализированную реализацию сортировки из гвидовского питуха.
        Ответить
        • >оптимальный алгоритм в райтайме.
          в зависимости от микроархитектуры
          Ответить
    • >Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0.

      Ak:k<0:a[k] <= a[2*k+1] and a[k] <= a[2*k+2]

      перевел на язык рус-ни
      Ответить
      • Непонятно. Переведи в «математическую нотацию».
        Ответить
    • А зачем отдельно push и pop? Куча же вроде самоупорядочивается? Или не?
      Ответить
      • А, pop же наверное элемент заодно и удаляет.
        Ответить
    • Не знаю почему, но я за С++
      std::vector data{1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
      std::vector heap{};
      
      std::make_heap(heap.begin(), heap.end());
      
      std::sort(data.begin(), data.end());
      std::all_of(data.begin(), data.end(), [](int value) {
        std::pop_heap(heap.begin(), heap.end());
        bool isEqual = heap.back() == value;
        heap.pop_back();
        return isEqual;
      });
      Ответить
    • Переведи на "PHP".
      Ответить
      • В семёрке можно так:
        https://www.php.net/manual/ru/class.ds-priorityqueue.php

        Для 5.х функции heappush и heappop придётся самому описать.
        Ответить
    • [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
      >>> data.sort()

      Пхаха.
      А я однажды написал сортировку в ноль строк, поставив у ListBoxa свойство Sorted=True
      Ответить
      • Q: можете прямо сейчас реализовать сортировку?
        A: конечно: ``foo.sort()``
        Ответить
        • while (!sorted(foo)) shuffle(foo);
          Ответить
          • while (!sorted(foo)) {shuffle(foo); sleep(1); }
            иначе процессор перегреется
            Ответить
            • Этот алгоритм оптимизирован под квантовые процессоры!
              Ответить
              • массив находится во всех состояниях одновременно, в некоторых из них он уже сортирован, надо только взять их
                Ответить
                • Собственно первый же shuffle и возьмёт отсортированный массив.

                  while здесь фактически выполняет роль ifa.

                  И нужен для совместимости с доквантовым барахлом, которое не может в сортировку с оракулом.
                  Ответить
    • Да, похоже как сишник писал. heappop(heap) вместо heap.pop()

      Но я не поверил, что там без классов с методами написали, пошёл глянуть что там внутри:
      def heappush(heap, item):
          """Push item onto heap, maintaining the heap invariant."""
          heap.append(item)
          _siftdown(heap, 0, len(heap)-1)
      
      def heappop(heap):
          """Pop the smallest item off the heap, maintaining the heap invariant."""
          lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
          if heap:
              returnitem = heap[0]
              heap[0] = lastelt
              _siftup(heap, 0)
              return returnitem
          return lastelt


      Дейстивтельно какое-то уебанство. Обернули какими-то extension-говнометодами готовый класс.
      Ответить
      • >что там без классов
        >что там внутри

        Блин, от этих ехал heap через heap у меня самого тавтологии начались.
        Ответить
      • А шо не так? Это же процiдурки с list'ом работающие, в «Python» массив без «классов» не запилишь.
        Ответить
        • А я пихаю в процедуры данные произвольных типов и теку. Крышечку плотнее закройте.
          Ответить
        • >А шо не так?
          > heappop(heap)
          DRY.

          Да тут прикол в том что само по себе наследование — говно.
          Отнаследовали логику heapa от листа — жестко привязали себя к родительскому классу.
          Захотели сделать очередь на другой реализации листа — извольте копировать код.

          Не знаю есть ли в питоне какие-то mixinы, extension-методы (https://www.dotnetperls.com/extension) или интерфейсы с впиленными методами (https://www.geeksforgeeks.org/default-methods-java/).

          Это бы помогло.
          Ответить
        • Поэтому я за "PHP".
          Ответить

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