Comments on: Union d’un ensemble d’intervalles

By: Fred

Fred — Wed, 05 Nov 2014 15:18:17 +0000

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

OPi — Sat, 23 Feb 2013 10:44:33 +0000

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

Recher — Thu, 21 Feb 2013 10:57:13 +0000

Ç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

OPi — Mon, 18 Feb 2013 21:08:14 +0000

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

OPi — Mon, 18 Feb 2013 15:01:28 +0000

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

Sam — Mon, 18 Feb 2013 14:19:08 +0000

Lol. Blague d’informaticien à la con.

By: kontre

kontre — Mon, 18 Feb 2013 12:44:19 +0000

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

Safran — Mon, 18 Feb 2013 07:53:21 +0000

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

nerbrume — Mon, 18 Feb 2013 07:40:58 +0000

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

recher — Sun, 17 Feb 2013 23:08:36 +0000

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.