Discussion :

[GnuVince]

Bonjour à tous,

dans le cadre de mon cours d'informatique théorique, je me suis codé un petit simulateur de machines de Turing en OCaml. Le code est très simple et petit (55 lignes de code). Pour mon plaisir personnel, j'ai codé un simulateur identique en Java. Pour une machine de Turing qui nous a été donnée en devoir, mon simulateur OCaml termine en 5.1s et celui en Java termine en 2.0s sur ma machine x64; sur ma machine 32 bits, le simulateur en OCaml prend 9 secondes et celui en Java en prend que 3.

Je sais que OCaml fait très peu d'optimisations du code objet et que Java en fait beaucoup, mais je me demandais si quelqu'un avait des petites améliorations à proposer pour mon code OCaml.

Pour compiler le code, utiliser la commande ocamlopt str.cmxa tm.ml -o tm et pour l'exécuter utiliser la commande ./tm <fichier de machine de Turing> <chaîne initiale> <état initial>.

Je note au passage que j'avais une version qui utilisait un Hashtbl et que sa performance était inférieure à l'utilisation d'un Map.

Si vous avez besoin d'informations supplémentaires, n'hésitez pas à me les demander.

Merci de votre aide.

Code :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
module TupleMap = Map.Make(
  struct
    type t = char * string
    let compare (c1, s1) (c2, s2) =
      let cmp1 = Char.compare c1 c2 in
        if cmp1 <> 0 then
          cmp1
        else
          String.compare s1 s2
  end
)
 
 
(* in_ch : Canal de lecture
   rules : Map contenant les règles.  Les clés sont
           des 2-tuples contenant un caractère et un état,
           et les valeurs sont des 3-tuples contenant un
           caractère, un état et une direction.
   Chaque ligne est lu et est séparée aux virgules; s'il
   y a 5 éléments, on ajoute la règle, sinon on passe à
   la ligne suivante.  À la fin du fichier, on retourne
   le Map.
*)
let rec read_rules in_ch rules =
  let splitter = Str.regexp "[ ]*,[ ]*" in
  let rec loop rules =
    try
      let line = input_line in_ch in
        match (Str.split splitter line) with
          | [old_st; old_ch; new_st; new_ch; dir] ->
              loop (TupleMap.add (old_ch.[0], old_st)
                      (new_ch.[0], new_st, dir.[0]) rules)
          | _ -> loop rules
    with End_of_file ->
      rules
  in
    loop rules
 
let move_head head dir =
  match dir with
    | 'G' -> head - 1
    | 'D' -> head + 1
    | _ -> head
 
 
(* tape: un tableau de caractères représentant le ruban
   head: un entier représentant la position dans le ruban
   state: une chaîne représentant l'état actuel
   rules: un map contenant les règles de transition
   steps: un entier contenant le nombre d'étapes exécutées
 
   Tant que `state` n'est pas l'état ACCEPTE ou REJETTE, on
   trouve la règle correspondante à l'état et au caractère
   actuel, on les remplace et on se déplace vers la gauche
   ou vers la droite.
*)
let rec execute tape head state rules steps =
  match state with
    | "ACCEPTE" -> ("ACCEPTE", steps)
    | "REJETTE" -> ("REJETTE", steps)
    | _ ->
        let (new_ch, new_st, dir) = TupleMap.find (tape.(head), state) rules in
          tape.(head) <- new_ch;
          execute tape (move_head head dir) new_st rules (steps+1)
 
(* Créer le ruban en créant un tableau de caractères _ et en
   remplaçant le centre par la chaîne d'entrée.
*)
let make_tape length input =
  let tape = Array.make length '_' in
    for i = 0 to (String.length input) - 1 do
      tape.(length / 2 + i) <- input.[i]
    done;
    tape
 
