Tester l'absence de répétition dans un tableau

Répondre

Messages : 0

Inscription : 08 août 2017 23:42

Profil de l'utilisateur : Élève de lycée

Tester l'absence de répétition dans un tableau

Message par Desert » 01 déc. 2017 00:59

Salut ! J'aimerais savoir s'il y'a un moyen optimisé ( c-a-d meilleur que l'algo naïf en O(n²)) pour tester l'absence de répétition d'une valeur dans un tableau en Caml.
Je me doute bien que ça existe, mais je sature et j'arrive pas à trouver (ou à expliquer pourquoi il n'en existerait pas). Merci de votre aide.

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par darklol » 01 déc. 2017 04:10

Si tu peux utiliser une structure de données auxiliaire avec insertion et recherche en O(f(n)), alors tu as un algorithme en O(n f(n)).

Exemple si tu peux hasher tes données: table de hashage, insertion et recherche en O(1), tu as un algorithme en O(n), et c’est évidemment optimal.

Exemple si tu peux trier tes données: arbre binaire rouge-noir, insertion et recherche en O(log n), tu as un algorithme en O(n log n).
ENS Lyon
Ingénieur de recherche

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par Errys » 01 déc. 2017 08:48

Si les éléments sont des entiers et sont bornées on a un algorithme en O(N) sans table de hachage, en utilisant une stratégie similaire au counting sort.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?

Messages : 0

Inscription : 08 août 2017 23:42

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par Desert » 01 déc. 2017 09:52

Merci de vos réponses.
Je vois que les algos pour y parvenir ne sont pas triviaux, donc j'imagine que l'épreuve attendait un algo naïf en O(n²).

Comment parvenir en O(n) pour trier ET rechercher un élément sur un tableau Errys ? Ou alors tu voulais dire O(nlogn) ?

EDIT : Ah j'ai compris N doit être la borne ?

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par fakbill » 01 déc. 2017 10:55

il y a un petit gag ici.
Si on suppose disons qu'on est sur R alors on n'a pas mieux que n log n.
Mais mais mais "Si les éléments sont des entiers et sont bornées" : informatiquement ça n'a pas trop de sens :) Tous les nombres machines sont bornés (sauf inf et NaN en IEEE754 mais bon...) et "entier" ne veut rien dire non plus. Si j'ai disons 64bits, ça représente peut etre un flotant mais je peux aussi le voir comme un brave entier 64bits. bref, tout ça pour dire que l'informatique *machine*, ça se passe toujours sur une partie bornée de N.
Je dis *machine* car on peut aussi avoir des nombres en representation "infinie" (la bonne blague en réalité) mais dans ce cas un nombre est une liste et il faut un algo et non une seule et unique instruction CPU pour faire + ou *.

autre partie du fun : la complexité en temps c'est bien mais :
1) c'est souvent un O donc on a des algo "meilleurs" mais dont les constantes sont horribles et donc en pratique on prend parfois du n² au lieu de n log n avec une constant horrible (si on sait qu'on restera sur des petits jeux de données).
2) il faut regarder la complexité mémoire. Si on autant de mémoire qu'on veut, certains algo deviennent triviaux.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par siro » 01 déc. 2017 10:59

fakbill a écrit :
01 déc. 2017 10:55
bref, tout ça pour dire que l'informatique *machine*, ça se passe toujours sur une partie bornée de N.
Plutôt dans Z/nZ. (Avec n souvent puissance de 2.)
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par Errys » 01 déc. 2017 13:20

Je pensais plutôt au cas où l'on avait un tableau de chaine de caractère par exemple, ou un objet quelconque qui ne peut pas être représenté par un simple entier sans perdre d'informations.

Mais sinon c'est vrai que ça devient intéressant dans R, comment ferais tu une stratégie similaire au counting sort avec des flottante ? Je ne vois pas trop de manière de convertir un flottant en entier (pour l'utiliser comme index) à moins de multiplier par 10^(precision) et donc avoir besoin de beaucoup trop d'espaces...
Desert a écrit :
01 déc. 2017 09:52
Merci de vos réponses.
Je vois que les algos pour y parvenir ne sont pas triviaux, donc j'imagine que l'épreuve attendait un algo naïf en O(n²).

Comment parvenir en O(n) pour trier ET rechercher un élément sur un tableau Errys ? Ou alors tu voulais dire O(nlogn) ?

EDIT : Ah j'ai compris N doit être la borne ?
Si tes entiers étaient compris entre 0 et 100 tu aurais un tableau de booleen indexé de 0 à 100 initialisé à false.
Tu parcours ta liste et pour chaque élément tu regardes si tu l'as déjà vu, si c'est le cas, c'est qu'il y a un élément en double. D'où le O(N) (N étant le nombre d'éléments)
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?

Messages : 0

Inscription : 08 août 2017 23:42

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par Desert » 01 déc. 2017 13:46

"Si tes entiers étaient compris entre 0 et 100 tu aurais un tableau de booleen indexé de 0 à 100 initialisé à false.
Tu parcours ta liste et pour chaque élément tu regardes si tu l'as déjà vu, si c'est le cas, c'est qu'il y a un élément en double. D'où le O(N) (N étant le nombre d'éléments)"

Merci ! J'ai compris ;)

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par darklol » 01 déc. 2017 14:52

Errys a écrit :
01 déc. 2017 08:48
Si les éléments sont des entiers et sont bornées on a un algorithme en O(N) sans table de hachage, en utilisant une stratégie similaire au counting sort.
Ça n’est rien d’autre qu’une table de hashage, avec une fonction de hash très simple: l’identité.
ENS Lyon
Ingénieur de recherche

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Tester l'absence de répétition dans un tableau

Message par fakbill » 01 déc. 2017 16:39

siro : si tu veux. c'était juste pour dire "PAS sur R ni même sur une partie de R". On a N bits, donc on peut représenter 2^N machins qu'on appelle des nombres car les operations standards ressemblent à celle sur N ou sur R...mais elle ne font que ressembler.

Sinon oui, les buckets et le hachage c'est puissant et souvent oublié/mal compris.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre