1.0k
views2
comments

I am wanting to use an appropriate F# data structure that is optimised for lookups (insertion / updates are not so important) for the following data.

I have several tens of thousands of records of type X. Lets suppose the records have 7 fields of various types named A,B,C,D,E,F,G and that a subset of these fields will be used for lookups, e.g. A B and C.

So of the thousands of objects of type X in the data structure I want to query:

"get all records where B = 24"
or
"get all records where B = "24" and C = false
or
"get all records where A = 12"

and the result of this query would be a list/array of X's that match. Note: the types of query are limited, there are just a handful of ways I'll be querying the data like above.

Any ideas on what would be appropriate for this?

Would a simple list of tuples with the queryable fields broken out in the tuple and the last element being the full object i.e (X.A , X.B , X.C , X) and then just filtering with a pattern match be the best way (bearing in mind I will have tens of thousands of items)?

e.g. match (a,b,c,x) with
| _ , 24 , _ , x -> x

match (a,b,c,x) with
| _ , 24 , false , x -> x

Another way I was considering is to implement a pre-prepared tree structure for each different type of query. e.g. corresponding to the 3 queries above: a tree of Root -> B[] -> X[], and another of Root -> B[] -> C[] -> X[] and finally Root -> A[] -> X[]

Any ideas much appreciated

The answer is a big "it depends" :)

Until recently I'd of said stick your data in relational database and let that take the strain. While this is still a good option, we now entering the post relational database era so perhaps keeping your own data structures in memory is okay.

With any kind of list structure your pretty much always going to have to scan the whole list to answer your queries. Even with tens of thousands of records this is probably still going to be pretty quick on a modern machine, though you don't say what your perf targets are so it's hard to know if it will quick enough. As you say you could implement some kind of sorted tree structure that would give you better search times but would be harder to implement.

The two options are roughly equivalent to a table in a DB with or without indexes, so perhaps a DB isn't such a bad option after all.

I'd probably go for a simple list of tuples, if that was quick enough stick with that, otherwise do something cleverer.

Cheers,

Rob

By Robert on 11/3/2008 7:11 AM (permalink)

Thanks Rob, I have done a compromise solution based on what you suggested with a Dictionary. the values are list of type X but the key is a tuple where each item is an Option type.

i.e. the key is (Some(12) , None , Some (24) , None , None)

and then I just insert each object several times for the different lookup combinations. This seems to be quite quick and does the job correctly. From my experience heavily transient data does not suit databases at all.

One other thing I was trying and seemed to have hit a roadblock on with the F# type system is to have a sort of higher order function tree where each level of the tree has a different key on the path to the leaves, and the leaf nodes contain a list of objects of type X.

What I tried to do was: let mytree = CreateTree [fn1 ; fn2 ; fn3 ]

the argument to CreateTree is a list of functions of type X -> 'a

So assuming X is an object with fields A,B,C,D,E then fn1 might be GetA, fn2 might be GetC and fn3 might be GetE.

So when inserting an item into the tree it would call each of fn1 fn2 and fn3 in turn to determine exactly which leaf node the item should be inserted into. In the example above all X's that have the same A,C and E values would all be stored in the same list at the leaf.

However I was unable to work out how to program the tree to work in the general case where the number of functions passed to CreateTree is variable.

By scherzo on 11/3/2008 4:14 PM (permalink)

Topic tags

Built with WebSharper

Home

Answers

Events

Courses

Groups and Conferences

Blogs

Jobs

Developers

Topic tags