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

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

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

25.08.2008 15:55:42
30 ОТВЕТОВ
РЕШЕНИЕ

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

PS Автор сообщения: Woodgnome, ожидая приглашения присоединиться

17
25.08.2008 16:20:15

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

9
25.08.2008 16:07:15

Это медленный :)

Я многое узнал как о C, так и о компьютерах в целом, разбираясь в перестановках Duffs Device и XOR

РЕДАКТИРОВАТЬ:

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

1
23.05.2017 12:25:08

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

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

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}
2
25.08.2008 16:24:35
Просто из любопытства, есть ли какая-то причина, чтобы делать что-то таким образом, вместо использования std :: swap?
Jason Baker 8.12.2008 22:48:17
В средах с очень малым объемом памяти (например, во встроенных системах) это может сэкономить выделение дополнительной памяти. Вроде слабый, я знаю. Как я уже сказал, акцент был сделан на нестандартном мышлении. На первый взгляд вы можете подумать, что невозможно поменять местами без промежуточной переменной.
Jason Z 9.12.2008 13:19:31
Этот код потерпит неудачу, если ему передадут одну и ту же переменную в обоих параметрах. Не так маловероятно, как кажется!
Dean Svendsen 30.06.2009 03:54:23

Для меня, простой обмен в книге Келли и Пола « Книга на С» для демонстрации обращения по ссылке перевернул меня, когда я впервые увидел это. Я посмотрел на это, и указатели встали на место. Verbatim. , ,

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

   temp = *p;
   *p = *q;
   *q = temp;
}
0
25.08.2008 16:47:09

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

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

0
25.08.2008 16:56:51

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

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

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

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

Теория чисел, связанная с:

  • AGM- связанные алгоритмы ( примеры ): приводят к очень простым и элегантным алгоритмам для вычисления числа pi (и намного больше!), Хотя теория довольно глубока (Гаусс ввел из нее эллиптические функции и модульные формы, так что вы можете сказать, что она родила алгебраической геометрии ...);
  • решета числового поля (для целочисленной факторизации): очень сложно, но вполне хороший теоретический результат (это также касается и АКС алгоритма, который доказал , что PRIMES в P).

Мне также понравилось изучать квантовые вычисления ( например, алгоритмы Шора и Дойча-Йосзы ): это учит вас мыслить «из коробки».

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

32
25.08.2008 17:15:52

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

1
25.08.2008 17:01:47

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

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

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

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

3
25.08.2008 17:27:35

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

Все остальные написали свою программу следующим образом: выберите шар, поместите его номер в «уже выбранный список», а затем выберите другой шар. Проверьте, выбран ли он уже, если это так, выберите другой шар, если нет, поместите его номер в «список уже выбранных» и т. Д ....

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

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

9
25.08.2008 18:23:57
У меня было это упражнение и в школе. Мое решение состояло в том, чтобы перемешать шары, меняя значение в каждом индексе массива значением случайного индекса, а затем распечатывать значения массива.
Dour High Arch 8.12.2008 22:18:33
@Dour: я сделал то же самое, но мы ошиблись - codinghorror.com/blog/archives/001015.html :)
JoeBloggs 10.12.2008 11:54:49

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

2
26.08.2008 13:55:08

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

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

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

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

0
26.08.2008 14:02:56

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

3
17.08.2010 16:06:45

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

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

0
3.07.2012 14:46:47

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

10
26.08.2008 14:09:10

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

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

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

3
26.08.2008 14:13:13
Хорошо, я думаю, это может быть интересно. Язык, который вы используете, немного неясен: /. Не могли бы вы дать немного комментариев?
Edmund 18.08.2010 10:46:03
Между прочим, этот рисунок первоначально назывался украшением старой школы. Рэндалл показал это некоторым людям в IRC, и с тех пор он назван в его честь. Вот гораздо более понятная версия Python: sorted = [v для k, v для sorted ([foo (k), k для k в unsorted], key = lambda x: [0])] Хитрость заключается в том, чтобы «кэшировать» ключевая функция для сравнения в списке кортежей вместо вычисления его для каждого сравнения. Это уменьшает оценки foo с nlogn до n в среднем.
rgrinberg 13.12.2012 06:44:33

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

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

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

4
26.08.2008 14:14:04
Да, я тоже помню это - очень круто; это не алгоритм на месте, но в любом случае ...
blabla999 13.01.2009 18:06:18

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

7
2.09.2008 14:41:34

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

6
2.09.2008 15:23:58

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

2
27.08.2013 12:50:21

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

0
26.11.2008 14:29:44

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

0
13.01.2009 18:14:59

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

0
8.10.2009 14:55:39

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

0
18.08.2010 09:57:04

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

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

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

0
8.10.2009 14:57:18

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

1
8.10.2009 14:57:35

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

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 на самом деле может быть проще, чем решение проблема А.

11
5.03.2010 01:02:07
Ну, я + 1, потому что я думаю, что FW - фантастический алгоритм, но я не могу честно сказать, что он настолько хорош, что вызывает у меня слезу ... Сердце камня, я знаю :-P
j_random_hacker 13.12.2012 09:49:47

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

1
12.08.2010 17:34:03

Бинарный поиск должен быть самым простым и элегантным алгоритмом. Конечно, данные должны быть отсортированы, и для этого алгоритм сортировки слиянием также является наиболее простым и элегантным.

0
13.12.2012 09:29:34

Я многому меня не научил, но алгоритм Джонсона-Троттера не может не поразить меня.

1
13.12.2012 09:32:11