let _ =
  let in_ch = open_in Sys.argv.(1) in
  let rules = read_rules in_ch TupleMap.empty in
    close_in in_ch;
    let init_st = Sys.argv.(3) in
    let tape_length = 1 lsl 20 - 1 in   (* ~1M *)
    let head = tape_length / 2 in
    let tape = make_tape tape_length Sys.argv.(2) in
    let (final_st, steps) = execute tape head init_st rules 0 in
      Printf.printf "%s (%d)\n" final_st steps

Code pour la machine de Turing (à exécuter avec ./tm fichier.tm "" 1):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
1,_,2,1,G
1,1,3,1,D
2,_,3,1,G
2,1,2,1,G
3,_,4,1,G
3,1,5,_,D
4,_,1,1,D
4,1,4,1,D
5,_,ACCEPTE,1,G
5,1,1,_,D

[Cacophrene]

Bonjour,

Compile avec l'option -p pour avoir les données de profiling sur ton code. Tu verras que ton programme passe l'essentiel du temps dans la fonction execute. À lui seul, le filtrage sur les chaînes "ACCEPTE" et "REJETTE" prend beaucoup de temps.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Flat profile:
 
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 25.13      1.93     1.93 94374171     0.00     0.00  compare_val
 12.37      2.88     0.95 141526538     0.00     0.00  camlTuring__compare_1031
 11.46      3.76     0.88 188748400     0.00     0.00  caml_string_length
 11.33      4.63     0.87        1     0.87     7.30  camlTuring__execute_1108

Pour aller plus vite, essaie de définir de nouveaux types et de mieux séparer le parsing et l'exécution. Par exemple :

Code :

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
type tm_state = Accept | Reject | Number of int

let state_of_string = function
  | "ACCEPTE" -> Accept
  | "REJETTE" -> Reject
  | nbr -> Number (int_of_string nbr)

let rec execute tape head state rules steps =
  match state with  
    | Accept -> ("ACCEPTE", steps)
    | Reject -> ("REJETTE", steps)
    | _ ->
      let (new_ch, new_st, dir) = TupleMap.find (tape.(head), state) rules in
      tape.(head) <- new_ch;
      execute tape (move_head head dir) new_st rules (steps + 1)

Rien qu'avec ceci on gagne une seconde d'exécution... Ensuite, le code passe beaucoup de temps à faire des comparaisons... une piste peut-être

Cordialement,
Cacophrène

[TropMDR]

Effectivement, un des grand bonheur quand on utilise des langages "à la ML", outre les fonctions de première classe, c'est la possibilité de définir en un rien de temps de nouveaux types de données ! (rien à voir avec java par exemple, où il faut ouvrir un nouveau fichier, puisqu'on a un seul type public par fichier, créer une nouvelle classe, avec tout le blabla qui va bien, etc, etc).

Donc, il faut en profiter !!

avec

Code :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
(* un etat est soit un entier, soit ACCEPTE ou REJETTE *)
type state =
  | ACCEPT
  | REJECT
  | State of int
 
let parse_state = function
  | "ACCEPTE" -> ACCEPT
  | "REJETTE" -> REJECT
  | s -> State (int_of_string s) (* peu echouer, donc pas propre *)
 
 
(* un direction est soit gauche, soit droite, soit reste au meme
   endroit *)
type direction =
  | L
  | R
  | S
 
let parse_direction = function
  | "G" -> L
  | "D" -> R
  |  _  -> S
 
 
module TupleMap = Map.Make(
  struct
    type t = char * int
    let compare ((c1, i1):t) ((c2, i2):t) =
      let cmp_c = compare c1 c2 in
      if cmp_c <> 0 then cmp_c else compare i1 i2
  end
 )
type action = (char * state * direction)    
 
