¿Cómo se cruzan dos listas en OCaml?

Question

Cuando tengo dos listas en OCaml, por ejemplo

e1 = [3; 4; 5; 6; 7] 

y

e2 = [1; 3; 5; 7; 9] 

¿Hay una manera eficaz de conseguir la intersección de esas dos listas? es decir .:

[3; 5; 7] 

Debido a que no me gusta el escaneo de cada elemento en la lista de E2 para cada elemento en la lista de e1, creando así una gran Oh de orden n^2.

Answer 1

Como Franck y Rémi dicho, la conversión de sus listas de conjuntos (de módulo stdlib Set) Cuesta N log (n), y a continuación, establece proporciona una implementación lineal de intersección. Franck también mencionó la alternativa equivalente para ordenar las listas y luego recorrerlas de forma sincronizada. Estos son más o menos los mismos (y, por cierto, en ambos casos debe ser capaz de proporcionar un pedido total de los elementos en sus listas).

Si intersecciones son una parte importante de su algoritmo y que quieren que sean más rápida en el caso de dos conjuntos de elementos que son sólo ligeramente diferente, es necesario cambiar a una estructura de fusionarsetales como árboles Patricia. Ver archivos pt* en http://www.lri.fr/~filliatr/ftp/ocaml/ds/.

Si necesita que la intersección sea rápida en todos los casos, tiene la posibilidad de utilizar árboles de hash-consed Patricia. El hash-consing ayuda a reconocer subárboles estructuralmente idénticos, y ayuda a construir cachés eficientes para operaciones previas al hacer la comparación barata.

Los árboles de Patricia no pueden usar un tipo arbitrario como clave (normalmente se presentan con ints como teclas). Pero a veces puede evitar esta limitación al numerar en la creación cada valor que pretenda usar como clave.

Answer 2

No sé OCaml (sintaxis-wise), pero en general se puede hacer esto de dos maneras:

1. Si su lenguaje tiene soporte para un Set-estructura de datos, a continuación, convertir las dos listas en conjuntos y usa la operación de intersección de conjuntos.

2. Más en general: Ordene ambas listas, luego escanee las listas ordenadas, lo que hace que encontrar los duplicados sea mucho más eficiente. Tomas n log (n) para clasificar y puedes encontrar los duplicados en tiempo lineal.

Answer 3

Mi OCaml no es la mejor, pero esta función hackeado juntos, que se cruzará listas ordenadas:

let rec intersect l1 l2 = 
    match l1 with [] -> [] 
     | h1::t1 -> (
      match l2 with [] -> [] 
       | h2::t2 when h1 < h2 -> intersect t1 l2 
       | h2::t2 when h1 > h2 -> intersect l1 t2 
       | h2::t2 -> (
       match intersect t1 t2 with [] -> [h1] 
        | h3::t3 as l when h3 = h1 -> l 
        | h3::t3 as l -> h1::l 
      ) 
     );; 

que deberán estar en un tiempo O (n + m). Básicamente, verifica el primer elemento de cada lista. Si son iguales, almacena el resultado de la llamada recursiva en sus colas, y luego verifica si el encabezado del resultado almacenado es igual a los encabezados de las listas. Si no lo está, lo inserta, de lo contrario es un duplicado y lo ignora.

Si no son iguales, solo avanza el que sea más pequeño.

Answer 4

Como @Frank sugirió, puede utilizar conjuntos para resolver este problema, aunque no es la mejor respuesta nunca, pero aquí hay una lista de código corto que muestra cómo esto podría lograrse en OCaml:

module Int_set = Set.Make (struct 
          type t = int 
          let compare = compare 
          end);; 

(* iters through a list to construct a set*) 
let set_of_list = List.fold_left (fun acc x -> Int_set.add x acc) Int_set.empty;; 

let e1 = [3; 4; 5; 6; 7];; 
let e2 = [1; 3; 5; 7; 9];; 

let s1 = set_of_list e1;; 
let s2 = set_of_list e2;; 

(*result*) 
let s3 = Int_set.inter s1 s2;; 


(*testing output*) 
Int_set.iter (fun elt -> print_int elt;print_string "\n") s3;; 

la salida es:

3 
5 
7 
- : unit =() 

Answer 5

Si sus listas solamente contiene números enteros de un tamaño limitado, también hay una solución en O (n):

1.) crear una matriz de valores booleanos del tamaño de y El valor entero más grande más 1 en sus listas originales (p. en tu ejemplo '9 + 1'); establecer todos los campos a falso;

let m = Array.create 10 false

->[|false; false; false; false; false; false; false; false; false; false|]

2.) iterar sobre la primera lista: Para cada elemento se encuentra con, establezca el valor booleano con el respectivo desplazamiento a 'verdadero'; en su ejemplo este cedería

List.iter (fun x -> m.(x) <- true) e1

->[|false; false; false; true; true; true; true; true; false; false|]

3.) de filtro sobre la segunda lista, manteniendo sólo los elementos de los cuales el campo correspondiente en la matriz es cierto

List.filter (fun x -> m.(x) = true) e2

->[3; 5; 7]