3 people like it.
Like the snippet!

Faster Filter

A filter function for arrays that is up to 4x faster and uses less memory. The catch is you need to manage the IndexPool, in case you filter some huge arrays and want the memory back after.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24:

open System
open System.Threading

type IndexPool private () =
    static let instance = new ThreadLocal<_>(fun () -> ResizeArray<int>(100000))
    static member Instance = instance.Value

type Array with    
  static member inline fastFilter (f: ^T -> bool) (array: ( ^T)[]) = 
    if array = null then invalidArg "array" "Array can not be null."            
    if array.Length = 0 then invalidArg "array" "Array can not be empty."    
    
    let indices = IndexPool.Instance
    indices.Clear()    
    for i = 0 to array.Length-1 do
        if f array.[i] then
            indices.Add(i)
        

    let res = Array.zeroCreate indices.Count
    for i = 0 to res.Length-1 do
        res.[i] <- array.[indices.[i]]
        
    res

namespace System

namespace System.Threading

Multiple items
type IndexPool =
private new : unit -> IndexPool
static member Instance : List<int>

Full name: Script.IndexPool

--------------------
private new : unit -> IndexPool

val instance : ThreadLocal<Collections.Generic.List<int>>

Multiple items
type ThreadLocal<'T> =
  new : unit -> ThreadLocal<'T> + 1 overload
  member Dispose : unit -> unit
  member IsValueCreated : bool
  member ToString : unit -> string
  member Value : 'T with get, set

Full name: System.Threading.ThreadLocal<_>

--------------------
ThreadLocal() : unit
ThreadLocal(valueFactory: Func<'T>) : unit

type ResizeArray<'T> = Collections.Generic.List<'T>

Full name: Microsoft.FSharp.Collections.ResizeArray<_>

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

static member IndexPool.Instance : Collections.Generic.List<int>

Full name: Script.IndexPool.Instance

property ThreadLocal.Value: Collections.Generic.List<int>

type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array

static member Array.fastFilter : f:('T -> bool) -> array:'T [] -> 'T [] (requires equality)

Full name: Script.fastFilter

val f : ('T -> bool) (requires equality)

type bool = Boolean

Full name: Microsoft.FSharp.Core.bool

Multiple items
val array : 'T [] (requires equality)

--------------------
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>

val invalidArg : argumentName:string -> message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.invalidArg

property Array.Length: int

val indices : Collections.Generic.List<int>

type IndexPool =
private new : unit -> IndexPool
static member Instance : List<int>

Full name: Script.IndexPool

property IndexPool.Instance: Collections.Generic.List<int>

Collections.Generic.List.Clear() : unit

val i : int

Collections.Generic.List.Add(item: int) : unit

val res : 'T [] (requires equality)

val zeroCreate : count:int -> 'T []

Full name: Microsoft.FSharp.Collections.Array.zeroCreate

property Collections.Generic.List.Count: int

Raw view Test code New version

More information

Link:	http://fssnip.net/7Qp
Posted:	8 years ago
Author:	Jack Mott
Tags:	filter