Discussion :

[bumbolol]

Disons que j'ai une liste de variables, que chaque variable peut être de plusieurs types, que seul le type 'Type1' m'interesse, et que le type 'Type1' contient un champ nommé 'val_int' qui est un entier.

Je veux construire une chaîne de caractères contenant tous les entiers 'val_int' des 'Type1' de la liste.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
type 'a ref = { mutable contents: 'a }
 
  method create_string list =
    let string = { contents = "" } in
    List.iter (fun var ->
      match var with 
      | Type1(var_info) ->
          string.contents <- string.contents
                          ^ (fprintf_to_string "%i " var_info.val_int)
      | _ -> ()) list;
    string.contents

Voici le code que j'ai pondu, il marche.

Seulement dans ma précédente question, on m'a fait savoir qu'éviter d'utiliser des mutables, si possible, c'était mieux.

Je voudrais donc savoir:
- Est-ce que c'est un cas où il faut utiliser un mutable ? Si ce n'est pas le cas, comment faire pour s'en passer ?
- Indépendamment du mutable, est-ce bien comme ca qu'il faut écrire ce genre de code ? Honnêtement, j'ai commencé par faire une boucle for ^^;; Quid de la vitesse, peut-on écrire ca de manière plus optimisée ?

[alex_pi]

Déjà, pourquoi tu définis ton type ref à la main ?? Il y en a un de base dans caml, et il est pas si mal hein

Ensuite, je pense que ce que tu veux faire, c'est un "List.fold_left". Et si ça te fait peur de concaténer des string, il faut un buffer.

[LLB]

Pour ma part, j'écrirais quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let create_string list =
  let rec build = function
    | [] -> []
    | Type1 {val_int=i} :: l -> string_of_int i :: build l
    | _::l -> build l
  in String.concat " " (build list)

