Comment étendre efficacement des tableaux

Version imprimable

31/07/2009, 07h13
Arthur Rainbow

Comment étendre efficacement des tableaux

Bonjour,

Je cherche à savoir si il existe une solution efficace connu à un problème que j'ai. Je code actuellement en oCaml, donc une solution orienté objet, fonctionnelle/récursive, ou itérative/impérative, tout me va.(C'est pour ça que je l'ai mis en section algorithmique)

Soient m>n des entiers.
J'ai un tableau t de taille n, puis je veux étendre ce tableau en plusieurs tableau t_1, t_2, t_3... de taille m, et où les n premières valeurs de t2 sont les valeurs de t1.

Et je recommence l'opération récursivement, donc je peux me trouver avec t_i1,t_i2,..., t_ijklm..z

Le tableau contient des constantes, au sens que, toutes les valeurs du tableau sont connu à sa création, et elle sont imédiatement écrite. Après, je lirai les cases de ce tableau mais ne les écrirai plus.
Une fois que les ti seront créé, je n'utiliserai plus t, donc ce n'est pas grave si le tableau est détruit au passage.

Actuellement, je vois trois solutions:

Soit quand je créé t1, j'initialise un nouveau tableau de taille m, et recopie les n premiières valeurs (mais c'est inefficace à la création)
Soit ti sera un couple, composé de t, et d'un nouveau tableau de taille m-n, et je dis que si je veux la kième case, si k>n, alors je prend la k-n ème case du nouveau tableau, sinon je prend la kième case du tableau t.
(Avec un module/une classe, ça s'écrit très facilement récursivement pour que ce soit transparant pour l'utilisateur, et permette d'étendre plusieurs fois un tableau)

Mais dans ce cas, si on étendu hj fois, l'accès à un élément du "tableau" n'est plus en O(1) mais en O(h) ce qui n'est pas vraiment efficace.

Soit j'abandonne le tableau, et j'utilise des arbre de recherche équilibré persistant, depuis les position du tableau vers mes valeurs.
(probablement un AVL, puisque oCaml fournit ça avec le module Map dans sa bibliothèque)
La création de t_i serait donc du O((m-n)log(m)), et la recherche en O(log(m)), ce n'est donc pas vraiment très efficace, mais j'évite les gros temps des deux premières solutions

Je souhaitai savoir si quelqu'un connaissait une méthode plus efficace au niveau du temps d'éxécution. Moi je bloque. (La mémoire n'est pas autant un problème, le garbage collector fera son office sur ce dont je ne me sers plus)

Pour information, j'ai malheureusement peu d'information pertinante sur son execution.

La plupart des tableau seront étendu, souvent une seule fois, parfois jusqu'à une dizaine de fois. (dans le sens où on aura t1 t2 ... t10). Certaines extensions seront utilisé très peu avant d'être détruite. Pour ces raisons, la première méthode est à proscrire

Mais les extensions qui sont gardé pourront être étendu plein de fois. Il n'est pas impossible qu'on se retrouve avec un tableau de la forme t_i1i2...i50, et que dans la 50ème extension, on est besoin d'accéder à une valeur du tout premier tableau. Donc la deuxième méthode est aussi à proscrire.
31/07/2009, 12h59
Jedai

On ne fait pas de miracles, donc ne t'attend pas à pouvoir accéder en O(1) à ta structure finale si tu veux garder le coût de l'extension raisonnable, néanmoins j'ai une solution acceptable pour toi : combiner tes solutions 2 et 3.
Utilises un AVL (ou n'importe quel arbre binaire équilibré) de tableaux. Ainsi, après N extensions, un accès te coûtera O(log N) et une extension de m éléments coûtera O(log N + m).

NB : Tu dois absolument utiliser tes tableaux fonctionnellement pour que cela fonctionne, si tu essaie de modifier des valeurs dans ces tableaux cette modification sera partagée (ou pas, selon la position de la modification).

--
Jedaï
31/07/2009, 15h38
SpiceGuid

En théorie:
À mon avis la meilleure structure de données est une variante renversée de la random-access-list de Okasaki. Cette structure de données te permet l'extension en O(1) et l'accès en O(ln n) dans le pire des cas. Tu peux en trouver une implantation dans Ocaml-Reins. Malheureusement cette implantation n'est pas exactement celle que tu cherche puisque qu'elle réalise le cons (extension à l'indice 0) alors que tu veux le snoc (extension à l'indice n).

En pratique:
cette structure de données devrait faire l'affaire, c'est un tableau plus général (à indices quelconques), donc avec de moins bonnes performances, O(ln n) pour l'extension et l'accès. L'avantage sur l'AVL c'est que tu n'as rien à coder, que tu as une version mutable et que chaque noeud consomme moins de mémoire. En terme de performance c'est compétitif dans le cas où les indices ne sont pas trop dispersés (c'est ton cas puisque tes indices sont consécutifs).

http://www.developpez.net/forums/m3783789-67/
31/07/2009, 17h43
Jedai

Citation:

Envoyé par SpiceGuid

En théorie:
À mon avis la meilleure structure de données est une variante renversée de la random-access-list de Okasaki. Cette structure de données te permet l'extension en O(1) et l'accès en O(ln n) dans le pire des cas. Tu peux en trouver une implantation dans Ocaml-Reins. Malheureusement cette implantation n'est pas exactement celle que tu cherche puisque qu'elle réalise le cons (extension à l'indice 0) alors que tu veux le snoc (extension à l'indice n).

Cette structure est vraiment sympa ! Elle ne devrait pas être trop difficile à implémenter non plus, ou adapter à un usage inversé (je suggère que juste conserver la taille totale de la liste et consulter l'élément d'indice (n-i) en interne quand l'élément i est demandé est encore la solution la plus simple).

Citation:

Envoyé par SpiceGuid

En pratique:
cette structure de données devrait faire l'affaire, c'est un tableau plus général (à indices quelconques), donc avec de moins bonnes performances, O(ln n) pour l'extension et l'accès. L'avantage sur l'AVL c'est que tu n'as rien à coder, que tu as une version mutable et que chaque noeud consomme moins de mémoire. En terme de performance c'est compétitif dans le cas où les indices ne sont pas trop dispersés (c'est ton cas puisque tes indices sont consécutifs).

Un trie sur les bits, c'est un bon choix, même si l'extension risque d'être coûteuse (O(m log (n+m))).

En bref, tout dépend de si Arthur a besoin de mutabilité dans ses tableaux (sans partager les modifications s'entend) et si oui à quelle fréquence. S'il n'en a pas besoin ou très peu souvent, ma solution est préférable à tes propositions (même si théoriquement l'extension pour ma solution est en O(log N + m) contre O(m) pour Okasaki, en pratique les facteurs constants sur mon m sont minuscules alors qu'ils sont relativement importants sur la structure d'Okasaki), sinon c'est nettement plus discutable, l'idéal étant de faire un bench (en pratique sauf si les performances sont critiques, je suppose que ta seconde proposition serait le plus simple dans ce cas).

--
Jedaï

Plus spécifiquement pour les Trie sur les bits des entiers consécutifs j'ai une autre source, honteusement pompée sur la bibliothèque Edison de Okasaki, (source non testée, recherche et ajout d'un élément en O(ln n), OCaml 3.11+) :

Module BraunTree :

Code:

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
module Make
:
sig
  type 'a tree = 'a node option
  and 'a node = {
    mutable left : 'a tree;
    mutable right : 'a tree;
    mutable item : 'a;
  }
  val empty : 'a tree
  val is_empty:  'a tree -> bool
  val singleton: 'a -> 'a tree
  val copy:      'a tree -> 'a tree
  val diff:      'a tree -> int -> int
  val length:    'a tree -> int
  val map:       ('a -> 'b) -> 'a tree -> 'b tree
  val add:       'a -> 'a tree -> 'a tree
  val insert:    'a -> 'a tree -> 'a tree
  val combine:   'a tree -> 'a tree -> 'a tree
  val case:      'a tree -> ('a * 'a tree) option
  val uncons:    'a tree -> 'a * 'a tree
  val lookup:    int -> 'a tree -> 'a option
  val find:      int -> 'a tree -> 'a
  val update:    int -> 'a -> 'a tree -> 'a tree
  val assign:    int -> 'a -> 'a tree -> 'a tree
  val append:    'a tree -> 'a tree -> 'a tree
end
=
struct

  type 'a tree =
    'a node option
  and 'a node =
    {
    mutable left: 'a tree; mutable right: 'a tree; mutable item: 'a;
    }

  let empty =
    None

  let is_empty t = (t = empty)

  let singleton x =
    Some {left = None; right = None; item = x}

  let rec copy = function
    | None -> None  
    | Some n -> Some {n with left = copy n.left; right = copy n.right}

  let rec diff t m =
    match t with
    | None -> 0  
    | Some n when m = 0 -> 1 
    | Some n ->
        if m land 1 = 1 then diff n.left ((m - 1) / 2)
        else diff n.right ((m - 2) / 2)

  let rec length = function
    | None -> 0  
    | Some n -> let m = length n.right in 1 + m + m + diff n.left m

  let rec map f = function
    | None -> None  
    | Some n -> Some
        {left = map f n.left; right = map f n.right; item = f n.item}

  let rec add x = function
    | None ->
        Some {left = None; right = None; item = x}
    | Some n -> 
        Some {left = add n.item n.right; right = n.left; item = x}

  let rec insert x t =
    match t with
    | None ->
        Some {left = None; right = None; item = x}
    | Some n -> 
        let l = n.left in
        n.left <- insert n.item n.right; n.right <- l;
        n.item <- x; t

  let rec combine t c =
    match t with
    | None -> None
    | Some n ->
        Some {left = c; right = combine n.left n.right; item = n.item}

  let case = function
    | None -> None
    | Some n -> Some (n.item,combine n.left n.right)

  let uncons = function
    | None -> failwith "uncons"
    | Some n -> (n.item,combine n.left n.right)

  let rec lookup i = function 
    | None -> None
    | Some n ->
        if i = 0 then Some (n.item) else
        if i land 1 = 1 then lookup (i / 2) n.left
        else lookup (i / 2 - 1) n.right

  let rec find i = function 
    | None -> raise Not_found
    | Some n ->
        if i = 0 then n.item else
        if i land 1 = 1 then find (i / 2) n.left
        else find (i / 2 - 1) n.right

  let rec update i x = function 
    | None -> raise Not_found
    | Some n ->
        if i = 0 then Some {n with item = x} else
        if i land 1 = 1 then Some {n with left = update (i / 2) x n.left}
        else Some {n with right = update (i / 2 - 1) x n.right} 

  let rec assign i x t =
    match t with
    | None -> raise Not_found
    | Some n ->
        if i = 0 then n.item <- x else
        if i land 1 = 1 then n.left <- assign (i / 2) x n.left
        else n.right <- assign (i / 2 - 1) x n.right;
        t

  let rec append n ta tb =
    if n = 0 then tb else
    match ta,tb with
    | _,None -> ta
    | None,_ -> assert false
    | Some a,Some b ->
        let m = n / 2 in
        if n land 1 = 1 then Some
          {item  = a.item;
           left  = append m a.left (add b.item b.right);
           right = append m a.right b.left}
        else Some
          {item  = a.item;
           left  = append m a.left b.left;
           right = append (m-1) a.right (add b.item b.right)}
  let append ta tb =
    if tb = None then ta
    else append (length ta) ta tb

