Comments on: Union d’un ensemble d’intervalles http://sametmax.com/union-dun-ensemble-dintervalles/ Du code, du cul Mon, 28 Oct 2019 11:54:55 +0000 hourly 1 https://wordpress.org/?v=4.9.7 By: Fred http://sametmax.com/union-dun-ensemble-dintervalles/#comment-147806 Wed, 05 Nov 2014 15:18:17 +0000 http://sametmax.com/?p=4572#comment-147806 Bonjour,
Je souhaite écrire ce super algo en pascal.
Ne connaissant pas le Python, je n’ai pas compris toutes les subtilités du code et je me pose 2 questions:
– Pourquoi supprimer les éléments lorsqu’ils sont égaux entre la liste de début et la liste de fin (cas du else) ?
On pourrait avoir un intervalle [10,10] qu’il faut conserver.
– Lorsque l’on trie la liste de début en ordre croissant ne faut-il pas également supprimer les doublons ? Idem pour la liste de fin.
Merci beaucoup pour vos réponses.

]]> By: OPi http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6367 Sat, 23 Feb 2013 10:44:33 +0000 http://sametmax.com/?p=4572#comment-6367 Je crois qu’il n’est pas si compliqué, et plus court si tu enlèves les assertions qui ne sont là que par sécurité.

Faire attention à ce que la fonction ordered_intervals_to_disjoint_intervals_iter() est un générateur.

Si tu as des questions n’hésite pas.

]]> By: Recher http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6330 Thu, 21 Feb 2013 10:57:13 +0000 http://sametmax.com/?p=4572#comment-6330 Ça m’a l’air un peu plus compliqué comme code. Mais peut-être plus rapide au final.

Je regarde tout ça en détail ce week-end, et je te dis ce que j’en pense, (si j’en pense quelque chose).

]]> By: OPi http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6277 Mon, 18 Feb 2013 21:08:14 +0000 http://sametmax.com/?p=4572#comment-6277 J’avoue humblement n’avoir pas très bien compris la bonne solution avec les niveaux, néanmoins je vous présente “fièrement” ma propre solution, de complexité en O(n*log(n)).

Une première fonction intervals_to_ordered_intervals() travaille en créant deux séquences avec les intervalles, ordonnées l’une sur le premier élément, l’autre sur le deuxième, ce qui permet de rassembler les intervalles contigus. O(n*log(n))

Ensuite une deuxième fonction ordered_intervals_to_disjoint_intervals_iter() parcourt la séquence ordonnée et “nettoyée” par la première fonction pour remplacer les intervalles qui se chevauchent. O(n)

Voir le code pour plus de détails :
intervals_to_disjoint_intervals

]]> By: OPi http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6265 Mon, 18 Feb 2013 15:01:28 +0000 http://sametmax.com/?p=4572#comment-6265 C’est une blague de mathématiciens. Citée ici Logiciels Libres et Entreprises comme exemple de ce qu’il ne faut pas faire.
Moi je la connaissais plutôt comme la différence entre un physicien et un mathématicien.

Je me suis pris au jeu des intervalles et tente d’implémenter mon propre algorithme…

]]> By: Sam http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6262 Mon, 18 Feb 2013 14:19:08 +0000 http://sametmax.com/?p=4572#comment-6262 Lol. Blague d’informaticien à la con.

]]> By: kontre http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6261 Mon, 18 Feb 2013 12:44:19 +0000 http://sametmax.com/?p=4572#comment-6261 Vous savez comment on fait des œufs durs avec une casserole ? On remplit d’eau la casserole, on fait bouillir, on met les œufs, et 5 min après c’est bon.
Vous savez comment on fait des œufs durs avec un casserole d’eau bouillante ? On vide la casserole et on se ramène au problème précédent.

(Et pour que ce soit plus facile à éplucher, passez-les dans l’eau froide directement après la cuisson)

]]> By: Safran http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6258 Mon, 18 Feb 2013 07:53:21 +0000 http://sametmax.com/?p=4572#comment-6258 C’est surtout que tu as astucieusement utilisé cette approche, même sans la connaitre, pour un problème qui n’a rien a voir.
Je pense que d’autres l’ont utilisée avant toi, mais je ne suis pas sûr que j’y aurais pensé moi-même, alors que je connais l’événementiel.
Ça rejoint ce que tu dis à la fin de l’article : si on arrive à se rapporter à un problème connu, on est gagnant.

]]> By: nerbrume http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6257 Mon, 18 Feb 2013 07:40:58 +0000 http://sametmax.com/?p=4572#comment-6257 Merci pour l’article. Et les precisions de Safran permettent de partiellement répondre à la question que je m’etais posé: OK, ton algo, il est cool, lisible, efficace, mais comment faire pour le trouver/y penser ? Parceque si on se doute bien qu’en utilisant le plus de fonctions du langage, on sera mieux optimisé (et lisible), encore faut-il trouver le moyen de le faire. Je doute que d’arriver un jour à resoudre un probleme similaire en me disant “Oh, tient, et si j’essayais de resoudre ca en utilisant sort() ? “

]]> By: recher http://sametmax.com/union-dun-ensemble-dintervalles/#comment-6255 Sun, 17 Feb 2013 23:08:36 +0000 http://sametmax.com/?p=4572#comment-6255 Ah merci pour l’étalage de science. Je savais pas que mon approche avait un nom générique. Pour moi, l’événementiel c’est des hôtesses cochonnes en tailleur, des toilettes toujours occupées, et des difficultés à tenir dans ses mains un verre de punsch + une verrine aux crevettes + la petite fourchette de la verrine.

J’avais pas de compte flattr, je viens de m’en créer un pour l’occasion. Je pige pas comment on connecte le compte à la prose que je raconte ici. Plus d’infos à ce sujet dans les notes privées du blog.

]]>