Le résultat est presque le même (sauf que mon code ne met pas l'espace finale). Test sur une liste de 30000 éléments : ma fonction est 10 fois plus rapide que la tienne.

Avec une bibliothèque plus fournie que celle de Caml, on peut tout faire sans récursion explicite (List.filter_map dans Batteries Included ; List.choose dans F#) et de façon plus élégante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let create_string list =
    let filter = function Type1 {val_int=i} -> Some (string_of_int i) | _ -> None in
    list |> List.filter_map filter |> String.concat " "

[gasche]

Il faut bien promouvoir son propre travail :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

String.concat " " [? List : string_of_int i | Type1 {val_int=i} <- List : list ]

[Cacophrene]

Bonjour !

C'est mon premier message sur ce forum, et en plus on y parle de Caml, et en plus on y trouve des gens connus (trève de "en plus")

Si j'ai bien compris le but c'est de prendre une liste de valeurs un peu siouxe et d'extraire les entiers sous forme de chaîne. Pourquoi pas ceci alors ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
let to_string =
  let buff = Buffer.create 16 in
  fun l ->
    Buffer.reset buff;
    List.iter (function
      | Type1 x -> Printf.bprintf buff "%i " x.val_int
      | _ -> ()
    ) l;
    Buffer.contents buff

Fonction tail-rec sans surprise.

Cordialement,
Cacophrène

[alex_pi]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
let to_string =
  let buff = Buffer.create 16 in
  fun l ->
    Buffer.reset buff;
    List.iter (function
      | Type1 x -> Printf.bprintf buff "%i " x.val_int
      | _ -> ()
    ) l;
    Buffer.contents buff

Je sais que OCaml n'est pas "multithread", mais quel intéret y a-t-il à utiliser le même buffer pour tous les appels de la fonction ? On doit gagner un pouillème de miliseconde, et le jour où on peut lancer deux fois "to_string" en parallèle, on se retrouve avec un comportement aléatoire !

[alex_pi]

Il faut bien promouvoir son propre travail :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

String.concat " " [? List : string_of_int i | Type1 {val_int=i} <- List : list ]

Quelle extension de syntaxe ?

[Cacophrene]

Salut !

Quelle extension de syntaxe ?

Peut-être les list comprehension « implémentées-cachées » de camlp4, ou un truc dans le même genre, mais fait maison... Non ?

Cordialement,
Cacophrène

[gasche]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

String.concat " " [? List : string_of_int i | Type1 {val_int=i} <- List : list ]

Quelle extension de syntaxe ?

C'est pa_comprehension de Batteries ( lien vers la doc HTML des extensions ). C'est encore très jeune.

Sinon tu peux effectivement utiliser Camlp4ListComprehension qui est en standard dans OCaml (camlp4o -parser Camlp4ListComprehension.cmo) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

String.concat " " [ string_of_int i | Type1 {val_int i} <- list ]

Ça évite de spécifier les "List" mais en conterpartie ce n'est pas modulaire par rapport à la structure de donnée (pa_comprehension permet d'avoir facilement des Array ou whatever (Enum par défaut) en entrée ou en sortie).

Un jour, une combinaison sublime avec le projet pa_do permettra (j'espère) de faire directement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

List.[? string_of_int i | Type1 {val_int i} <- list ]

[bumbolol]

Pour ma part, j'écrirais quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let create_string list =
  let rec build = function
    | [] -> []
    | Type1 {val_int=i} :: l -> string_of_int i :: build l
    | _::l -> build l
  in String.concat " " (build list)

Le résultat est presque le même (sauf que mon code ne met pas l'espace finale). Test sur une liste de 30000 éléments : ma fonction est 10 fois plus rapide que la tienne.

Bon bah du coup j'ai opté pour cette solution là, merci bcp ^^

Tant que j'y suis, j'ai une autre chaîne à construire, cette fois je recois 2 listes, et je dois concaténer tous les couples de var_int.

En utilisant la même approche que ci-dessus, j'obtiens:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let create_string list1 list2 =
  let rec build1 = function
    | ([],var) -> []
    | (Type1 {val_int=i} :: l,var) -> string_of_int (i,var) :: build1 (l,var)
    | (_::l,var) -> build1 (l,var)
  in let rec build2 = function
    | [] -> []
    | Type1 {val_int=i} :: l -> String.concat " " (build1 (list1,i)) :: build2 l
    | _::l -> build2 l
  in String.concat " " (build2 list2)

Est-ce que par hazard il y aurait encore plus rapide/élégant (avec juste les libs Ocaml standard) pour écrire cela ?

En tout cas merci à tous pour les suggestions, cela m'en apprend beaucoup.

[Cacophrene]

Re !

@bumbolol : Ceci peut-être (code non testé) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
open Printf
 
let to_string2 l1 l2 =
  let buff = Buffer.create 16 in
  let to_string i = List.iter (function 
    | Type1 x -> bprintf buff "%i,%i " i x.val_int
    | _ -> ()
  ) l1 in List.iter (function Type1 x -> to_string x.val_int | _ -> ()) l2;
  Buffer.contents buff

Attention : ce n'est peut-être pas ce que tu veux. Comme ton code utilise "string_of_int (i,var)" qui est incorrect (problème manifeste de typage) , j'ai essayé d'interpréter (avec plus ou moins de succès) d'après le texte.

@alex_pi : Exact ! Où avais-je la tête... c'est sûr que pour observer un gain il faut une situation qui maximise la création de nouveaux buffers (petites listes), et non une autre où l'on en crée très peu (grandes listes). Vien bu

@+
Cacophrène

[bumbolol]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let create_string list1 list2 =
  let rec build1 = function
    | ([],var) -> []
    | (Type1 {val_int=i} :: l,var) -> string_of_int_couple (i,var) :: build1 (l,var)
    | (_::l,var) -> build1 (l,var)
  in let rec build2 = function
    | [] -> []
    | Type1 {val_int=i} :: l -> String.concat " " (build1 (list1,i)) :: build2 l
    | _::l -> build2 l
  in String.concat " " (build2 list2)

Aheum... je viens de me rendre compte que j'ai oublié un morceau important, je dois obtenir des listes de chaines de couple d'entier unique, en gros je ne dois concaténer que les éléments uniques de (build2 list2).

Donc soit:

- à la place de 'String.concat " " (build2 list2)' je fais 'let stripped_list = strip (build2 list2) in String.concat " " stripped_list' où trip est une fonction qui reste à écrire et qui prend une liste et retourne cette liste avec juste des elements uniques (pas bien dur à faire...).

- dans 'build2' je remplace 'String.concat " " (build1 (list1,i)) :: build2 l' par quelque chose qui me permettent de n'ajouter 'String.concat " " (build1 (list1,i))' de manière unique, mais je vois pas du tout quoi ^^

[Cacophrene]

Salut !

Je récapitule ce que j'ai compris :
1. Tu as deux listes l1 et l2.
2. On sélectionne tous les éléments uniques de la forme Type1 {val_int = i} dans l2
3. On crée la chaîne de couples formés par i et tous les j des éléments de l1 qui sont de la forme Type1 {val_int = j}.

Si c'est ça, voici une solution :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
open Printf
 
module IntSet = Set.Make (
  struct
    type t = int
    let compare = compare
  end
)
 
let to_string2 l1 l2 =
  let buff = Buffer.create 16 in
  let to_string i = List.iter (function 
    | Type1 x -> bprintf buff "%i,%i " i x.val_int
    | _ -> ()) l1 in
  let rec loop set = function
    | [] -> Buffer.contents buff
    | Type1 {val_int = i} :: l -> if IntSet.mem i set then loop set l
      else (to_string i; loop (IntSet.add i set) l)
    | _ :: l -> loop set l 
  in loop IntSet.empty l2

Principe : Au fur et à mesure qu'elle progresse, la fonction loop stocke les entiers déjà passés en revue dans un set (une liste peut tout aussi bien faire l'affaire... selon les exigences de performance de la fonction mem). Si l'entier est unique, il est passé à la fonction to_string qui complète la liste.

Et puis au besoin on peut même abstraire to_string2 pour choisir les fonctions et la valeur initiale de set, mais ça devient vraiment très lourd :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
let to_string2 ~mem ~add ~ini l1 l2 =
  let buff = Buffer.create 16 in
  let to_string i = List.iter (function 
    | Type1 x -> bprintf buff "%i,%i " i x.val_int
    | _ -> ()) l1 in
  let rec loop set = function
    | [] -> Buffer.contents buff
    | Type1 {val_int = i} :: l -> if mem i set then loop set l
      else (to_string i; loop (add i set) l)
    | _ :: l -> loop set l
  in loop ini l2
 
(* Exemple avec IntSet. *)
let to_string2_set = to_string2 
  ~mem:IntSet.mem 
  ~add:IntSet.add 
  ~ini:IntSet.empty

Très logiquement ça nous donne la signature suivante :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
val to_string2 :
  mem:(int -> 'a -> bool) ->
  add:(int -> 'a -> 'a) -> 
  ini:'a -> t list -> t list -> string

Ultime question que je me pose : les entiers de l1 doivent-ils aussi être uniques ? Si c'est le cas, il faut réécrire to_string dans mon code. Sinon, voici ce que ça donne sur un exemple bidon dans l'interpréteur :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
# let x = [Type1 {val_int = 2}; Type1 {val_int = 2}; Type1 {val_int = 3}];;
val x : t list =[Type1 {val_int = 2}; Type1 {val_int = 2}; Type1 {val_int = 3}]
# to_string2_set x x ;;
- : string = "2,2 2,2 2,3 3,2 3,2 3,3 "
#

Cordialement,
Cacophrène

[bumbolol]

Déjà, pourquoi tu définis ton type ref à la main ?? Il y en a un de base dans caml, et il est pas si mal hein

Parce que j'ai vu ca dans un code source sur le net et que j'ai recopié en me disant "tient c'est pratique, bizarre que ca soit pas par default dans le language", ah bah si en fait...

Il faut bien promouvoir son propre travail :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

String.concat " " [? List : string_of_int i | Type1 {val_int=i} <- List : list ]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let create_string list =
    let filter = function Type1 {val_int=i} -> Some (string_of_int i) | _ -> None in
    list |> List.filter_map filter |> String.concat " "

Voilà deux solutions bien compactes je crois que je vais éviter de rajouter à mon programme d'autre dépendance que la librairie de parsing pour l'instant.

@Cacophrene
En fait, pour vous demander de l'aide, j'ai viré dans mon problème tout ce qui n'avait aucune pertinence avec mes questions, car en fait, ce n'est pas un int que je convertis en string, mais une structure complexe. La librairie de parsing fournis une fonction toute prête pour ca mais il n'est pas possible de connaître à l'avance la taille maximale retournée par cette dernière.