Tester l'absence de répétition dans un tableau
Tester l'absence de répétition dans un tableau
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.
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.
Re: Tester l'absence de répétition dans un tableau
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).
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
Ingénieur de recherche
Re: Tester l'absence de répétition dans un tableau
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-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: Tester l'absence de répétition dans un tableau
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 ?
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 ?
Re: Tester l'absence de répétition dans un tableau
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.
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Tester l'absence de répétition dans un tableau
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.
Re: Tester l'absence de répétition dans un tableau
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...
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)
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...
Si tes entiers étaient compris entre 0 et 100 tu aurais un tableau de booleen indexé de 0 à 100 initialisé à false.Desert a écrit : ↑01 déc. 2017 09:52Merci 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 ?
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-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: Tester l'absence de répétition dans un tableau
"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
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
Re: Tester l'absence de répétition dans un tableau
Ç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
Ingénieur de recherche
Re: Tester l'absence de répétition dans un tableau
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.
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.