2

I'm currently using the following function:

 let rec combine xss = function
  | [] -> []
  | ys::yss -> List.map ((@) ys) xss @ combine xss yss

It is combining two lists of lists in the following way:

combine [["x"];["a"];["c"]] [["u"];["h"];["p"]]

gives this result:

[["u"; "x"]; ["u"; "a"]; ["u"; "c"]; ["h"; "x"]; ["h"; "a"]; ["h"; "c"];
["p"; "x"]; ["p"; "a"]; ["p"; "c"]]

This is totally as I want it, however.. I'm currently using this method a lot and the data has become so vast that the program currently aren't able to run.
Is there a way for this to run fast for lists of lists? The lists contain about 1100 elements and the lists inside contain about 10 elements each. Just a little speed up is appreciated!

EDIT:

The above listed example might not be that good, it was just to show what it is doing. The data I'm actually using combines lists of lists of this predifined type:

    type atom = ANum of float | AExponent of string * int 
              | ADiv of atom list list * atom list list | ARoot of expr * int

The expr type used here is of no interest for the combining method.

Specifically in my code I could be doing something as terrible as (in a match):

     | ADiv(all3,all4) -> ADiv((combine all2 all3)@(combine all1 all4),combine all2 all4)

With allx being atom list list as the above type states.

Does any of this explain it enough?

zniwalla
  • 367
  • 4
  • 17
  • 3
    Are you just trying to create a powerset? If so there are plenty of duplicates on SO – John Palmer May 23 '16 at 11:13
  • Oh, that's the term of it? Will try to search for it. – zniwalla May 23 '16 at 11:14
  • It's not a true powerset I'm going for - I need two lists combined as some kind of a powerset, not just one combined with itself. My function will actually create a powerset if the two arguments are identical.. but that's not the needed output. – zniwalla May 23 '16 at 11:20
  • 4
    Sorry, got terms mixed up, meant cartesian product - http://stackoverflow.com/questions/6198168/projecting-a-list-of-lists-efficiently-in-f – John Palmer May 23 '16 at 11:21
  • Alright, cycled through the cartesian product posts (which are all cross linking to each other) and it is indeed something in that lane I try to achieve. I found the best match in the link you commented. I've implemented the accepted answer's `cartesian2`, but it's only running as fast as the above code. It's also not _excactly_ doing what I want. – zniwalla May 23 '16 at 11:56
  • 2
    @zniwalla You should see an improvement when you move away from using `@` for the "outer" result concatenation. The function isn't even tail recursive. Also, maybe you could specify more precisely what you want? Do you really need to build a huge list and throw it onto the heap and GC, or could you maybe iterate over the two original lists? Why do you use lists of strings to represent only single characters? If you really need speed, these things can make quite a difference, so some more information about the data, or how to create example data, could improve potential answers. – Vandroiy May 23 '16 at 12:07
  • 2
    @zniwalla think if you want this to remain open you really need to explain how this is different - maybe show some specific timings for your actual case (as well as how to make them so we can reproduce to try and improve)? – John Palmer May 23 '16 at 12:13
  • I've done some experiments and I'm no longer sure about the list concatenation being the main issue here. I'm giving up on answering this for now, there are just too many unknowns. It looks to me as if this is burning through CPU cache by the bucket; in my tests, iterating over a sequence expression of the desired result is more than twice as fast as creating a structure to store it, even as an imperatively built array. So I'd say that if there is some way to get the memory footprint down, give it a try. – Vandroiy May 23 '16 at 13:45
  • I've edited my post now - maybe it clarifies things a little? – zniwalla May 23 '16 at 16:36
  • 1
    @zniwalla - please actually post a complete, runnable example, that we can just cut/paste. – John Palmer May 24 '16 at 03:39

0 Answers0