Comment faire pour générer une liste triée?
Voici une étrange question pour vous les gars,
J'ai une belle liste triée à qui je tiens à rendre aléatoire. Comment pourrais-je aller sur le faire?
Dans mon application, j'ai une fonction qui retourne une liste de points qui décrivent le contour d'un discrétisé objet. En raison de la façon dont le problème est résolu, la fonction renvoie une belle liste ordonnée. j'ai une deuxième limite décrite en mathématiques et souhaitez déterminer si les deux objets se croisent les uns les autres. J'ai simplement itterate plus de points et de déterminer si un point est à l'intérieur de la limite mathématique.
La méthode fonctionne bien, mais je veux augmenter la vitesse de randomisation du point de données. Car il est probable que que mon mathématique limite sera recouverte par une série de points qui sont juste à côté les uns des autres, je pense qu'il serait judicieux de vérifier une liste aléatoire plutôt que de parcourir un agréable triés un (puisqu'il ne prend d'un seul coup à déclarer une intersection).
Donc, toutes les idées sur la façon dont j'allais sur randomisation une liste ordonnée?
- Êtes-Vous sûr que le temps passé sur la randomisation est-il la peine? Si non, à mesure 🙂
Vous devez vous connecter pour publier un commentaire.
Utilisation
std::random_shuffle
. Si vous souhaitez appliquer la méthode, vous devriez regarder la Shuffle de Fisher-Yates.Vous pouvez essayer le random_shuffle algorithme, mais notez que cela ne fonctionne pas sur les
list
car il nécessite des itérateurs à accès aléatoire. Vous pouvez l'utiliser sur unvector
oudeque
, si.En supposant que votre "liste" ne signifie pas une liste chaînée, mais quelque chose qui prend en charge l'accès aléatoire (par exemple, un tableau, std::vector, ou std::deque), std::random_shuffle pourrait être utile.
Mais la question serait de savoir si le moteur d'exécution nécessaires pour rendre aléatoire la liste pourrait pas être plus de l'exécution de la traverser de façon séquentielle.
Peut-être ce que vous avez vraiment besoin de faire est de ne pas réellement aléatoire, mais plutôt que les lire dans un ordre autre que l'avant vers l'arrière. Par exemple, si la liste est n de membres, peut-être vous devriez processus 1, n 2, n-1, 3, n-2, etc. ou 1, n/2, 2, n/2 + 1, 3, n/2 +2, etc.
Si vous avez toujours le même nombre de points, ou si le nombre de points tombe dans un petit ensemble fini, vous pourriez produire une commande de point d'évaluation pour chaque nombre possible de points d'avance en une seule fois, soit vraiment aléatoire ou peut-être calculé avec soin, d'une certaine façon.