Back to Questions
2.2k
views15
comments
Reading a column from a text file into an array
f#

I've momentarily given up on trying to read Excel. I've copied an Excel file (25,000 rows) to a text file. I want to read the 7th column into an Array. Actually I just think this is what I want to do, but it should depend on how efficient various methods are.

Anyway, I've written the following code to accomplish this. It's really really slow. I didn't time it, but it probably takes about 15 minutes. This leads me to believe that I'm doing something really wrong. Could anyone let me know if there's a better way to do this, and what it is that I doing that is so stupid.

Oh, I copied the data reader stuff from a sample.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

open System.IO
let mPath = @"J:\DataFolder\"
let ExcelData=
    seq { use reader = new StreamReader(File.OpenRead(mPath + "Written & Expense.txt"))
        while not reader.EndOfStream do 
            yield reader.ReadLine() }
let y = Seq.map (fun x -> String.split['\t'] x) ExcelData

let f1() i x =
    let y = Seq.nth(i) x
    let z= String.split['\t'] y
    Seq.nth(6) z

let bb = Array.init 25340 (fun x -> f1() x ExcelData)

Thanks,

Mitchell

.

You don't want to use Seq.nth, it is an O(n) operation which makes the evaluation of bb O(n^2). Try

1

let bb = ExcelData |> Seq.map (fun x -> List.nth (String.split ['\t'] x) 6) |> Seq.to_array
By on 2/1/2008 2:32 PM ()

Wow!

The difference was huge. In playing around with it, though, it looks like the problem was more with my poor construction rather than Seq.nth. I tried exactly the same code lusing Seq.nth rather than List.nth and it worked fine. Maybe the list wasn't long enough?

When I put in List.nth instead, I did have to change your syntax to:

1

List.nth (String.split ['\t'] x) 6

.

Is Seq.nth O(n) while List.nth is faster?

Also, since it seemed to work fine with Seq.nth, I'm unclear as to what the difference is.

Anyway, thanks very much, the revised code made a huge difference.

Mitchell

By on 2/3/2008 1:41 AM ()

Sorry, I should have been more precise in my explanation. The use of Seq.nth in the code 

1

Seq.nth(6) z

is ok. The performance problem with your code is in the line 

1

let y = Seq.nth(i) x

. This use of nth is bad because for <i>every element<i> in the output array, <c>f1</c> opens the data file again and reads through it from the beginning until the nth line. This is what introduces the quadratic performance in the number of lines in the file. <c>Seq.nth</c> and <c>List.nth</c> are similar functions: they are both linear in the size of their collection as work analogously to iterating through a linked list to get to the nth item. P.S. As you pointed out, I got the order of the parameters to <c>List.nth</c> wrong. I've fixed that now.

By on 2/3/2008 5:15 PM ()

A related question, if I may:

I think I should be able to figure this out myself, but so far I'm having no luck. I'd like to set an array equal to 1 column and another array to another column (and eventually a few more later on). Anyway, I could repeat the code for each column, but then I'll have to go through the list twice, which doesn't seem great.

I was trying to figure out how to do it in one pass using Seq.map a few times. So far I haven't been able to get anything to survive a syntax check (evidence of my lack of knowledge). Is it sensible to look for this type of solution? If so, any hints?

I guess I could use a 2-dim array, but the code that follows would seem more mysterious, relying on that second index to indentify the meaning of the column. It just seemed like it would make more sense to keep the columns as separate arrays, with understandable names.

Thanks for any help!

Mitchell

By on 2/4/2008 12:52 PM ()

