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

Modérateur : Michel Quercia

Répondre
Desert
Messages : 104
Enregistré le : mar. août 08, 2017 11:42 pm

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

Message par Desert » ven. déc. 01, 2017 1:59 am

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.

darklol
Messages : 803
Enregistré le : dim. avr. 19, 2015 12:08 am

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

Message par darklol » ven. déc. 01, 2017 5:10 am

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

Errys
Messages : 259
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

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

Message par Errys » ven. déc. 01, 2017 9:48 am

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-?

Desert
Messages : 104
Enregistré le : mar. août 08, 2017 11:42 pm

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

Message par Desert » ven. déc. 01, 2017 10:52 am

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 ?

Avatar du membre
fakbill
Messages : 11167
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

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

Message par fakbill » ven. déc. 01, 2017 11:55 am

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é.

Avatar du membre
siro
Messages : 3226
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

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

Message par siro » ven. déc. 01, 2017 11:59 am

fakbill a écrit :
ven. déc. 01, 2017 11:55 am
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.

Errys
Messages : 259
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

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

Message par Errys » ven. déc. 01, 2017 2:20 pm

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 :
ven. déc. 01, 2017 10:52 am
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-?

Desert
Messages : 104
Enregistré le : mar. août 08, 2017 11:42 pm

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

Message par Desert » ven. déc. 01, 2017 2:46 pm

"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 ;)

darklol
Messages : 803
Enregistré le : dim. avr. 19, 2015 12:08 am

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

Message par darklol » ven. déc. 01, 2017 3:52 pm

Errys a écrit :
ven. déc. 01, 2017 9:48 am
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

Avatar du membre
fakbill
Messages : 11167
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

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

Message par fakbill » ven. déc. 01, 2017 5:39 pm

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

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité