|> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" |> wrote:
|> >Est-on toujours obligé de trier un container pour pouvoir |> >enlever les doublons?
[...]
Avec un bon hachage, utiliser hash_set pourrait être O(n).
Et "trouver un bon hachage", c'est O( ? ) ? ;-)
--
Français *==> "Musique renaissance" <==* English midi - facsimiles - ligatures - mensuration http://anaigeon.free.fr | http://www.medieval.org/emfaq/anaigeon/ Alain Naigeon - - Strasbourg, France
James Kanze
"Alain Naigeon" writes:
|> "James Kanze" a écrit dans le message news: |>
|> > |> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" |> > |> wrote:
|> > |> >Est-on toujours obligé de trier un container pour pouvoir |> > |> >enlever les doublons?
|> [...]
|> > Avec un bon hachage, utiliser hash_set pourrait être O(n).
|> Et "trouver un bon hachage", c'est O( ? ) ? ;-)
Ça dépend de la clé. Il existe de bonnes fonctions, connues, pour les chaînes de caractère, par exemple, et un hachage des entiers plus ou moins aléatoire n'est pas difficile non plus. Mais effectivement, on n'est jamais à l'abri d'un cas pervers.
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
"Alain Naigeon" <anaigeon@free.fr> writes:
|> "James Kanze" <kanze@alex.gabi-soft.fr> a écrit dans le message news:
|> 863cb23yne.fsf@alex.gabi-soft.fr...
|> > |> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
|> > |> wrote:
|> > |> >Est-on toujours obligé de trier un container pour pouvoir
|> > |> >enlever les doublons?
|> [...]
|> > Avec un bon hachage, utiliser hash_set pourrait être O(n).
|> Et "trouver un bon hachage", c'est O( ? ) ? ;-)
Ça dépend de la clé. Il existe de bonnes fonctions, connues,
pour les chaînes de caractère, par exemple, et un hachage des
entiers plus ou moins aléatoire n'est pas difficile non plus. Mais
effectivement, on n'est jamais à l'abri d'un cas pervers.
--
James Kanze mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
|> > |> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" |> > |> wrote:
|> > |> >Est-on toujours obligé de trier un container pour pouvoir |> > |> >enlever les doublons?
|> [...]
|> > Avec un bon hachage, utiliser hash_set pourrait être O(n).
|> Et "trouver un bon hachage", c'est O( ? ) ? ;-)
Ça dépend de la clé. Il existe de bonnes fonctions, connues, pour les chaînes de caractère, par exemple, et un hachage des entiers plus ou moins aléatoire n'est pas difficile non plus. Mais effectivement, on n'est jamais à l'abri d'un cas pervers.
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