(* in_ch : Canal de lecture
   rules : Map contenant les règles.  Les clés sont
           des 2-tuples contenant un caractère et un état,
           et les valeurs sont des 3-tuples contenant un
           caractère, un état et une direction.
   Chaque ligne est lu et est séparée aux virgules; s'il
   y a 5 éléments, on ajoute la règle, sinon on passe à
   la ligne suivante.  À la fin du fichier, on retourne
   le Map.
*)
let read_rules in_ch : action TupleMap.t=
  let splitter = Str.regexp "[ ]*,[ ]*" in
  let rec loop rules =
    try
      let line = input_line in_ch in
      match (Str.split splitter line) with
      | [old_st; old_ch; new_st; new_ch; dir] ->
          loop (TupleMap.add (old_ch.[0], int_of_string old_st)
                  (new_ch.[0], parse_state new_st, parse_direction dir) rules)
      | _ -> loop rules
    with End_of_file ->
      rules
  in
  loop TupleMap.empty
 
let move_head head dir =
  match dir with
    | L-> head - 1
    | R -> head + 1
    | S -> head
 
 
(* tape: un tableau de caractères représentant le ruban
   head: un entier représentant la position dans le ruban
   state: une chaîne représentant l'état actuel
   rules: un map contenant les règles de transition
   steps: un entier contenant le nombre d'étapes exécutées
 
   Tant que `state` n'est pas l'état ACCEPTE ou REJETTE, on
   trouve la règle correspondante à l'état et au caractère
   actuel, on les remplace et on se déplace vers la gauche
   ou vers la droite.
*)
let rec execute tape head state rules steps =
  match state with
    | ACCEPT -> ("ACCEPTE", steps)
    | REJECT -> ("REJETTE", steps)
    | State s ->
        let (new_ch, new_st, dir) = TupleMap.find (tape.(head), s) rules in
          tape.(head) <- new_ch;
          execute tape (move_head head dir) new_st rules (steps+1)
 
(* Créer le ruban en créant un tableau de caractères _ et en
   remplaçant le centre par la chaîne d'entrée.
*)
let make_tape length input =
  let tape = Array.make length '_' in
    for i = 0 to (String.length input) - 1 do
      tape.(length / 2 + i) <- input.[i]
    done;
    tape
 
let _ =
  let in_ch = open_in Sys.argv.(1) in
  let rules = read_rules in_ch in
    close_in in_ch;
    let init_st = parse_state (Sys.argv.(3)) in
    let tape_length = 1 lsl 20 - 1 in   (* ~1M *)
    let head = tape_length / 2 in
    let tape = make_tape tape_length Sys.argv.(2) in
    let (final_st, steps) = execute tape head init_st rules 0 in
      Printf.printf "%s (%d)\n" final_st steps

Je passe de 5.10 secondes à 1.90. On y gagne !

[Cacophrene]

Bonjour,

En poussant plus loin, on peut aussi nettoyer la fonction read_rules en utilisant les fonctions du module Scanf, représenter tape sous forme de chaîne au lieu de tableau, ce qui donne :

Code :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
open Scanf

type tm_state = Accept | Reject | State of int
type tm_direction = GoLeft | GoRight | Unchanged

let get_state = function
  | "ACCEPTE" -> Accept
  | "REJETTE" -> Reject
  | s -> State (int_of_string s) 
      
let get_direction = function
  | 'G' -> GoLeft
  | 'D' -> GoRight
  |  _  -> Unchanged
    
module TMap = Map.Make(
  struct
    type t = char * int
    let compare ((c1, i1) : t) ((c2, i2) : t) =
      let cmp_c = Char.compare c1 c2 in
      if cmp_c = 0 then compare i1 i2 else cmp_c
  end
 )

let nlines = Str.split (Str.regexp "\n")

let add_rule rules old_st old_ch new_st new_ch dir =
  TMap.add (old_ch, old_st) (new_ch, get_state new_st, get_direction dir) rules

