Архив интересного кода

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

    Примеры на сайте преимущественно закодированы в C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных. Структуры данных реализованы на Java.

    Кит Шварц дает разрешение использовать свой код всем желающим без всяких ограничений.

    Каждый пример кода Кит Шварц дополняет подробным комментарием, объясняя каждую строчку и все аспекты целой концепции.

    В коллекции есть серьёзные вещи: алгоритм Дейкстры (Java) или вейвлет Хаара, а также просто интересные примеры кода, как игра «Змейка» (C++).

    Работа Шварца только началась. Пока что готов лишь малая часть алгоритмов и структур данных, которые автор планирует обработать в будущем: см. его список TODO. По словам самого Кита, список чаще увеличивается, чем сокращается. Жирным в списке отмечены алгоритмы, которые планируется реализовать в ближайшее время.

    Для изучения: другие коллекции алгоритмов.
    http://teachingtree.co/cs
    http://www.geeksforgeeks.org/
    http://aggregate.org/MAGIC/
    http://www.algorithmatic.com/browse?q=sort:latest
    http://programmingpraxis.com/contents/chron/
    http://xlinux.nist.gov/dads/
    Поделиться публикацией

    Комментарии 33

      +3
      Достаточно амбициозно… но если Кейту действительно нравится всё это делать (анализировать и очень тщательно комментировать), то получится шикарная коллекция. Я думаю многие будут о-очень благодарны ему.
      Однозначно в избранное.
        +5
        Алгоритм Дейкстры-то уж без сомнения очень серьезная вещь :)

        Ну, а в целом конечно крайне импонирует видеть такие ресурсы
          +1
          Зато исходники прокомментированы, хорошо отформатированы, так что подход к делу основательный)
          +3
          Keith правильно читается как «Кит». Кейт (Kate) — это женское имя.
            0
            Смотря на каком языке. Фамилия-то у него немецкая (Sch — Ш). Возможны разночтения.
              +4
              В таком случае имя должно читаться как «Кайт».
                0
                В качестве личного имени Keith встречается у британцев и американцев, так что следует читать по-английски.
            0
            Надеюсь, в коллекцию попадет референсная реализация bubblesort ;)
              +3
              Что такое референсная реализация bubblesort? Уж не это ли?
              for (int i=0;i<n;i++) ref[i]=i;
              for (int i=0;i<n;i++)
                for (int j=0;j<n-1;j++) 
                  if (to_sort[ref[j]] > to_sort[ref[j+1]])
                    swap(ref[j],ref[j+1);
              
                0
                Это Вы так шутить изволили? :)
                  +1
                  Ни капли. Сколько я не гуглил референсную реализацию пузырька на русском и английском — ничего не нашел. Вот и интересуюсь, что такое?
                    0
                    Как насчет этого?

                    Или, если брать Ваш пример кода, то нужно сделать следующие небольшие изменения:
                    for (int i=1;i<n;i++)
                      for (int j=0;j<i;j++) 
                        if (to_sort[ref[j]] > to_sort[ref[j+1]])
                          swap(ref[j],ref[j+1);
                    


                    В чем суть: это небольшое изменение снизит количество сравнений с n*(n-1) до n*(n-1)/2, при этом оставив сортировку корректной. Насколько я знаю, это лучшая возможная реализация сортировки пузырьком.

                    О корректности:
                    К концу первой итерации внешнего цикла максимальный элемент будет находится в конце массива. Потому, на второй итерации, когда мы будем гнать «второй сверху» элемент на предпоследнее место в массиве, нам нет смысла сравнивать его с последним, потому что тот, заведомо больше. Отсюда и условие j < i.
                      0
                      Разумеется я знаю эту и некоторые другие реализации пузырька. Меня интересует одна конкретная реализация пузырька — «референсная», которая настолько интересна, что инициатор ветки предлагает добавить ее в список выше.
                        +2
                        Если оптимизировать количество итераций, то стоит тогда добавить во внутренний цикл флаг обмена и проверять его во внешнем.
                          0
                          Ой-вей, только j < n-i, опечаточка вышла.
                  +20
                    +4
                    Очень красиво написано (методы сгруппированы, оставлены пустые строки для разделения разных секций, пробелы все на месте, одно удовольствие читать). В России\Украине преподаватели так не пишут, у всех все как попало…
                      +9
                      Примеры на сайте преимущественно закодированы в C++, поскольку этот язык лучше всего подходит для описания алгоритмов.

                      Ась?

                      На всякий случай, цитата из самого автора:
                      I generally prefer to use C++ for algorithms, since the STL provides a great framework for expressing algorithms that work on a variety of data types.

                      «Я предпочитаю использовать для алгоритмов C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных».
                        0
                        Ну если открыть ссылку, можно узнать, что алгоритмы преимущественно закодированы в C++ из-за библиотеки шаблонов, а структуры данных — на Java из-за Collections и сборщика мусора.
                        UPD. уже не актуально :(
                          +8
                          Ссылку-то я открыл. Просто Ализар традиционно переврал оригинал.

                          (ну и да, описывать структуры данных на языке со сборщиком мусора — это, конечно, современно, но не всегда поучительно)
                        +2
                        Удобно, что сразу в одном месте описание алгоритма, строгое доказательство корректности, и реализация. Хотелось бы конечно ещё группировку по темам (как на e-maxx например), может быть автор добавит.
                          0
                          А где строгие доказательства?
                        +1
                        Здесь явно не хватает целочисленного алгоритма вычисления инверсного обратного корня.
                          +2
                          Про хитрые целочисленные вычисления целая книга есть: «Hacker's delight», Henry S. Warren, Jr
                          +5
                          А можно было и на github все это класть :)
                            +1
                            Чтобы люди пулл-реквесты присылали? :)
                              +2
                              Да нет. Ради того, что удобно искать код, когда он весь в одном месте
                            +2
                            Тесты есть?:)
                              +8
                              А если найду?
                              +1
                              Я вот, когда на JS искал Levenshtein distance, нашел некий rosettacode.org
                              Например, rosettacode.org/wiki/Levenshtein_distance

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

                            Самое читаемое