Ваш любимый алгоритм и урок, который он вам преподал [закрыт]

Question

Какой алгоритм научил вас больше всего программированию или какой-то конкретной языковой особенности?

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

Answer 1

"Повторять - это по-человечески, повторять - божественно", - процитировано в 1989 году в колледже.

P.S.Опубликовано Woodgnome в ожидании приглашения присоединиться

Answer 2

Общие алгоритмы:

• Быстрая сортировка (и это анализ средней сложности) показывает, что рандомизация вашего ввода может быть полезной!;
• сбалансированные деревья (Деревья AVL например), аккуратный способ сбалансировать затраты на поиск / вставку;
• Dijkstra и Форд-Фулкерсон алгоритмы на графиках (мне нравится тот факт, что второй имеет много приложений);
• семейство алгоритмов сжатия LZ* (LZW например), сжатие данных казалось мне чем-то вроде волшебства, пока я не обнаружил это (давным-давно :));
• тот самый БПФ, повсеместный (повторно используется во многих других алгоритмах);
• тот самый симплексный алгоритм, к тому же вездесущий.

Численное отношение:

• Алгоритм Евклида для вычисления НОД двух целых чисел:один из первых алгоритмов, простой и элегантный, мощный, имеет множество обобщений;
• быстрое умножение целых чисел (Кули-Туки например);
• Итерации Ньютона для инвертирования / нахождения корня, очень мощный мета-алгоритм.

Связанный с теорией чисел:

• Общее собрание акционеров-связанные алгоритмы (примеры):приводит к очень простым и элегантным алгоритмам вычисления числа пи (и многому другому!), хотя теория довольно глубокая (Гаусс ввел из нее эллиптические функции и модульные формы, так что вы можете сказать, что она породила алгебраическую геометрию ...);
• тот самый сито для числового поля (для целочисленной факторизации): очень сложный, но довольно приятный теоретический результат (это также относится к АКС алгоритм, который доказал, что ПРОСТЫЕ ЧИСЛА находятся в P).

Мне также нравилось изучать квантовые вычисления (Шор и Deutsch-Josza алгоритмы, например):это научит вас мыслить нестандартно.

Как вы можете видеть, я немного предвзят к математически ориентированным алгоритмам :)

Answer 3

Алгоритм кратчайших путей Флойда-Уорсхолла для всех пар

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Вот почему это круто:когда вы впервые узнаете о задаче кратчайшего пути в своем курсе теории графов, вы, вероятно, начнете с алгоритма Дейкстры, который решает одинокий- кратчайший путь к источнику.Поначалу это довольно сложно, но потом ты справляешься с этим и полностью понимаешь это.

Затем учитель говорит: "Теперь мы хотим решить ту же задачу, но для ВСЕ источники".Вы думаете про себя: "О боже, это будет гораздо более сложная проблема! Это будет как минимум в N раз сложнее, чем алгоритм Дейкстры!!!".

Затем учитель дает вам Флойда-Уорсхолла.И ваш разум взрывается.Затем вы начинаете плакать от того, насколько удивительно прост этот алгоритм.Это просто цикл с тремя вложениями.Он использует только простой массив для своей структуры данных.

---

Самое интересное для меня - это следующее осознание:допустим, у вас есть решение проблемы A.Тогда у вас есть более крупная "суперзадача" B, которая содержит проблему A.Решение проблемы B на самом деле может быть проще, чем решение проблемы A.

Answer 4

Быстрая Сортировка.Это показало мне, что рекурсия может быть мощной и полезной.

Answer 5

Это может показаться банальным, но в то время для меня это было откровением.Я был на своем самом первом занятии по программированию (VB6), и профессор только что рассказал нам о случайных числах и дал следующие инструкции:"Создайте виртуальный лотерейный автомат.Представьте себе стеклянный шар, наполненный 100 шариками для пинг-понга, помеченными от 0 до 99.Выбирайте их случайным образом и отображайте их количество до тех пор, пока не будут выбраны все, без дубликатов. "

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

Конечно, к концу они провели сотни сравнений, чтобы найти несколько мячей, которые еще не были выбраны.Это было все равно что бросить шарики обратно в банку после того, как отобрал их.Моим откровением было выбрасывать мячи после выбора.

Я знаю, это звучит ошеломляюще очевидно, но именно в этот момент в моей голове щелкнул "переключатель программирования".Это был момент, когда программирование перешло от попыток выучить незнакомый иностранный язык к попыткам разгадать приятную головоломку.И как только я установил эту ментальную связь между программированием и развлечением, меня уже ничто не могло остановить.

Answer 6

Кодирование по Хаффману было бы моим, изначально я создал свою собственную тупую версию, минимизировав количество битов для кодирования текста с 8 до меньшего, но не подумал о переменном количестве битов в зависимости от частоты.Затем я нашел кодировку Хаффмана, описанную в статье в журнале, и это открыло массу новых возможностей.

Answer 7

Алгоритм рисования линий Брезенхэма меня заинтересовал рендеринг графики в реальном времени.Это можно использовать для рендеринга заполненных полигонов, таких как треугольники, для таких вещей, как рендеринг 3D-модели.

Answer 8

Рекурсивный Синтаксический анализ спуска - Я помню, что был очень впечатлен тем, как такой простой код может делать что-то столь, казалось бы, сложное.