let read_rules tm_file =
  let tm_chan = open_in tm_file in
  let tm_size = in_channel_length tm_chan in
  let tm_buff = String.create tm_size in
  really_input tm_chan tm_buff 0 tm_size;
  List.fold_left (fun tm_rules tm_line ->
    kscanf (Scanning.from_string tm_line) (fun _ _ -> tm_rules) 
      "%d , %c , %[^,] , %c , %c" (add_rule tm_rules)
  ) TMap.empty (nlines tm_buff)

let move_head x = function
  | GoLeft -> x - 1
  | GoRight -> x + 1
  | Unchanged -> x

let execute tape rules =
  let rec loop head steps = function
    | Accept -> ("ACCEPTE", steps)
    | Reject -> ("REJETTE", steps)
    | State s -> let new_ch, new_st, dir = TMap.find (tape.[head], s) rules in
      tape.[head] <- new_ch;
      loop (move_head head dir) (steps + 1) new_st
  in loop

let make_tape length input =
  let tape = String.make length '_' in
  for i = 0 to String.length input - 1 do
    tape.[length lsr 1 + i] <- input.[i]
  done;
  tape

let _ =
  let x = Unix.gettimeofday () in
  let rules = read_rules Sys.argv.(1) in
  let init_st = get_state (Sys.argv.(3)) in
  let tape_length = 1 lsl 20 - 1 in   (* ~1M *)
  let head = tape_length lsr 1 in
  let tape = make_tape tape_length Sys.argv.(2) in
  let (final_st, steps) = execute tape rules head 0 init_st in
  Printf.printf "%s (%d)\n" final_st steps;
  let y = Unix.gettimeofday () in
  Printf.printf "Elapsed time: %.3f s\n%!" (y -. x)

J'arrive grosso modo au même gain de performance que ce qu'indique TropMDR car la définition de nouveaux types est vraiment la solution au problème.

Cordialement,
Cacophrène

[GnuVince]

Merci pour vos suggestions à tous les deux; comme les états ne sont pas toujours des entiers, mais peuvent être des chaînes arbritraires, j'ai utilisé la fonction Hashtbl.hash pour faire une conversion string -> int. Mon nouveau code exécute la machine de Turing en 1.7s sur ma machine 64 bits et en 3.3s sur ma machine 32 bits! Je vous donne mon nouveau code, et merci encore de votre aide!

Code :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
type state = Accept | Reject | Other of int
 
module TupleMap = Map.Make(
  struct
    type t = char * state
    let compare (c1, st1) (c2, st2) =
      let cmp1 = Char.compare c1 c2 in
        if cmp1 <> 0 then cmp1
        else
          match (st1, st2) with
            | (Other i1, Other i2) -> i1 - i2
            | (_, _) -> 0 (* unsafe *)
  end
)
 
 
let state_of_string s =
  match s with
    | "ACCEPTE" -> Accept
    | "REJETTE" -> Reject
    | _ -> Other (Hashtbl.hash s)
 
(* in_ch : Canal de lecture
   rules : Map contenant les règles.  Les clés sont
           des 2-tuples contenant un caractère et un état,
           et les valeurs sont des 3-tuples contenant un
           caractère, un état et une direction.
   Chaque ligne est lu et est séparée aux virgules; s'il
   y a 5 éléments, on ajoute la règle, sinon on passe à
   la ligne suivante.  À la fin du fichier, on retourne
   le Map.
*)
let rec read_rules in_ch rules =
  let splitter = Str.regexp "[ ]*,[ ]*" in
  let rec loop rules =
    try
      let line = input_line in_ch in
        match (Str.split splitter line) with
          | [old_st; old_ch; new_st; new_ch; dir] ->
              loop (TupleMap.add (old_ch.[0], state_of_string old_st)
                      (new_ch.[0], state_of_string new_st, dir.[0]) rules)
          | _ -> loop rules
    with End_of_file ->
      rules
  in
    loop rules
 
let move_head head dir =
  match dir with
    | 'G' -> head - 1
    | 'D' -> head + 1
    | _ -> head
 
 