If you want to have separate arrays then doing it as Robert says is good (you'll need to reverse the accumulators returned from loop though). However given that this is data from a spreadsheet you'd usually want to keep data from individual rows grouped together. You could do this by producing a sequence of tuples.

1
2
3
4
5
6

let parseRow x = 
  let cols = String.split ['\t'] x
  List.nth cols 6, List.nth cols 7

(* y : seq<string*string> *)
let y = ExcelData |> Seq.map parseRow

Or you could create a record type for a row to give the columns names.

1
2
3
4
5

type Row = { column6 : string; column7 : string }

let parseRow x = 
  let cols = String.split ['\t'] x
  { column6 = List.nth cols 6; column7 = List.nth cols 7}

Hope this helps.

By on 2/6/2008 5:03 AM ()

gneverov,

Thanks for both of your most recent responses. As I wrote to Robert I am very appreciative of the time that you've given me and am sort of amazed I get any responses at all!

With regard to the speed of finding an element of a List. Is there another commonly used structure in F#, more like a hash table that can quickly find the element you're looking for?

With regard to the solution you provided, that's more like what I had imagined, although I was quite far from getting there. Robert's solution also worked very well and for me and was terrific because I learned another way of looking at these things. An embarrassment of riches with regard to approaches.

At this point, since I'm experimenting (although with real data), I'm not sure whether I want separate arrays or one sequence of tuples. I'll think I'll take my next few steps and see how it goes.

Again, thanks very much for all of your help.

Mitchell

By on 2/6/2008 6:33 PM ()

The conventional data structure for O(1) lookup is an array. But whether arrays or lists are better depends on the application: if you structure your code to be "stream-processing" style then you never need to do an nth element lookup on a sequence.

By on 2/7/2008 1:20 AM ()

My asumption had been that you wanted to seperate list, if want to keep the data together gneverov solution is great. However if you're looking for a hash table like structure then you have plenty of choice in F#. You can either use a "Map" an functional imutable data structure, when new items are added to a Map a new version of the map is created. Alteratively you can use a .NET dictionary a sort of hash table with strong typing - thanks to generics. Both options are shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let map = 
    ExcelData 
    |> Seq.fold
        (fun (acc:Map<string, string>) x -> 
            let cols = x.Split([|'\t'|])
            acc.Add(cols.[0], cols.[1])) 
         Map.empty 

open System.Collections.Generic

let dict = 
    let dict = new Dictionary<string, string>()
    ExcelData 
    |> Seq.iter
        (fun x -> 
            let cols = x.Split([|'\t'|])
            dict.Add(cols.[0], cols.[1]))

One word of warning - both implementations will fail if the "keys" (the first column) is not unique, it should be relatively easy to modify the solution to deal with repeated keys.

Cheers,
Rob

By on 2/7/2008 1:04 AM ()

Rob,

I guess at this point I'm really not sure how I'll be approaching the problem I'm looking at. I want to analyze data that comes from one of our reporting systems. This is, really, experimental on my part. It's an attempt to learn F# in a way that may make it applicable to my job.

I do have a few questions about your latest post. Up till now I've been using String.split and supplying a character to split by. In your post your using x.Split – I didn't know you could do that, although I shouldn't be surprised. However you had to use |'\t'| instead of just '\t'. Could you explain that a little?

Also, what does the Map.empty do at the end? Does this somehow help with garbage collection as acc keeps getting replaced? Along those lines, are the "older" versions of acc no longer accessible so the memory can be released?

I haven't yet spent much time with your second implementation using Dictionary. I see that this uses Seq.iter instead of Seq.fold. I'm still a fuzzy on "iter" vs "map" vs "fold" (in some cases). Something I'll spend some time on.

Again, thanks for all of your help. Oh, have a great time at Tech Days in Paris – sounds like fun!

Mitchell

By on 2/7/2008 8:25 AM ()

Hi Michell,

It’s quite important to understand the difference between map fold and iter. Here is a quick guide:

map – this transforms a list or sequence into a new list of sequence. It takes a function of type ‘a -> ‘b mean a function takes a value of type ‘a and returns a value of type ‘b. This function is that applied to every item in the sequence and the results of the function form the new sequence. Typical example of a map would be taking a list of integers and multiplying them all by 2 or transforming them into a list of strings.

iter – this applies a function to every item in the sequence. The function has type ‘a -> unit, meaning it takes a value of type ‘a but has no return result, so to be useful the function has to have a side effect. A typical example of iter would be to print a sequence of strings to the console.

fold – this is used to create summaries of lists. It takes a function of type ‘a -> ‘b -> ‘a, meaning a function with two parameters the first is of type ‘a and is the accumulator, the second of type ‘b is the value from the list, it must return a value of the same type as the accumulator. Folding functions also require an initial value for the accumulator (this is why we pass an empty map at the start of the end of the fold function). A typical example of using fold would be to calculate the total of a list of integers.

So we use fold to create the Map because we are creating a summary of the list, and because Map is a immutable data structure, when add items to it we don’t change it we create a new version with the extra items in place. Here’s a new version with extra comment:

1
2
3
4
5
6
7
8
9
10
11
12

let map = 
    ExcelData 
    |> Seq.fold
        // first parameter "acc" is the accumulator
        // the second parameter "x" is the item from the list
        (fun (acc:Map<string, string>) x -> 
            let cols = x.Split([|'\t'|])
            // create a new version of the map
            // with the item added
            acc.Add(cols.[0], cols.[1])) 
         // pass in an empty map
         Map.empty

On the other hand diction is a mutable data structure so we can use iter, as adding items to it is a side effect.

Oh and concerning the vertical bars:

1
2

let l = [ 1; 2; 3; ] // this is a list
let a = [| 1; 2; 3; |] // this is an array

but don’t worry about this too much for now.

By on 2/8/2008 12:47 AM ()

Rob,

Thanks for the clear explanantion. At this point I'm still having trouble with the very terse descriptions in the documentation such as <i>'a -> unit<i>. Your descriptions, e.g., <i>"It takes a function of type ‘a -> ‘b -> ‘a, meaning a function with two parameters the first is of type ‘a and is the accumulator, the second of type ‘b is the value from the list, it must return a value of the same type as the accumulator."<i> are much easier for me to understand. Thanks very much! Mitchell

By on 2/8/2008 6:38 AM ()

Sorry about the slow response, I completely over looked this post.

Basically you have to explicitly traverse the list and use two accumulators to hold the results:

1
2
3
4
5
6
7
8
9
10
11

let split l =
    let rec loop l acc1 acc2 =
        match l with
        | hd :: tail -> 
            let col1 = List.nth (String.split ['\t'] hd) 1
            let col2 = List.nth (String.split ['\t'] hd) 2
            loop tail (col1 :: acc1) (col2 :: acc2) 
        | [] -> acc1, acc2
    loop l [] []
    
let bb = ExcelData |> List.of_seq |> split
By on 2/6/2008 3:17 AM ()

Robert,

Thanks for the help. Actually I appreciated the 1 day pause, I was having trouble keeping up anyway. Seriously though, I am extremely appreciative of the help you and others have been giving me and hope that I'm not becoming too much of a pest.

Your suggestion worked very well. It did leave me with a string list * string list, which forced me to pay a little more attention to what I was working with.

I'm still thinking in more of an imperative way, but gradually I'm seeing this a little more clearly. I liked the idea of pulling off the head each time and working with that. Then it naturally leads to recursion.

Thanks again,

Mitchell

By on 2/6/2008 6:15 PM ()

gneverov,

Okay, I think I understand do I have this right?

A sequence is a linked list, so that any searching is going to be O(n). If you eventually search for every element, I guess this becomes something like n/2 on average. In my original code I went into each element, one at a time, split the string and extracted the 7th element. This then got assembled, one by one into an array. So I have n elements times n/2 elements to be searched (approximately).

Your code goes into the sequence and Splits and extracts the data from the string one at a time, but without having to do any searching. Then there's the Seq.to_array.

Does the Seq.to_array place the extracted element into the array as the linked list is being processed, or is there some temporary sequence that gets created and then moved into an array?

In any case is seems that your vastly improved routine is O(n), because it still has to go through n elements. So this seems that my original routine will take something like 25000/2 longer than yours. Is that right?

Mitchell

By on 2/4/2008 8:51 AM ()

Sorry for the slow response. Yes, you have a correct understanding of how your code was working.

A seq is like a linked list, but it is not necessarily one. In this case the ExcelData seq reads its elements from a file; it doesn't store anything in memory. So when it is searching it for the nth element, it is searching the file on disk and not an in-memory data structure.

Seq.to_array is an O(n) operation. It does create temporary data structures though. Check the fslib source if you <i>really<i> want to know what it does.

By on 2/6/2008 4:47 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper