使内联函数避免关闭？

问题描述

我正在读博客：

一个简单的实现Burrow Wheeler压缩算法：

 ＃比较两个字符串str [i..end，0..i-1]和str [ j..end，0..j-1] 
 let cmp（str：_ array）ij = 
 let rec cmp ij = 
 if i = str.Length then 1 else 
 if j = str.Length then -1 else 
 let c =如果c 中比较str。[i] str。[j]然后c else 
 cmp i + 1）（j + 1）
 cmp ij 
＃sort n strings 
 let bwt（str：byte array）= 
 let n = str.Length 
 let a = Array.init n（fun i  - > i）
 Array.sortInPlaceWith（cmp str）a 
 Array.init n（fun i  - > str。[（a。[i] + n  -  1）％n]）
  

这个实现看起来非常有效，他排序 Array.sortInPlaceWith（cmp str）a 使用闭包函数（cmp str），并称它太多次（平均O（n log n））！

通过内联排序算法和比较函数，内联速度非常快。

我的问题是，内联函数是否意味着seeming-closure调用不再是闭包？

我在想的另一件事是C中的函数指针。当我们使用qsort时：

  void qsort（void * base，size_t num， size_t size，int（* comparator）（const void *，const void *））; 
  

我们需要传入比较函数的指针。看来在C的情况下，速度并没有太大的吸引力。

谢谢！

解决方案

如果您将它与C ++实现 std :: sort 。

您可以将C ++版本视为上面提到的内联代码。通过使用模板，您不需要运行时间间接来调用函数指针，但编译器可以直接在编译时间插入和优化给定的比较谓词。

对于上面的F＃代码，第一个实现将要求编译器生成一个在运行时通过间接调用的闭包对象，而内联版本不需要间接寻址，因为它的实现在编译时间。 （但是由于.NET的JIT编译器甚至可以在运行时进行这样的优化，所以我从未想过它们之间的差别会很大）

I am reading a blogpost at:http://flyingfrogblog.blogspot.com/2009/07/ocaml-vs-f-burrows-wheeler.html

a simple implementation for Burrow Wheeler compressing algorithm:

# compare two strings str[i..end,0..i-1] and str[j..end,0..j-1]
let cmp (str: _ array) i j =
  let rec cmp i j =
    if i=str.Length then 1 else
      if j=str.Length then -1 else
        let c = compare str.[i] str.[j] in
        if c<>0 then c else
          cmp (i+1) (j+1)
  cmp i j
# sort n strings
let bwt (str: byte array) =
  let n = str.Length
  let a = Array.init n (fun i -> i)
  Array.sortInPlaceWith (cmp str) a
  Array.init n (fun i -> str.[(a.[i] + n - 1) % n])

This implementation seems quite efficient, but actually slow because the sorting Array.sortInPlaceWith (cmp str) a uses a closure function (cmp str), and calls it too many times (O(n log n) on average)!

By making both sorting algorithm inline and the comparison function inline, the speed is fast.

My question is that does inline function mean that the seeming-closure call is not a closure anymore?

Another thing I am thinking is function pointers in C. When we use qsort:

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

we need to pass in the pointer of a comparison function. It seems that in C's case, the speed does not suck much.

Thanks!

解决方案

It does if you compare it to a C++-implementation of std::sort.

You can think of the C++-version as the inlined code mentioned above. Through the use of templates, you don't need runtime indirection to invoke the function pointer but the compiler can directly insert and optimize the given comparison predicate at compile-time.

In case of your above F#-code, the first implementation will require the compiler to generate a closure object that is invoked through indirection at runtime whereas the inlined version won't need indirection since it's implementation is known at compile-time. (But since .NET's JIT-compiler can even do such optimizations at runtime, I'd never thought the difference would be that big)

这篇关于使内联函数避免关闭？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！