(* tape: un tableau de caractères représentant le ruban
   head: un entier représentant la position dans le ruban
   state: une chaîne représentant l'état actuel
   rules: un map contenant les règles de transition
   steps: un entier contenant le nombre d'étapes exécutées
 
   Tant que `state` n'est pas l'état ACCEPTE ou REJETTE, on
   trouve la règle correspondante à l'état et au caractère
   actuel, on les remplace et on se déplace vers la gauche
   ou vers la droite.
*)
let rec execute tape head state rules steps =
  match state with
    | Accept -> ("ACCEPTE", steps)
    | Reject -> ("REJETTE", steps)
    | Other _ ->
        let (new_ch, new_st, dir) = TupleMap.find (tape.(head), state) rules in
          tape.(head) <- new_ch;
          execute tape (move_head head dir) new_st rules (steps+1)
 
(* Créer le ruban en créant un tableau de caractères _ et en
   remplaçant le centre par la chaîne d'entrée.
*)
let make_tape length input =
  let tape = Array.make length '_' in
    for i = 0 to (String.length input) - 1 do
      tape.(length / 2 + i) <- input.[i]
    done;
    tape
 
let _ =
  let in_ch = open_in Sys.argv.(1) in
  let rules = read_rules in_ch TupleMap.empty in
    close_in in_ch;
    let init_st = state_of_string Sys.argv.(3) in
    let tape_length = 1 lsl 20 - 1 in   (* ~1M *)
    let head = tape_length / 2 in
    let tape = make_tape tape_length Sys.argv.(2) in
    let (final_st, steps) = execute tape head init_st rules 0 in
      Printf.printf "%s (%d)\n" final_st steps

[TropMDR]

Merci pour vos suggestions à tous les deux; comme les états ne sont pas toujours des entiers, mais peuvent être des chaînes arbritraires, j'ai utilisé la fonction Hashtbl.hash pour faire une conversion string -> int.

Je te rappelle que Hashtbl.hash n'est pas injective ! Donc si tu as deux états qui ont la mauvaise idée de se retrouver avec le même hash, tu auras des surprise désagréable !

En revanche, tu peux créer dynamiquement une fonction injective de string -> int :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
let num_state=
  let next_state = ref 0 in
  let seen_states = Hashtbl.create 15 in
  (fun s ->
    try
      Hashtbl.find seen_states s
    with
    | Not_found ->
	Hashtbl.add seen_states s !next_state;
	incr next_state;
	!next_state - 1)

Un deuxième intérêt d'utiliser cette méthode, c'est que tu rends les numéros de tes états dense entre 0 et (n-1), ce qui te permet de remplacer avantageusement ta map par une matrice de taille n * 256. Faire ça (voir code plus bas) me fait passer de 1'95 (sur le code de mon précédent message) à 0,35s.

Code :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
(* un etat est soit un entier, soit ACCEPTE ou REJETTE *)
type state =
  | ACCEPT
  | REJECT
  | State of int
 
 
let num_state, max_state =
  let next_state = ref 0 in
  let seen_states = Hashtbl.create 15 in
  (fun s ->
    try
      Hashtbl.find seen_states s
    with
    | Not_found ->
	Hashtbl.add seen_states s !next_state;
	incr next_state;
	!next_state - 1),
  (fun () -> !next_state)
 
 
let parse_state = function
  | "ACCEPTE" -> ACCEPT
  | "REJETTE" -> REJECT
  | s -> State (num_state s)
 
 
(* un direction est soit gauche, soit droite, soit reste au meme
   endroit *)
type direction =
  | L
  | R
  | S
 
let parse_direction = function
  | "G" -> L
  | "D" -> R
  |  _  -> S
 
type action = (char * state * direction)    
 
