how to order PSeq with the original index of list

Category: visual studio fsharp

Question

Map to new space on Fri, 09 May 2014 03:18:08


1.

[list1; list4] |> PSeq.map test2 |> PSeq.toList

when using divide and conquer with parallel , PSeq result not in order by the original index of list

2.

when using divide and conquer with parallel , it become very slow,

does it mean divide and conquer with parallel is useless ?

3.

calculated at once when read is the most fastest and faster than divide and conquer without parallel 

does it mean that divide and conquer is useless?

a simple for loop already faster than divide and conquer

let rec test1(xs : decimal list) =
        let (list1, list2) = split1 (xs.Length/2) xs
        let (list3, list4) = split1 (xs.Length/2-1) xs
        let b1 = list1  |> Seq.windowed 2
                        |> Seq.map (fun x -> x.[0]/x.[1])
                        |> Seq.toList
        let b2 = list4  |> Seq.windowed 2
                        |> Seq.map (fun x -> x.[0]/x.[1])
                        |> Seq.toList
        b1 @ b2

    let rec test2(xs : decimal list) =
        if xs.Length > 5 then
            let (list1, list2) = split1 (xs.Length/2) xs
            let (list3, list4) = split1 (xs.Length/2-1) xs

            let b1::b2::_ = [list1; list4] |> Seq.map test2 |> PSeq.toList
            b1 @ b2
        else
            let b1 = xs |> Seq.windowed 2
                        |> Seq.map (fun x -> x.[0]/x.[1])
                        |> Seq.toList
            b1

    // Addition optimized using memoization
    let test2a = 
        // Initialize the cache 
        let cache = new Dictionary<_, _>()
        // Created function uses the private cache
        (fun x ->
            // Read the value from the cache or calculate it
            match cache.TryGetValue(x) with
            | true, v -> v
            | _ -> let v = test2(x)
                   cache.Add(x, v)
                   v)

    //let b7 = split1 4 a
    //let b8 = test1(a)
    //let b10 = test2(a)
    let sw0 = new Stopwatch()
    sw0.Start()
    let small2 = new CsvProvider<"C:\\Users\\martin.lee\\Downloads\\0388.HK.csv">()
    let mutable close = []
    let small3 = small2.Rows.Reverse()
    for row in small3 do
        close <- row.Close :: close
    sw0.Stop()
    Console.WriteLine("reading csv Elapsed={0}",sw0.Elapsed)
    Console.WriteLine("***")

    let sw = new Stopwatch()
    sw.Start()
    let b1 = test1(close)
    sw.Stop()
    Console.WriteLine("Divide one time Elapsed={0}",sw0.Elapsed + sw.Elapsed)
    let sw2 = new Stopwatch()
    sw2.Start()
    let b2 = test2(close)
    sw2.Stop()
    Console.WriteLine("Divide and conquer without parallel map Elapsed={0}",sw0.Elapsed + sw2.Elapsed)

    let sw3 = new Stopwatch()
    sw3.Start()
    let mutable close2 = []
    let mutable return2 = []
    let mutable previousvalue : decimal = Decimal.Zero
    let small3 = small2.Rows.Reverse()
    for row in small3 do
        close2 <- row.Close :: close2
        if previousvalue <> Decimal.Zero then
            return2 <- row.Close/previousvalue :: return2
        previousvalue <- row.Close
    sw3.Stop()
    Console.WriteLine("Calculated at once Elapsed={0}",sw3.Elapsed)


成功者拿未來換現在,失敗者用現在換未來. 原來無求品自高, 機到有求先得手. She likes you.




Replies

Mr. Tines on Sat, 10 May 2014 07:15:29


A simple way to do things would be to start by tagging each list entry with its index and sort the output

mylist
|> List.mapi (fun i x -> (i,x))
|> parallelOperation
|> List.sortBy (fun (i,x) -> i)
|> List.map snd
However it would probably be worth investigating ParallelEnumerable.AsOrdered and its friends rather than rolling your own.

Map to new space on Mon, 12 May 2014 08:36:16


error at 

b1 @ b2

expected to type 'a * 'b  but here have type 'c list

let rec test2(xs : decimal list) =
    if xs.Length > 3 then
        let (list1, list2) = split1 (xs.Length/2) xs
        let (list3, list4) = split1 (xs.Length/2-1) xs

        let b1::b2::_ = [list1; list4]  |> List.mapi (fun i x -> (i,x)) 
                                        |> PSeq.map (fun x -> test2(snd x)) 
                                        |> PSeq.toList 
                                        |> List.sortBy (fun (i,x) -> i) 
                                        |> List.map snd
        b1 @ b2

Mr. Tines on Mon, 12 May 2014 21:55:03


Probably because this is the same problem in your related question about (int,decimal) list because no sooner have you added the tag you wanted to sort with then you try to throw it away before passing the tagged value in the recursion.

Also you're passing a scalar value into the recursive call to test2 which is expecting a list.

I think you have gotten yourself deeply confused here.

Map to new space on Tue, 13 May 2014 04:14:33


|> PSeq.map (fun x -> test2(snd x)) 

isn't it passing the list ?

snd is for passing list into function recursively, the index i added is just for sorting, and i will throw it away

and just get the list in later part

i am really confused, it return error expected 'a * 'b , but in previous work, 'a list is correct

let rec test2(xs : decimal list) =
    if xs.Length > 3 then
        let (list1, list2) = split1 (xs.Length/2) xs
        let (list3, list4) = split1 (xs.Length/2-1) xs
        //|> Seq.map test2  |> Seq.toList
        let b1::b2::_ = [list1; list4]  |> List.mapi (fun i x -> (i,x)) 
                                        |> PSeq.map (fun x -> test2(snd x)) 
                                        |> PSeq.toList 
                                        |> List.sortBy (fun (i,x) -> i) 
                                        |> List.map snd
                                        |> List.toSeq
                                        |> Seq.toList
        b1 @ b2
    else
        let b1 = xs |> Seq.windowed 2
                    |> Seq.map (fun x -> x.[0]/x.[1])
                    |> Seq.toList
        //let b1 = xs |> PSeq.map (fun x -> (snd x).[0]/(snd x).[1])
                    //|> List.sortBy (fun (i,x) -> i)
                    //|> List.map snd
        b1

Mr. Tines on Tue, 13 May 2014 06:09:25


Right, I forgot that this was a list of lists.

The outline

mylist
|> List.mapi (fun i x -> (i,x))
|> parallelOperation
|> List.sortBy (fun (i,x) -> i)
|> List.map snd
is to tag the list values at the top level, and work in terms of (tag, value) pairs in the parallel operation, so that when they all complete you can reassemble the mapped values in the original order.