CODEWITHSUNDEEP
listpositionocamlelement
moumoute6919
moumoute6919

Reputation: 2416

Position of an element in a list

What is the fastest way to get the position of an element in a list of element in OCaml? I know how to get the "nth" position of an element in a list but I would like to know how to get the position of this element if I already know the value.

Upvotes: 2

Views: 3071

Answers (3)

Chris
Chris

Reputation: 36581

If the elements in a list are all unique, you may wish to convert to a map, where the elements are keys and the indices are values. The creation of the map is O(n), but subsequently, lookups of indices are O(log n).

E.g.

module IntMap = Map.Make (Int)

let lst = [34; 56; 17; 2; 0; 99]
let indexed_lst = List.mapi (fun x i -> (i, x)) lst

let map = 
  List.fold_left 
    (fun m (k, v) -> IntMap.add k v m) 
    IntMap.empty 
    indexed_lst

let idx_of_2 = IntMap.find 2 map

Now idx_of_2 is 3.

This is more expensive than a linear search for very low numbers of lookups, but increasingly less expensive as the number of lookups increases.

If numbers in the list are not unique, we could generate a map with lists of indices.

let lst = [34; 56; 17; 2; 0; 99; 2; 34]
let indexed_lst = List.mapi (fun x i -> (i, x)) lst

let map =
  List.fold_left 
    (fun m (k, v) -> 
       IntMap.update 
         k 
         (function 
          | None -> Some [v] 
          | Some vs -> Some (v::vs)) 
         m) 
       IntMap.empty 
       indexed_lst
  |> IntMap.map List.rev

let idx_of_2 = IntMap.find 2 map

In this situation, idx_of_2 would now be [3; 6].

Upvotes: 0

David Monniaux
David Monniaux

Reputation: 2004

let rec findi_rec base p l = 
  match l with 
    [] -> raise Not_found 
  | h::_ when p h -> base 
  | _::t -> findi_rec (base+1) p t;;

let findi p l = findi_rec 0 p l;;

As:

# findi (fun x -> x=4) [1;9;3;2;1;4;5;7];;
- : int = 5

Upvotes: 0

Jackson Tale
Jackson Tale

Reputation: 25812

I believe the fastest is way is the most usual way:

  1. Scan the list
  2. Return the position if you hit the desired element
  3. If never hit, then it is the worst case and entire list is scanned.

The time complexity will be O(N)

let index_of e l = 
  let rec index_rec i = function
    | [] -> raise Not_found
    | hd::tl -> if hd = e then i else index_rec (i+1) tl
  in
  index_rec 0 l

Upvotes: 11

Related Questions