Menu
When I have two lists in OCaml, for example
e1 = [3; 4; 5; 6; 7]
and
e2 = [1; 3; 5; 7; 9]
Is there an efficient way to get the intersection of those two lists? I.e.:
[3; 5; 7]
Because I don't like scanning every element in list e2 for every element in list e1, thus creating a big Oh of order n^2.
217
map when you'd like to see something done to each element in a list, use List. iter when you'd like to see something done with each element in a list.
rev ( List. map f l) , but is tail-recursive and more efficient. filter_map f l applies f to every element of l , filters out the None elements and returns the list of the arguments of the Some elements.
To perform the intersection of two lists in python, we just have to create an output list that should contain elements that are present in both the input lists. For instance, if we have list1=[1,2,3,4,5,6] and list2=[2,4,6,8,10,12] , the intersection of list1 and list2 will be [2,4,6] .
Just have a function that takes the original list and a empty list. Build up the empty list(with the first half of the original list) until you reach the halfway point and then use the remainder of the original list and the built up empty list to generate your pairs.
As Franck and Rémi said, converting your lists to sets (from stdlib module Set) costs n log(n), and then Sets provides a linear implementation of intersection. Franck also mentioned the equivalent alternative to sort the lists, and then traverse them in a synchronized way. These are roughly the same (and by the way, in both cases you need to be able to provide a total ordering on the elements in your lists).
If intersections are an important part of your algorithm and you want them to be faster in the case of two sets of elements that are only slightly different, you need to switch to a mergeable structure such as Patricia trees. See files pt* in http://www.lri.fr/~filliatr/ftp/ocaml/ds/ .
If you need intersection to be fast in all cases, you have the possibility to use hash-consed Patricia trees. Hash-consing helps to recognize structurally identical sub-trees, and help to build efficient caches for previous operations by making comparison cheap.
Patricia trees can not use an arbitrary type as key (typically they are presented with ints as keys). But you can sometimes work around this limitation by numbering at creation each value you intend to use as a key.
160
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
