對於列表循環

Question

永世經常使用

for i in [0 .. 10] do something 

，但據我所知，創建一個列表，然後迭代通過，在我看來，這將更有意義使用

for i = 0 to 10 do something 

，而不產生不必要的列表，但具有相同的行爲。 我錯過了什麼嗎？ （我想是這樣）

Answer 1

你是對的，寫for i in [0 .. 10] do something生成一個列表，它確實有一個重大的開銷。雖然你也可以省略方括號，在這種情況下，它只是建立一個懶惰的序列（事實證明，編譯器甚至優化了這種情況）。我通常更喜歡編寫in 0 .. 100 do，因爲它看起來與遍歷序列的代碼相同。

使用交互式做一個簡單的分析，F＃的#time特點：

for i in [ 0 .. 10000000 ] do // 3194ms (yikes!) 
    last <- i 

for i in 0 .. 10000000 do  // 3ms 
    last <- i 

for i = 0 to 10000000 do  // 3ms 
    last <- i 

for i in seq { 0 .. 10000000 } do // 709ms (smaller yikes!) 
    last <- i 

所以，事實證明，編譯器實際優化in 0 .. 10000000 do到同樣的事情0 to 10000000 do循環。您可以強制它顯式創建惰性序列（最後一種情況），它比列表更快，但仍然非常慢。

Answer 2

前者的形式要求在語言中的特殊構造（VAR爲從...到...的），事情是這樣的，隨後古老的編程語言：

• Fortran語言「做」循環
• 爲VAR：= expr來在帕斯卡
• 等EXPR

後一種形式（在一些變種）是更通用的。它適用於普通列表，但也適用於生成器（如Python）等。在運行列表之前，可能不需要構建完整列表。這允許在潛在的無限列表上編寫循環。

無論如何，一個體面的編譯器/解釋器應該識別相當頻繁的特殊情況[expr1..expr2]，並避免計算和存儲中間列表。

Answer 3

給人一種有些不同形式的答案，但希望有趣一些

你是在正確的F＃編譯器未申請快速for循環優化在這種情況下。好消息是，F＃編譯器是開源的，我們可以改進它的行爲。

所以這裏有一個免費的東西從我：

快速for循環優化發生在tastops.fs。目前這是相當原始的，我們有很好的機會改進。

// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <finishExpr> do <bodyExpr>' expression over integers 
// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <step> .. <finishExpr> do <bodyExpr>' expression over integers when step is positive 
let (|CompiledInt32ForEachExprWithKnownStep|_|) g expr = 
    match expr with 
    | Let (_enumerableVar, RangeInt32Step g (startExpr, step, finishExpr), _, 
      Let (_enumeratorVar, _getEnumExpr, spBind, 
       TryFinally (WhileLoopForCompiledForEachExpr (_guardExpr, Let (elemVar,_currentExpr,_,bodyExpr), m), _cleanupExpr))) -> 

     let spForLoop = match spBind with SequencePointAtBinding(spStart) -> SequencePointAtForLoop(spStart) | _ -> NoSequencePointAtForLoop 

     Some(spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m) 
    | _ -> 
     None 

let DetectFastIntegerForLoops g expr = 
    match expr with 
    | CompiledInt32ForEachExprWithKnownStep g (spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m) 
     // fast for loops only allow steps 1 and -1 steps at the moment 
     when step = 1 || step = -1 -> 
      mkFastForLoop g (spForLoop,m,elemVar,startExpr,(step = 1),finishExpr,bodyExpr) 
    | _ -> expr 

的這裏的問題是，RangeInt32Step只檢測像0..10和0..1..10模式。它錯過例如[0..10]

讓我們介紹符合這些類型的表達式的另一個活躍模式SeqRangeInt32Step：

let (|SeqRangeInt32Step|_|) g expr = 
    match expr with 
    // detect '[n .. m]' 
    | Expr.App(Expr.Val(toList,_,_),_,[TType_var _], 
       [Expr.App(Expr.Val(seq,_,_),_,[TType_var _], 
          [Expr.Op(TOp.Coerce, [TType_app (seqT, [TType_var _]); TType_var _], 
            [RangeInt32Step g (startExpr, step, finishExpr)], _)],_)],_) 
     when 
      valRefEq g toList (ValRefForIntrinsic g.seq_to_list_info) && 
      valRefEq g seq g.seq_vref && 
      tyconRefEq g seqT g.seq_tcr -> 
      Some(startExpr, step, finishExpr) 

    | _ -> None 

你怎麼搞清楚，這是你需要爲模式匹配呢？我經常採用的方法是使用正確的屬性來執行一個簡單的F＃程序，並在編譯過程中放置​​一個斷點來檢查表達式。從我創建的模式匹配：

讓我們把兩種模式一起：

let (|ExtractInt32Range|_|) g expr = 
    match expr with 
    | RangeInt32Step g range -> Some range 
    | SeqRangeInt32Step g range -> Some range 
    | _ -> None 

CompiledInt32ForEachExprWithKnownStep被更新爲使用ExtractInt32Range超過RangeInt32Step

完整的解決方案將是這樣的：

使用簡單的測試程序

let print v = 
    printfn "%A" v 

[<EntryPoint>] 
let main argv = 
    for x in [0..10] do 
     print x 

    0 

優化之前，相應的C＃代碼會是這個樣子（IL代碼是更好地檢查，但可能有點難以理解，如果一個未使用它）：

// Test 
[EntryPoint] 
public static int main(string[] argv) 
{ 
    FSharpList<int> fSharpList = SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(0, 1, 10))); 
    IEnumerator<int> enumerator = ((IEnumerable<int>)fSharpList).GetEnumerator(); 
    try 
    { 
     while (enumerator.MoveNext()) 
     { 
      Test.print<int>(enumerator.Current); 
     } 
    } 
    finally 
    { 
     IDisposable disposable = enumerator as IDisposable; 
     if (disposable != null) 
     { 
      disposable.Dispose(); 
     } 
    } 
    return 0; 
} 

F＃創建一個列表，然後使用枚舉器遍歷它。難怪與經典的for循環相比，它相當慢。

後的優化應用，我們得到這個代碼：

// Test 
[EntryPoint] 
public static int main(string[] argv) 
{ 
    for (int i = 0; i < 11; i++) 
    { 
     Test.print<int>(i); 
    } 
    return 0; 
} 

一個顯著的改善。

因此，盜取此代碼，發佈PR到https://github.com/Microsoft/visualfsharp/，並獲得榮耀。當然，您需要添加單元測試和發射的IL代碼測試，這些測試可能有點棘手以找到合適的級別，請檢查此commit的靈感

PS。可能應該支持[|0..10|]以及seq {0..10}以及

PS。此外，for v in 0L..10L do print v以及for v in 0..2..10 do print v在F＃中效率低下。