Magdoll wrote: >> One question you should ask yourself is: do you want all solutions? or >> just one? >> If you want just one, there's another question: which one? the one with >> the most intervals? any one? >> > > I actually don't know which solution I want, and that's why I keep > trying different solutions :P > You should think about what is your data and what is probably the "best" solution.
>> If you want all of them, then I suggest using prolog rather than python >> (I hope I won't be flamed for advocating another language here). >> > > Will I be able to switch between using prolog & python back and forth > though? Cuz the bulk of my code will still be written in python and > this is just a very small part of it. > You'll have to popen a prolog interpreter and parse its output. Not very sexy. Moreover if you've never done prolog, well, you should be warned it's a "different" language (but still beautiful) with an important learning curve. Maybe not worth it for just one single problem. >> If you have a reasonable number of intervals, you're algorithm seems >> fine. But it is O(n**2), so in the case you read a lot of intervals and >> you observe unsatisfying performances, you will have to store the >> intervals in a cleverer data structure, see one of >> these:http://en.wikipedia.org/wiki/Interval_treehttp://en.wikipedia.org/wiki/Segment_tree >> > > Thanks! Both of these look interesting and potentially useful :) > Indeed. However these structures are clearly heavyweight if the number of intervals is moderate. I would consider them only if I expected more than several thousands of intervals. Cheers, RB -- http://mail.python.org/mailman/listinfo/python-list
