Comments on: Union d’un ensemble d’intervalles

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.

By: Safran

Safran — Sun, 17 Feb 2013 16:50:59 +0000

Je viens étaler ma science : c’est ce qu’on appelle l’approche événementielle.
Pour simuler un système dans le temps, par exemple des utilisateurs de vélib, il y a 3 approches.

1) purement discrète, on regarde ce qui se passe à l’instant 1 puis à l’instant 2 puis etc. Problème : c’est très long, il y a de grands moments sans qu’il ne se passe rien (la nuit), et on ne prend en compte que des instants entiers.

2) l’approche des simulationnistes, avec chaque trajet qui correspond à un thread ou quelque chose dans le genre… Grosse prise de tête, mais les simulationnistes, fidèles à leur habitude, disent “oh oui c’est bon !” même s’ils détestent.

3) L’approche décrite dans l’article, la meilleure dans la plupart des cas, où l’on dit “à tel instant futur, il y aura tel événement retenu quelque part en mémoire”. Par exemple, au début d’un trajet, on indique à quel moment et où aura lieu l’arrivée. Ensuite, on suit les événements dans l’ordre chronologique, de façon discrète, mais en allant uniquement à l’essentiel. Et ça permet effectivement de traiter des instant non entiers.

Fin de l’étalage de science, merci.