Je suis en train de développer une routine heuristique et j'ai besoin de maintenir une séquence/tableau/liste triée. J'ai entendu dire que le timsort est rapide pour maintenir l'ordre des séquences avec des sous-séquences déjà triées. D'autre part, ce dont j'ai besoin est assez simple. Après le tri initial de la séquence, je dois répéter l'une des opérations suivantes à chaque étape:timsort ou manuellement en maintenant une séquence triée, ce qui est plus efficace?
Supprimer l'élément min. Visitez le plus petit
Kélément.insérer un élément et maintenir l'ordre.
timsort semble avoir une meilleure complexité de O (n). Naively, je peux mettre en œuvre l'opération 3 en appelant timsort pour obtenir O (n). Mais ces opérations doivent être répétées plusieurs fois. Je me demandais si maintenir manuellement une séquence triée (tableau ou liste) ou faire un partial_sort à chaque étape serait plus rapide, et si oui, quelles sont les complexités.
Pour la divulgation, j'utilise C++, et des exemples en C++/C++ 11 seraient nécessaires si nécessaire.
Merci,
pourriez-vous effectuer des tâches ensemble? c'est-à-dire regrouper plusieurs éléments et les trier, mémoriser plusieurs éléments à supprimer et les supprimer tous en même temps? Ou est-ce ce que vous demandez? – Daniel
non, je ne peux pas, car les étapes qui suivent dépendent de quel élément est le plus petit, ou est supprimé. L'insertion/suppression doit donc être faite par élément. – tinlyx
Lorsque vous dites "maintenir manuellement", voulez-vous dire mettre les données en mémoire cache après les avoir triées et les utiliser la prochaine fois au lieu de les utiliser à chaque fois? Parce que "manuellement" pour moi signifie parcourir les données à la main et en cliquant sur "supprimer": P – Daniel