(* in_ch : Canal de lecture
   rules : Map contenant les règles.  Les clés sont
           des 2-tuples contenant un caractère et un état,
           et les valeurs sont des 3-tuples contenant un
           caractère, un état et une direction.
   Chaque ligne est lu et est séparée aux virgules; s'il
   y a 5 éléments, on ajoute la règle, sinon on passe à
   la ligne suivante.  À la fin du fichier, on retourne
   le Map.
*)
let read_rules in_ch : action array array =
  let splitter = Str.regexp "[ ]*,[ ]*" in
  let rec loop rules : ((int * char) * action) list =
    try
      let line = input_line in_ch in
      match (Str.split splitter line) with
      | [old_st; old_ch; new_st; new_ch; dir] ->
	  begin match parse_state old_st with
	  | ACCEPT | REJECT -> failwith "No rules from final states"
	  | State os ->
              loop (((os, old_ch.[0]),
                    (new_ch.[0], parse_state new_st, parse_direction dir))
		   ::rules)
	  end
      | _ -> loop rules
    with End_of_file ->
      rules
  in
  let rules_def = List.rev (loop []) in
  let rules = Array.make_matrix (max_state ()) 256 ('!', REJECT, S) in
  List.iter (fun ((old_st, old_ch), act) ->
    rules.(old_st).(int_of_char old_ch) <- act) rules_def;
  rules
 
let move_head head dir =
  match dir with
    | L-> head - 1
    | R -> head + 1
    | S -> head
 
 
(* tape: un tableau de caractères représentant le ruban
   head: un entier représentant la position dans le ruban
   state: une chaîne représentant l'état actuel
   rules: un map contenant les règles de transition
   steps: un entier contenant le nombre d'étapes exécutées
 
   Tant que `state` n'est pas l'état ACCEPTE ou REJETTE, on
   trouve la règle correspondante à l'état et au caractère
   actuel, on les remplace et on se déplace vers la gauche
   ou vers la droite.
*)
let rec execute tape head state rules steps =
  match state with
    | ACCEPT -> ("ACCEPTE", steps)
    | REJECT -> ("REJETTE", steps)
    | State s ->
        let (new_ch, new_st, dir) = rules.(s).(int_of_char tape.[head]) in
          tape.[head] <- new_ch;
          execute tape (move_head head dir) new_st rules (steps+1)
 
(* Créer le ruban en créant un tableau de caractères _ et en
   remplaçant le centre par la chaîne d'entrée.
*)
let make_tape length input =
  let tape = String.make length '_' in
    for i = 0 to (String.length input) - 1 do
      tape.[length / 2 + i] <- input.[i]
    done;
    tape
 
let _ =
  let in_ch = open_in Sys.argv.(1) in
  let rules = read_rules in_ch in
    close_in in_ch;
    let init_st = parse_state (Sys.argv.(3)) in
    let tape_length = 1 lsl 20 - 1 in   (* ~1M *)
    let head = tape_length / 2 in
    let tape = make_tape tape_length Sys.argv.(2) in
    let (final_st, steps) = execute tape head init_st rules 0 in
      Printf.printf "%s (%d)\n" final_st steps

[Cacophrene]

Bonjour,

Un deuxième intérêt d'utiliser cette méthode, c'est que tu rends les numéros de tes états dense entre 0 et (n-1), ce qui te permet de remplacer avantageusement ta map par une matrice de taille n * 256. Faire ça (voir code plus bas) me fait passer de 1'95 (sur le code de mon précédent message) à 0,35s.

En fait, cette solution est également motivée par le profiling du code que nous lui avons proposé initialement, où le seul changement consistait à définir de nouveaux types. On peut lire :

Code :

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

1
2
3
4
5
6
7
8
9
 
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 25.60      1.27     1.27 141526538    0.00     0.00  camlTm1__compare_1048
 22.38      2.38     1.11 235900704    0.00     0.00  caml_int_compare
 19.76      3.36     0.98 141526554    0.00     0.00  caml_apply2
 15.93      4.15     0.79 47176873     0.00     0.00  camlMap__find_1117
 11.90      4.74     0.59        1     0.59     4.74  camlTm1__execute_1125

Il en ressort clairement que le programme passe le plus clair de son temps à faire des comparaisons... (déjà signalé à la fin de ce message). Le recours aux tableaux permet justement de contourner ce problème efficacement, à condition bien sûr que les états ne soient pas trop dispersés, comme tu l'as justement souligné. On gaspille quand même un peu d'espace à cause des tableaux de 256 éléments pour stocker les caractères...

Cordialement,
Cacophrène

[gasche]

J'ai réfléchi hier soir à l'intérêt de la conversion 'a TupleMap.t -> 'a array array. Tout content, j'implémente ce matin, j'améliore les performances considérablement, je viens pour poster et.. TropMDR l'a déjà fait.

La vie est injuste alors je me vengerai avec une remarque aigrie.

Je sais que OCaml fait très peu d'optimisations du code objet et que Java en fait beaucoup, mais je me demandais si quelqu'un avait des petites améliorations à proposer pour mon code OCaml.

Si tu passais moins de temps à essayer d'exploiter les "optimisations du code objet", et plus de temps à utiliser les structures de données appropriées, tu aurais dès le départ du code rapide dans tous les langages (civilisés).

[Cacophrene]

Bonjour,

J'ai réfléchi hier soir à l'intérêt de la conversion 'a TupleMap.t -> 'a array array. Tout content, j'implémente ce matin, j'améliore les performances considérablement, je viens pour poster et.. TropMDR l'a déjà fait.

Ah Ah Ah toi aussi ça te l'a fait ? J'y pensais moi aussi car j'avais remarqué en profilant le code du PO qu'on perdait beaucoup de temps à comparer des valeurs et qu'un accès par tableau serait donc plus performant.

En pareil cas, on peut aussi dissiper son mécontentement en glosant inutilement sur le message de TropMDR comme je l'ai fait. On en arriverait même à se disputer sur l'ordre des réponses . À l'unanimité des plaignants, TropMDR sera donc déclaré coupable de répondre trop vite.

Bonne après-midi à tout le monde,
Cacophrène

[GnuVince]

Si tu passais moins de temps à essayer d'exploiter les "optimisations du code objet", et plus de temps à utiliser les structures de données appropriées, tu aurais dès le départ du code rapide dans tous les langages (civilisés).

Justement pour ça que j'ai posé la question ici; également pour ça que j'ai switché d'un Hashtbl à un Map.

[GnuVince]

TropMDR: Merci pour ta suggestion, après l'avoir lu j'ai fermé la fenêtre pour l'implanter sans faire du copier/coller bête, et je suis arrivé à sensiblement la même solution que toi. Quelques différences:

* Plutôt que d'avoir une action sentinelle, j'utilise le type option
* Quand je lis la direction, je stocke immédiatement -1, 0 ou 1 pour pouvoir éviter d'appeler move_head des millions de fois
* Ton make_matrix est pas mal plus joli que les Array.make imbriqués que j'avais


Merci encore!

[GnuVince]

Cacophrene:

Ceci semble plus optimal pour le profiling?

Code :

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
 
 
Flat profile:
 
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 97.50      0.39     0.39                             camlTm__execute_1088
  2.50      0.40     0.01  1049856     0.01     0.01  caml_initialize
  0.00      0.40     0.00     4022     0.00     0.00  caml_page_table_modify
  0.00      0.40     0.00      703     0.00     0.00  caml_page_table_lookup
  0.00      0.40     0.00      369     0.00     0.00  caml_darken
  0.00      0.40     0.00      327     0.00     0.00  camlChar__chr_1032
  0.00      0.40     0.00      256     0.00     0.00  camlChar__lowercase_1043
  0.00      0.40     0.00      124     0.00     0.00  caml_oldify_one
  0.00      0.40     0.00      123     0.00     0.00  caml_string_length