那么 - 最近你"发现"了哪些激动人心的算法？

我喜欢阅读有关新的和聪明的算法.我喜欢开箱即用,因此欢迎各种计算领域的各种算法.

我不时阅读研究论文以跟上当前的研究并扩展我的视野.我也想学习新的技巧.不幸的是,我倾向于只关注我感兴趣的领域,所以我想念很多有用的东西.

我们不要发布主流的东西.而是写一些让你思考的特别的东西:"哇 - 现在这是一个聪明的解决方案!".

我将从每个人都可以使用的东西开始:内省排序.http://en.wikipedia.org/wiki/Introsort

一种新的排序算法,结合了快速,插入和堆排序的最佳选择.确切地说,它本身并不是一种新算法,而是一种非常聪明的组合.

您可以快速排序到快速排序进入退化O(n²)情况的速度.这几乎没有成本检测到.剩余分区使用heap-或merge-sort进行排序.这不仅避免了退化的情况,而且还为堆栈使用创建了明确定义的上限.

插入排序 - 像往常一样 - 关注快速排序传递中遗留的所有小分区.

对我来说这是一个新发现,因为我停止对我的应用程序使用快速排序.

我在嵌入式设备上做了很多工作,我不得不关心堆栈的使用.使用快速排序总是有点冒险,因为它运行的机会很小.即使您知道使用当前数据一切都会很好,您永远不会知道是否有人后来将您的代码切换到一个不同的项目并将其用于数据,而这些数据从来都没有.

由于内省排序,我现在可以完全控制堆栈使用并获得性能提升.

这不是全新或令人兴奋的事情,但我喜欢Levenshtein Distance.

Levenshtein距离通常被称为两个字符串之间的编辑距离,并且基本上是通过计算将一个字符串转换为另一个字符串的最小操作数来测量两个字符串之间的差异的度量.

我正在使用这个算法来建议对一些字符串进行排序,以匹配(可能是不同的)字符串的外部源的顺序.

我最近重新发现了用于整数平方根的旧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,对于那些不熟悉的人.