2009/3/11 Manlio Perillo <[email protected]>: > Hi. > > I'm still working on the Netflix Prize; now I have managed to implement a > parsing function for the qualifying data set (or quiz set). > > The quiz set is in the format: > > 1: > 10 > 20 > 30 > 2: > 100 > 200 > 3: > 1000 > 2000 > 3000 > 4000 > 5000 > > > Where 1, 2, 3 are movie ids, and the others are user ids. > > The parsing program is at: > http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2300 > > > The program reads the file using lazy IO. > One of the feature I want is, for the quiz function, to be a *good > producer*. > > I'm quite satisfied with the result (this is the first "complex" parsing > function I have written in Haskell), and I have also managed to avoid the > use of an accumulator. > > However I'm interested to know it there is a more efficient solution. > > > The qualifying.txt file is 51MB, 2834601 lines. > > On my laptop, the function performance are: > > real 1m14.117s > user 0m2.496s > sys 0m0.136s > > CPU usage is about 3%, > system load is about 0.20, > memory usage is 4956 KB. > > > What I'm worried about is: > > quiz' ((id, ":") : l) = (id, quiz'' l) : quiz' l > quiz' ((id, _) : l) = quiz' l > > > the problem here is that the same elements in the list are processed > multiple times. > > > I have written alternate versions. > The first using foldl > http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2303 > (that, however, builds the entire data structure in memory, and in reverse > order) > > The latter using foldr > http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2304 > (that, however, is incorrect and I'm unable to fix).
Hi, I suggest you try an alternative strategy. That altenrative strategy is twofold, just like you have quiz' and quiz'. This alternate strategy avoid pattern matching on strings (which would be cumbersome for a bit more complex syntax). So you have to write two functions : one try to parse an 'id:' from the string. It either succeed and returns the Int value of the id, or it fails. You can use Either to encode success and failure. Furthermore that function has to return the remaining string (which is the same as received upon failure). The second function do a similar thing, this time failing on 'id:'. (And it still returns alos the remainstring). If you're familiar with the State monad, you can write the above two functions by using the string as the state. Now, given those two functions, try to apply them on your input string, feeding the next function application with the resulting string of the current application. What I proposed here is the very basics of a natural and very used parsing technique (google for parser combinators). That technic will scale well for more complex inputs, and, I believe, should provide you with sufficient performance. Cheers, Thu _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
