Таким образом - какие захватывающие алгоритмы Вы недавно “обнаружили”?

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

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

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

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

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

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

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

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

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

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

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

Этот алгоритм может быть адаптирован к огромному множеству проблем во многих полях; также тот же алгоритм я упомянул в [1 127] это сообщение .

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

, у Него также есть связанное волшебный обратный квадратный корень .

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

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

введение в алгоритмы биоинформатики является большим чтением для этого вида материала

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

Он не такой яркий, как другие, но он пригодился:

((m + n) + (mn)) / 2 === m (для любых двух действительных чисел m и n)

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

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

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

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