:arrow: Un Skew max-heap est un tas-maximum.
(* skew max-heap *)
type 'a skew =
| Empty
| Skew of 'a skew * 'a * 'a skew
let rec join ha hb =
Type: Messages; Utilisateur: SpiceGuid
:arrow: Un Skew max-heap est un tas-maximum.
(* skew max-heap *)
type 'a skew =
| Empty
| Skew of 'a skew * 'a * 'a skew
let rec join ha hb =
Et oui, il y a forcément un nombre d'éléments en dessous duquel un algo avancé fait moins bien que l'algo naïf. Le contournement habituel consiste à trouver le point où ça bascule (par exemple...
Souvent, par facilité, pour coder un environnment on utilise une simple liste d'association d'un string vers un élément.
Pour faire un peu mieux on peut désigner les variables par leur indice De...
:ccool: tu as eu l'idée lumineuse que j'espérais, malheureusement je ne peux pas modifier le code dans mon message original (parce que, pour une raison que j'ignore, je n'y ai pas de bouton Editer)
...
Pour ce qui est de la structure de données je t'encourage à chercher du côté du Kd-Tree.
C'est généralisable à plus de 2 dimensions :
(* Kd-Tree en 3D *)
type ('a, 'b, 'c) kd_tree =
| Nil
...
Merci. J'ai corrigé mon code selon tes indications et j'ai ajouté 1 ou 2 idées d'extensions non triviales.
Il s'agit d'un TAD qui ressemble fort à un arbre binaire ordonné sauf qu'en plus il fait aussi "annuaire inversé". C'est-à-dire que le domaine d'arrivée est lui aussi totalement ordonné et peut faire...
Merci, c'est plus clair comme ça, c'est une co-récursion sur une co-donnée, on ne lui demande pas d'être bien fondée, on lui demande d'être productive.
La gendarmerie te souhaites bonne route...
Et qu'est-ce qu'elle fait la gendarmerie Haskell quand un véhicule grille un real_cmp [] [] ?
Pour être clair, ce que j'appelle "défonctorisé" c'est à la façon OCaml-Reins (une implantation défonctorisée), pas à la façon ExtLib (une interface défonctorisée).
Plus concrêtement, au lieu de...
Après avoir tatonné pendant plusieurs heures (bench puis recodage, en boucle) j'ai finalement réussi à dépasser Map.Make. Ça m'a pris pas mal de temps parce que j'ai suivi toutes les fausses pistes...
Beaucoup de warnings dans ton code.
J'ai testé mon code (uniquement l'insertion): les arbres générés sont corrects et équilibrés.
Mais les benchs sont décevants.
Pourtant avant de les faire...
:google:
http://caml.inria.fr/pub/ml-archives/caml-list/2006/08/d1ec8eab49ebe7ca40266e6edee0a88c.en.html
Une autre astuce (utilisée par OCaml-Reins) c'est d'ajouter un variant Leaf pour les...
L'astuce c'est d'utiliser un constructeur "équilibré".
let balance n =
match n.left,n.right with
| None,None -> 0
| Some t,None -> t.height
| None,Some t -> - t.height
...
Nous parlons bien de la même chose.
C'est juste que c'est mon style qui perturbe tes repères.
Les algos sont exactement les mêmes que pour un arbre non-équilibré, il suffit simplement d'ajouter un...
Au point où j'en suis je vais me contenter d'une version correcte.
On verra plus tard pour les perfs.
Est-ce que ce code te paraît correct :question:
(moyennant les fonctions d'équilibrage...
C'est pareil du côté de Niklaus Wirth (Algorithms and Data Structures), pas utilisable car le code est trop impératif pour du Caml.
La grande caractéristique d'un AVL c'est qu'il n'est jamais...
J'ai volontairement effacé toutes les autres fonctions pour améliorer la lisibilité.
module AvlTreeMap (Ord: Ordered)
=
struct
type key = Ord.t
type 'a node =
Petite analyse de complexité de la fonction Mutable.MakeSet.zip_intersect.
Vu que cette fonction est utilisée pour de la recherche bidirectionnelle les deux arbres à intersecter croisent dans les...
Un plateau de jeu pour le Rubik's Cube Pocket (La version 2 x 2 x 2 du cube classique).
module PocketCube =
struct
type cubie =
| C1 | C2 | C3 | C4 | C5 | C6 | C7
type...
Un higher-order module pour solutionner des problèmes sur les plateaux de jeu.
Set est un module pour les tables de transposition
find permet de rechercher un plateau satifaisant une...
Un module-type pour les plateaux de jeu.
Typiquement la fonction compare servira à placer les positions de jeu dans une table de transposition (à l'aide du module Set).
module type Board = ...
Un Mutable.Set higher-order module.
J'ai trop besoin de la fonction zip_intersect, c'est essentiellement ça qui m'empêche d'utiliser le module standard Set.Make.
(voir mon billet blog pour plus de...
J'ai mis à jour la source du module Vect pour que ni le fold ni le foldi ne traversent les noeuds contenant la valeur par défaut (que cette valeur soit None ou autre).
Quant au module Shared, pour...
Tu as bien vu, le fold "canonique" applique exactement un morphisme par constructeur, ici il n'y aurait donc qu'un seul morphisme de type 'a * 'b list → 'b.
(je vais révoir ce passage)
Sinon, il...
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.