Итак, какие захватывающие алгоритмы вы "открыли" в последнее время?

Question

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

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

Давай просто не будем публиковать основные темы. Вместо этого напишите о чем-то особенном, что заставило вас задуматься: «Ух ты - теперь это умное решение!"

Answer 1

Я начну с того, что каждый может использовать: интроспективная сортировка. http://en.wikipedia.org/wiki/Introsort

Новый алгоритм сортировки, который сочетает в себе лучшее из быстрой сортировки, вставки и сортировки кучи. Точнее, это не новый алгоритм сам по себе, а очень умная комбинация .

Вы получаете скорость быстрой сортировки до точки, где быстрая сортировка наталкивается на вырожденный корпус O (n²). Это обнаруживается практически без затрат. Остальные разделы сортируются с использованием кучи или сортировки слиянием. Это не только позволяет избежать вырожденного случая, но и создает четкую верхнюю границу для использования в стеке.

Сортировка вставок, как обычно, заботится обо всех небольших разделах, оставшихся после прохода быстрой сортировки.

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

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

Благодаря интроспективной сортировке у меня теперь есть полный контроль над использованием стека и повышение производительности.

Answer 2

Это не что-то совершенно новое или захватывающее, но мне нравится Расстояние Левенштейна .

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

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

Answer 3

Недавно я заново открыл двоичный вариант старого алгоритма калькулятора Маршана для целочисленных квадратных корней. Нет умножения или деления, только сложение, вычитание и сдвиги. Извините, я потерял ссылку:

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

Вдвойне извините, забыл сказать, что это Ruby, для тех, кто незнаком.

Answer 4

Я всегда думал, что магический квадратный корень функции в 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;
}

У него также есть связанный магический обратный квадратный корень .

Answer 5

Динамическое программирование использует всю мощь с задачами оптимального управления . Очень освежает.

Answer 6

Биоинформатика полна случаев экспериментов, генерирующих множество данных в странных формах, требующих обработки оригинальных алгоритмов.

введение в алгоритмы биоинформатики отлично подходит для такого рода вещей

Answer 7

Я был впечатлен, когда узнал об алгоритме сортировки блоков Burrows-Wheeler для сжатия данных (который используется в bzip2 ). Удивительно, но шаг сортировки обратим!

Answer 8

Вот реализация алгоритма Витерби , который я "открыл" недавно. Целью здесь является определение оптимального распределения типов кадров при кодировании видео. Самого Витерби иногда немного сложно понять, поэтому я думаю, что лучший метод - это на примере.

В этом примере максимальное количество последовательных 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-кадром, и затем начнется кодирование.

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

Answer 9

Это не так броско, как другие, но пригодилось:

((m+n) + (m-n)) / 2 === m (for any two real numbers m and n)

Я использовал некоторую агрегированную логику запросов в SQL для подсчета оценок элемента. Рейтинги либо +1, либо -1. Мне нужно было знать количество положительных оценок (м), учитывая только общее количество оценок, и их сумму.

Использование этой логики действительно ускорило запрос и позволило мне возвращать результаты для элементов с 0 оценками.

(я не выбрал +1 и -1; я унаследовал это.)

Answer 10

Я нашел это очень полезное доказательство того, что a ^ n = b ^ n + c ^ n, но только для n = 2.
К сожалению, это поле для комментариев слишком маленькое, чтобы его содержать!