Визуализация алгоритмов

    Специалист по дата-майнингу и визуализации данных Майк Босток (Mike Bostock) опубликовал великолепную подборку с визуализацией различных алгоритмов.

    Работа уникальная, в своём роде, потому что в этом случае графическое отображение особенно сложно сделать: ведь, по сути, нет данных для анализа. «Но алгоритмы также демонстрируют, что визуализация — это больше, чем просто инструмент для поиска закономерностей среди данных, — пишет Майк Босток. — Визуализация использует зрительную систему человека, чтобы расширить человеческий интеллект: с её помощью мы лучше понимаем важные абстрактные процессы и, надеюсь, другие вещи тоже».

    Проще говоря, зрение помогает нам думать.

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

    К тому же, графическое представление проблемы помогает найти ошибки в своей реализации алгоритма, да и вообще, это интересно само по себе.

    Автор опубликовал анимационное представление следующих алгоритмов и процессов:

    Тасование (shuffling)
    Быстрая сортировка
    Сортировка слиянием
    Генерация лабиринтов (maze generation)
    Дискретизация

    Например, для быстрой сортировки Майк Босток предлагает три варианта визуализации: 1) анимация; 2) плотная стационарная экспозиция и 3) разреженная стационарная экспозиция. У каждого из вариантов есть свои преимущества и недостатки. Так, на анимацию интересно смотреть, зато статичные картинки можно вдумчиво изучить в подробностях.

    Быстрая сортировка


    function quicksort(array, left, right) {
      if (left < right - 1) {
        var pivot = (left + right) 9>> 1;
        pivot = partition(array, left, right, pivot);
        quicksort(array, left, pivot);
        quicksort(array, pivot + 1, right);
      }
    }
    
    function partition(array, left, right, pivot) {
      var pivotValue = array[pivot];
      swap(array, pivot, --right);
      for (var i = left; i < right; ++i) {
        if (array[i] < pivotValue) {
          swap(array, i, left++);
        }
      }
      swap(array, left, right);
      return left;
    }


    Два варианта статичной визуализации.



    • +35
    • 32.1k
    • 8
    Support the author
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 8

      +3
      Ещё хороший пример визуализации + аудиолизации на youtube — 15 Sorting Algorithms in 6 Minutes. Bogo Sort особо порадовал :)
        0
        15 Sorting Algorithms in 6 Minutes.
        Обалденно, восторг.! Доводилось видеть когнитивную графику, но это нечто.
        0
        у вас по ссылке «Генерация алгоритмов» вместо алгоритмов лабиринты генерируются…
          0
          Майк крут, но есть не менее крутые Венгры

          www.youtube.com/watch?v=CmPA7zE8mx0&feature=share
            +4
            Венгры не такие уж и крутые. Приведённые картинки несколько лучше, но тоже не очень. Дело в том, что глядя на танцующих туда-сюда мужиков, совершенно не видно, почему в данный момент начинают танцевать именно те мужики и именно в то место, куда они утанцевали. В результате понимания не добавляется. На хорошей визуализации должны прослеживаться причины, по которым предпринимаются те или иные действия, а их очень трудно представить наглядно.
              +2
              Да и к тому же, больше 4х минут сортировать массив из 10 элементов — абсолютно неприемлимо!
                +2
                все зависит от сложности сортируемых объектов :) скажем сколько времени приемлимо сортировать десять вагонов?
                0
                Хорошо что никто не стал спорить что Майк танцует лучше чем Венгры. (при всём к нему уважении)

              Only users with full accounts can post comments. Log in, please.