Answer 9

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

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Хотя в то время я не мог написать Haskell, я понимал этот код, а вместе с ним рекурсию и алгоритм быстрой сортировки.Это просто щелкнуло, и вот оно появилось...

Answer 10

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

Уточним: подход "fib (10) = fib (9) + fib (8)" означает, что fib (9) будет оцениваться как fib (8) + fib (7).Таким образом, оценка fib (8) (и, следовательно, fib7, fib6) будет оцениваться дважды.

Итерационный метод (curr = prev1 + prev2 в forloop) не использует дерево таким образом и не занимает столько памяти, поскольку в стеке рекурсии всего 3 переходных переменных вместо n кадров.

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

Answer 11

По какой-то причине мне нравится Преобразование Шварца

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

Где foo($) представляет собой трудоемкое выражение, которое принимает $ (каждый элемент списка по очереди) и выдает соответствующее значение, которое подлежит сравнению в его целях.

Answer 12

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

Answer 13

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

Поменяйте местами 2 целых числа без использования промежуточной переменной (в C ++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

Answer 14

Быстрая Сортировка:Пока я не поступил в колледж, я никогда не задавался вопросом, является ли пузырьковая сортировка методом перебора наиболее эффективным способом сортировки.Это просто казалось интуитивно очевидным.Но опыт работы с неочевидными решениями, такими как Быстрая сортировка, научил меня смотреть мимо очевидных решений, чтобы увидеть, доступно ли что-то лучшее.

Answer 15

Для меня это алгоритм слабой сортировки по кучам, потому что он показывает (1), насколько разумно выбранная структура данных (и алгоритмы, работающие над ней) могут влиять на производительность и (2) что интересные вещи можно обнаружить даже в старых, хорошо известных вещах.(weak-heapsort - лучший вариант из всех типов кучи, который был доказанный восемь лет спустя.)

Answer 16

Это очень медленный процесс :)

Я многое узнал как о C, так и о компьютерах в целом, понимая Устройство Даффса и Обмены XOR

Редактировать:

@Джейсон Зет, это мой обмен XOR :) круто, не правда ли.

Answer 17

По какой-то причине Bubble Sort всегда выделялся для меня.Не потому, что он элегантный или хороший, а просто потому, что у него было / имеет дурацкое название, я полагаю.

Answer 18

У меня нет любимый -- есть так много красивых моделей, из которых можно выбрать, но одна, которую я всегда находил интригующей, - это Формула Бейли–Борвейна–Плауффа (BBP), который позволяет вам вычислить произвольную цифру числа пи без знания предыдущих цифр.

Answer 19

RSA познакомил меня с миром модульной арифметики, которая может быть использована для решить a удивительно число из интересно проблемы!

Answer 20

Это ничему меня не научило, но Алгоритм Джонсона–Троттера это никогда не перестает сводить меня с ума.

Answer 21

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

Чему они меня научили:

• компактное представление Любой проблема важна;маленькое - это прекрасно
• для достижения этой цели можно использовать небольшой набор ограничений / сокращений, применяемых рекурсивно
• для задач с симметриями первым шагом к рассмотрению должно быть преобразование в каноническую форму
• не каждое произведение литературы читается.Кнут узнал о BDD через несколько лет после их изобретения / внедрения.(и потратил почти год на их расследование)

Answer 22

Для меня простой обмен в Kelly's Книга по Си демонстрация вызова по ссылке вывела меня из себя, когда я впервые увидел это.Я посмотрел на это, и указатели встали на свои места.Дословно...

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

Answer 23

Тот Самый Алгоритм Ханойских башен это один из самых красивых алгоритмов.Это показывает, как вы можете использовать рекурсию для решения задачи гораздо более элегантным способом, чем итерационный метод.

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

Answer 24

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

Итерационный метод (curr = prev1 + prev2 в forloop) не использует дерево таким образом и не занимает столько памяти, поскольку в стеке рекурсии всего 3 переходных переменных вместо n кадров.

Вы знаете, что у Фибоначчи есть решение в замкнутой форме, которое позволяет напрямую вычислять результат за фиксированное количество шагов, верно?А именно, (phiⁿ - (1 - фи)ⁿ) / sqrt (5).Мне всегда кажется несколько примечательным, что это должно давать целое число, но это так.

фи - это, конечно, золотое сечение;(1 + sqrt(5)) / 2.

Answer 25

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

Answer 26

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

Answer 27

Больше всего я гордился решением, которое заключалось в написании чего-то очень похожего на пакет DisplayTag.Это многому научило меня в области разработки кода, ремонтопригодности и повторного использования.Я написал его задолго до DisplayTag, и он был включен в соглашение NDA, поэтому я не мог открыть исходный код, но я все еще могу с восторгом говорить об этом на собеседованиях при приеме на работу.

Answer 28

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

О...и это всего лишь основа массово-параллельной индексации:

http://labs.google.com/papers/mapreduce.html

Answer 29

Не мой любимый, но самый Алгоритм Миллера Рабина ибо тестирование primality показало мне, что быть правым почти все время - это достаточно хорошо почти всегда.(т.е.Не доверяйте вероятностному алгоритму только потому, что у него есть вероятность ошибиться.)

Answer 30

@Кришна Кумар

Побитовое решение еще интереснее, чем рекурсивное.