end

Module BraunList :

Code:

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
module rec Mutable :
  sig
    include Interfaces.MutableList
    val to_pure:  'a list -> 'a Pure.list
    val to_pure_unsafe: 'a list -> 'a Pure.list
  end
  =
  struct
   
    include BraunTree.Make
  
    type 'a list = 'a tree ref
  
    let cons x t = t := insert x !t

    let to_pure t = copy !t
    let to_pure_unsafe t = !t

    let make () = ref empty 
    let singleton x = ref (singleton x) 
    let length t = length !t
    let is_empty t = (!t = empty)
    let copy t = ref (copy !t)   
    let find i t = find i !t
    let lookup i t = lookup i !t
    let assign i x t = t := assign i x !t 
    let remove i t = t:= remove i !t
    let append a b = ref (append !a !b)
    let map f t = ref (map f !t)
      
  end

and Pure :
  sig
    include Interfaces.PureList
    val to_mutable:  'a list -> 'a Mutable.list
    val to_mutable_unsafe: 'a list -> 'a Mutable.list
  end
  =
  struct
   
    include BraunTree.Make
  
    type 'a list = 'a tree
  
    let cons = add

    let to_mutable t = ref (copy t)
    let to_mutable_unsafe t = ref t  

  end

Le type de modules List :

