Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre habitué
    Tirer un élément aléatoire parmi les plus grands éléments d'un std::vector
    Bonjour je suis étudient et je travaille actuellement sur un alpha-beta dans un jeux ou il est fréquent que plusieurs coup aient la même valeurs.

    Mettons que mon algorithme me sorte le tableau de tuple (coup, valeur) suivant :

    [c1:23, c2:-9, c3:23, c4:12, c5:23]

    Je souhaite choisir un coup aléatoirement parmi c1, c3 et c5. Je voudrais donc savoir si la STL permet de faire ça simplement.

    Merci d'avance.

  2. #2
    Expert éminent sénior
    je dirai oui, en utilisant un std::sort et un comparator bien pensé
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  3. #3
    Membre éprouvé
    Si le problème est de tirer un indice pair/impair :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    std::vector<std::tuple<Coup,Valeur>> v;
     
    int indice_pair = std::rand() % (v.size() / 2) * 2;
    int indice_impair = std::rand() % ((v.size()-1) / 2) * 2 + 1;

  4. #4
    Membre habitué
    Citation Envoyé par leternel Voir le message
    je dirai oui, en utilisant un std::sort et un comparator bien pensé
    Merci pour ta réponse, si je comprend bien, je modifie mon comparateur de tuple

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    bool tupleCoup::greater(std::tuple<Coup, int> a, std::tuple<Coup, int> b)
    {
    	return std::get<1>(a) > std::get<1>(b);
    }


    de la manière suivante :

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    bool tupleCoup::greater(std::tuple<Coup, int> a, std::tuple<Coup, int> b)
    {
    	if (std::get<1>(a) > std::get<1>(b))
    		return true;
    	else if (std::get<1>(a) == std::get<1>(b))
    		return ((rand()%100) >= 50);
    	return false;
    }


    La liste est bien triée dans l'ordre décroissant mais les élléments egaux sont mélangés.

    Merci pour ton aide

  5. #5
    Expert confirmé
    Il serait intéressant de faire des tests pour voir si la répartition est bonne. Il est probable que c1, c3 et c5 n'aient pas une chance sur trois d'être tiré chacun.

  6. #6
    Rédacteur/Modérateur

    Je conseille la lecture de http://en.wikipedia.org/wiki/Fisher%...ing_algorithms

    Sinon, et si tu n'as pas des contraintes de perf trop drastiques, un simple tri, un comptage du nombre de valeurs identiques, puis un choix parmi ces valeurs me semble le plus simple.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  7. #7
    Membre habitué
    Citation Envoyé par Iradrille Voir le message
    Il serait intéressant de faire des tests pour voir si la répartition est bonne. Il est probable que c1, c3 et c5 n'aient pas une chance sur trois d'être tiré chacun.
    En effet, la répartition dépend du tri implémenté par std::sort, (cf. ici), mais bon on peut pas vraiment savoir quel tri est (sera) implémenté, du coup ça semble difficile de prédire si la répartition sera uniforme ou non (de toute façon les stateux dirons que ça suit une loi normale ). Mais à la rigueur c'est pas grave.

    Citation Envoyé par JolyLoic Voir le message
    Je conseille la lecture de http://en.wikipedia.org/wiki/Fisher%...ing_algorithms

    Sinon, et si tu n'as pas des contraintes de perf trop drastiques, un simple tri, un comptage du nombre de valeurs identiques, puis un choix parmi ces valeurs me semble le plus simple.
    Enfaite j'ai plus des contraintes de perf (l'algo s'exécute sur un temps limité) que sur répartition. Tout ce qui compte c'est que mon IA ne bouge pas tout le temps le même pion (dans ce jeu il est très risqué et du coup l'IA campe).

  8. #8
    Expert confirmé
    Citation Envoyé par ahoff Voir le message
    En effet, la répartition dépend du tri implémenté par std::sort, (cf. ici), mais bon on peut pas vraiment savoir quel tri est (sera) implémenté, du coup ça semble difficile de prédire si la répartition sera uniforme ou non (de toute façon les stateux dirons que ça suit une loi normale ). Mais à la rigueur c'est pas grave.
    Que ce soit un Quicksort ou autre, ça sera un tri en O(n log(n)), je vois mal la STL implémenter un BubleSort ou autre en O(n²), bien que ça peut être plus rapide dans certains cas précis.
    (Enfin il est possible que le type de tri change en fonction de la taille du conteneur, mais c'est à prendre en compte ici)

    Du coup, comme propose JolyLoic, si tu fais un tri "normal" (O(n log(n)), suivi d'une recherche linéaire pour trouver le nombre de coups optimaux (O(n)), suivi d'un choix aléatoire parmi ces coups optimaux (O(1)), tu restes en O(n log(n)) mais avec une meilleure répartition.

  9. #9
    Rédacteur/Modérateur

    Voire même, si tu te moques de louper certains résultats, tu fais un partial_sort pour ne récupérer que les 15 premiers résultats (c'est du n log(m), avec m = 15, quelque soit n). Ensuite, parmi les valeurs égales dans ces 15 premiers résultats, tu sélectionne un au hasard.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.