Итак - какие захватывающие алгоритмы вы недавно "обнаружили"?
Мне нравится читать о новых и умных алгоритмах. И мне нравится думать из коробки, поэтому приветствуем все виды алгоритмов из всех областей вычислений.
Время от времени я читаю исследовательские работы, чтобы идти в ногу с текущими исследованиями и расширять горизонт. Мне также нравятся новые трюки. К сожалению, я склонен концентрироваться только на своей области, поэтому я скучаю по множеству полезных вещей.
Пусть просто не публикуются основные вещи. Вместо этого напишите о чем-то особенном, что заставило вас подумать: "Ого - теперь это умное решение!".
Ответы
Ответ 1
Это не что-то совершенно новое или захватывающее, но мне нравится Levenshtein Distance.
Расстояние Левенштейна часто называют расстоянием редактирования между двумя строками и в основном является метрикой, которая измеряет разницу между двумя строками, подсчитывая минимальное количество операций для преобразования одной строки в другую.
Я использую этот алгоритм, чтобы предложить сортировку ряда строк для соответствия порядку внешнего источника (возможно, разных) строк.
Ответ 2
Я начну с того, что каждый может использовать: интроспективный вид. http://en.wikipedia.org/wiki/Introsort
Новые алгоритмы сортировки, которые сочетают в себе лучшие из быстрых, вставки и сортировки кучи. Точнее это не новый алгоритм сам по себе, а умная комбинация очень.
Вы получаете скорость быстрого сортировки до той точки, где быстрая сортировка запускается в вырожденный случай O (n²). Это обнаруживается практически без затрат. Остальные разделы сортируются с использованием кучи или сортировки. Это не только устраняет вырожденный случай, но и создает четкую верхнюю границу для использования стека.
Вставка сортировки берет - как обычно - заботится обо всех небольших разделах, оставшихся после прохода быстрой сортировки.
Для меня это было новое открытие, потому что я прекратил использовать quick-sort для своих приложений.
Я много работаю над встроенными устройствами, и мне приходится заботиться об использовании стека. Использование quick-sort всегда было немного рискованным, потому что слабый шанс, что он работает в стеке. Даже если вы знаете, что с текущими данными все будет в порядке, вы никогда не знаете, сможет ли кто-то позже вырезать ваш код в другой проект и использует его для данных, для которых он никогда не обращался.
Благодаря интроспективной сортировке я теперь полностью контролирую использование стека и получаю повышение производительности.
Ответ 3
Недавно я недавно открыл двоичный вариант старого алгоритма калькулятора Marchant для целых квадратных корней. Нет умножения или деления, только сложение, вычитание и сдвиги. Извините, я потерял ссылку:
def assert
raise "Assertion failed !" if $DEBUG and not yield
end
def sqrt(v)
value = v.abs
residue = value
root = 0
onebit = 1
onebit <<= 8 while (onebit < residue)
onebit >>= 2 while (onebit > residue)
while (onebit > 0)
x = root + onebit
if (residue >= x) then
residue -= x
root = x + onebit
end
root >>= 1
onebit >>= 2
end
assert {value == (root**2+residue)}
assert {value < ((root+1)**2)}
return [root,residue]
end
$DEBUG = true
a = sqrt(4141290379431273280)
puts a.inspect
Вдруг жаль, забыл сказать, что это Руби, для незнакомых.
Ответ 4
Я всегда думал, что функции magic square-root в Quake были очень умными. Это очень быстро, потому что он избегает любых медленных операций, таких как разделение и т.д.
float SquareRootFloat(float num) {
long i;
float x, y;
const float f = 1.5F;
x = num * 0.5F;
y = num;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return num * y;
}
У него также есть связанный волшебный обратный квадратный корень.
Ответ 5
Здесь реализована реализация алгоритма Витерби, которую я недавно обнаружил. Цель здесь - определить оптимальное распределение типов кадров в кодировании видео. Сам Витерби иногда трудно понять, поэтому я считаю, что лучший метод - на самом деле.
В этом примере максимальные последовательные B-кадры - 2. Все пути должны заканчиваться P-кадром.
Длина пути 1 дает нам P
как лучший путь, так как все пути должны заканчиваться на P-кадре, другого выбора нет.
Длина пути 2 дает нам BP
и _P
. "_"
- лучший путь длины 1.
Это дает нам BP
и PP
. Теперь мы вычисляем фактические затраты.
Скажем, для этого примера, что BP лучше всего.
Длина пути 3 дает нам BBP
и _B
P и __P
. "__"
- лучший путь длины 2.
Это дает нам BBP
и PBP
и BPP
. Теперь мы вычисляем фактические затраты.
Скажем, ради этого примера, что BBP лучше всего.
Длина пути 4 дает нам _BBP
и __BP
и ___P
. "___"
- лучший путь длины 3.
Это дает нам PBBP и BPBP и BBPP. Теперь мы вычисляем фактические затраты.
Скажем, ради этого примера, что BPBP лучше всего.
Длина пути 4 дает нам __BBP
и ___BP
и ____P
. "____"
- лучший путь длины 4.
Это дает нам BPBBP
и BBPBP
и BPBPP
.
Теперь - подожди минутку - все пути согласны с тем, что первый кадр - это B
! Итак, первый кадр - B
.
Процесс повторяется до тех пор, пока они не согласятся, какой кадр является первым P-кадром, а затем начинается кодирование.
Этот алгоритм может быть адаптирован к огромному множеству проблем во многих областях; его также тот же алгоритм, о котором я упоминал в этом сообщении.
Ответ 6
Я был впечатлен, когда узнал о алгоритме сортировки блоков Burrows-Wheeler для сжатия данных (как используется в bzip2). Удивительно, что шаг сортировки является обратимым!
Ответ 7
биоинформатика полна случаев экспериментов, генерирующих нагрузки данных в странных формах, требующих обработки имитационных алгоритмов.
введение в алгоритмы биоинформатики - это отличное чтение для такого рода материалов
Ответ 8
Динамическое программирование берет все свои силы с проблемы с оптимальным управлением. Очень освежает.
Ответ 9
Это не так круто, как другие, но это пригодится:
((m+n) + (m-n)) / 2 === m (for any two real numbers m and n)
Я использовал некоторую совокупную логику запросов в SQL для подсчета оценок элемента. Рейтинги - +1 или -1. Мне нужно было знать количество положительных оценок (м), учитывая только общее количество рейтингов и их сумму.
Использование этой логики действительно ускорило запрос и позволило мне вернуть результаты для элементов с рейтингом 0.
(я не выбрал +1 и -1; я унаследовал это.)
Ответ 10
Я нашел это очень полезное доказательство того, что a ^ n = b ^ n + c ^ n, но только для n = 2.
К сожалению, этот блок комментариев слишком мал, чтобы его содержать!