Code:

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
module Interfaces
=
struct

module type BaseList
  =
  sig
    type 'a list
    val singleton: 'a -> 'a list 
    val is_empty:  'a list -> bool
    val length:    'a list -> int
    val append:    'a list -> 'a list -> 'a list
    val find:      int -> 'a list -> 'a 
    val lookup:    int -> 'a list -> 'a option
    val map:       ('a -> 'b) -> 'a list -> 'b list
  end
  
module type PureList
  =
  sig
    include BaseList
    val empty:     'a list 
    val cons:      'a -> 'a list -> 'a list
    val uncons:    'a list -> 'a * 'a list
    val case:      'a list -> ('a * 'a list) option
    val update:    int -> 'a -> 'a list -> 'a list 
  end
  
module type MutableList
  =
  sig
    include BaseList
    val make:      unit -> 'a list 
    val cons:      'a -> 'a list -> unit
    val copy:      'a list -> 'a list
    val assign:    int -> 'a -> 'a list -> unit 
  end

end

01/08/2009, 05h11
Arthur Rainbow

Citation:

Envoyé par Jedai

On ne fait pas de miracles, donc ne t'attend pas à pouvoir accéder en O(1) à ta structure finale si tu veux garder le coût de l'extension raisonnable

Je m'en doute, je cherchais juste un compromis

Citation:

Envoyé par Jedai

, néanmoins j'ai une solution acceptable pour toi : combiner tes solutions 2 et 3.
Utilises un AVL (ou n'importe quel arbre binaire équilibré) de tableaux. Ainsi, après N extensions, un accès te coûtera O(log N) et une extension de m éléments coûtera O(log N + m).

Effectivement, sauf que je ne suis pas sur de voir exactement comment faire.
J'associe à un noeud son minimum et son maximum, m et M, et si je cherche la position i, c'est bon si m<=i<M, sinon je vais à gauche si i<m et à droite si i>=M? Ca nécessiterait de pas mal changer le module d'oCaml, mais ça doit être faisable.

Citation:

Envoyé par Jedai

NB : Tu dois absolument utiliser tes tableaux fonctionnellement pour que cela fonctionne, si tu essaie de modifier des valeurs dans ces tableaux cette modification sera partagée (ou pas, selon la position de la modification).

C'est pour ça que je précisai que je remplie le tableau a sa création puis n'y touche pas, donc ça ne sera pas un problème.

[QUOTE=SpiceGuid;4532503]
[url=http://damien-guichard.developpez.com/tutoriels/ocaml[/QUOTE]
Je ne vois pas la différence avec un trie, mais c'est vrai qu'un trie pourrait être efficace pour ce que je fais

Ce dont je me suis rendu compte en repensant à mon problème, c'est que la plupart du temps, je ne lirai qu'une fois une valeur. Il sera très rare que je relise deux fois la même position, et je sais en lisant si j'aurai besoin ou non de relire. Donc je peux supprimer les positions inutile de mon avl dès que je cherche la position. A ce moment là, l'AVL peut regagner en utilité.

Le module Map de ocaml est un avl, donc l'implémentation sera très simple, j'utilise juste ce module.

Citation:

Envoyé par Jedai

En bref, tout dépend de si Arthur a besoin de mutabilité

Non j'écris dans les tableau à la création, et c'est tout

Sinon, merci pour le module et pour toute votre aide