小编Pet*_*gey的帖子

我有兴趣编写一个高效的 Haskell 函数triangularize :: [a] -> [[a]]，它接受一个（可能是无限的）列表并将其“三角化”为一个列表列表。例如，triangularize [1..19]应该返回

[[1,  3,  6,  10, 15]
,[2,  5,  9,  14]
,[4,  8,  13, 19]
,[7,  12, 18]
,[11, 17]
,[16]]

高效，我的意思是我希望它及时运行，O(n)其中n列表的长度是多少。

请注意，这在 Python 这样的语言中很容易做到，因为附加到列表（数组）的末尾是一个常数时间操作。完成此操作的一个非常命令式的 Python 函数是：

def triangularize(elements):
    row_index = 0
    column_index = 0
    diagonal_array = []
    for a in elements:
        if row_index == len(diagonal_array):
            diagonal_array.append([a])
        else:
            diagonal_array[row_index].append(a)
        if row_index == 0:
            (row_index, column_index) = (column_index + 1, 0)
        else:
            row_index -= 1
            column_index += …

在 Ruby 2.1.4* 中 IRB 的粗略性能测试中，我注意到它的i**0.5执行速度似乎比Math.sqrt(i).

def benchmark(n, &block)
  start = Time.now
  (1..n).each(&block)
  Time.now - start
end

结果：

benchmark(1_000_000) { |i| i**0.5 }
=> 0.101748

benchmark(1_000_000) { |i| Math.sqrt(i) }
=> 0.257887

1. 在什么情况下我应该使用Math.sqrt(i)而不是i**0.5？
2. 是否存在精确权衡？（我特别注意到这一点Math.sqrt(3015) != 3015**0.5。）
3. 为什么不Math.sqrt直接作为指数实现？

* 在 2.3.0 中，这种差异似乎已经消失，而且速度确实Math.sqrt快了 30% 左右。