Good data structure for finding date intervals including a given date
Hello, I have a long list of n date intervals that gets added or suppressed intervals regularly. I am looking for a fast way to find the intervals containing a given date, without having to check all intervals (less than O(n)). Do you know the best way to do this in Python with the stdlib? A variant of the red black trees can do the job quickly [1], is this a good enough use case to discuss the inclusion of a red black tree implementation in the stdlib? This has been discussed here: http://bugs.python.org/issue1324770 , and lack of good use case was the reason the bug was closed. A dict implemented with red black trees is slower (but not too slow) at inserting, searching and deleting but the dict is always kept ordered. Bigger projects have their own implementation of ordered dict so such datastructures in the standard library would help the porting of the project to other platforms. Take the example of the zodb and the C-only implementation of the btree: btree in the stdlib in Python would help the porting to GAE or pypy [2]. Cheers, [1] in the "Cormen" book: http://en.wikipedia.org/wiki/Introduction_to_Algorithms [2] https://blueprints.launchpad.net/zodb/+spec/remove-btree-dependency -- http://mail.python.org/mailman/listinfo/python-list
Re: Good data structure for finding date intervals including a given date
> Since you say "intervals" in plural here, I assume that they can overlap?
Yes,
For instance, there are the following intervals :
[[1, 10],
[4, 7],
[6, 15],
[11, 17]]
asking for the intervals including 5, the returned value should be
[[1, 10],
[4, 7]]
The idea here to make it fast is to have done some preprocessing at
insertion time, so that not all intervals are processed at query time.
On Sat, May 12, 2012 at 2:30 PM, Karl Knechtel wrote:
> On Sat, May 12, 2012 at 8:17 AM, Jean-Daniel
> wrote:
>> I am looking for a fast way to find the intervals
>> containing a given date, without having to check all intervals (less
>> than O(n)).
>
> Since you say "intervals" in plural here, I assume that they can overlap?
>
> --
> ~Zahlman {:>
> --
> http://mail.python.org/mailman/listinfo/python-list
--
http://mail.python.org/mailman/listinfo/python-list
Re: Good data structure for finding date intervals including a given date
On Sun, May 13, 2012 at 2:29 PM, Alec Taylor wrote: > There is an ordered dict type since Python 3.1[1] and Python 2.7.3[2]. Ordered dict are useful, but they only remember the ordered in which they were added, you can not order them a on key. Thanks for the links. > > If you are looking for the best possible self-sorting structure for > searching, then perhaps you are looking for what's outlined in the > 2002 article by Han & Thorup: Integer Sorting in O(n sqrt(log log n)) > Expected Time and Linear Space[3]. > > [1] http://www.python.org/getit/releases/3.1/ > [2] http://www.python.org/getit/releases/2.7.3/ > [3] http://dl.acm.org/citation.cfm?id=645413.652131 > > On Sat, May 12, 2012 at 10:17 PM, Jean-Daniel > wrote: >> >> Hello, >> >> I have a long list of n date intervals that gets added or suppressed >> intervals regularly. I am looking for a fast way to find the intervals >> containing a given date, without having to check all intervals (less >> than O(n)). >> >> Do you know the best way to do this in Python with the stdlib? >> >> A variant of the red black trees can do the job quickly [1], is this a >> good enough use case to discuss the inclusion of a red black tree >> implementation in the stdlib? >> >> This has been discussed here: http://bugs.python.org/issue1324770 , >> and lack of good use case was the reason the bug was closed. A dict >> implemented with red black trees is slower (but not too slow) at >> inserting, searching and deleting but the dict is always kept ordered. >> Bigger projects have their own implementation of ordered dict so such >> datastructures in the standard library would help the porting of the >> project to other platforms. Take the example of the zodb and the >> C-only implementation of the btree: btree in the stdlib in Python >> would help the porting to GAE or pypy [2]. >> >> Cheers, >> >> [1] in the "Cormen" book: >> http://en.wikipedia.org/wiki/Introduction_to_Algorithms >> [2] https://blueprints.launchpad.net/zodb/+spec/remove-btree-dependency >> -- >> http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
executing a function with feeding its global variables
Hello, I am writing a small framework where the user which writes a function can expect some global variable to be set in the function namespace. The user has to write a function like this: """ # function.py from framework import, command, run @command def myfunc(): print HOST if __name__=="__main__": run() """ command() registers the function, and run() evaluates or execute the function within an environment or a namespace where HOST has been automagically set. Question: how can write run in a way that when using run() in a script, the decorated function will be run with the special names made available? Here is the code for this, which does not work as intended because the 'HOST' can not be found when evaluating the decorated function """ # framework.py HOST = '192.168.0.1' PORT = 12345 commands = [] def command(f): commands.append(f) return f def run(): for f in commands: assert globals()['HOST'] exec 'f()' in globals(),locals() if __name__=='__main__': @command def info(): print HOST,PORT run() """ Note that the assert makes sure the HOST variable is indeed present in the globals when running the function. When running function.py, I get an NameError exception. When I put the func function in the framework module and execute framework.py as a script, this works fine, the global HOST is available in the func namespace which gets printed. I tried many combinations of eval() or exec as well as many combinations for the globals() and locals() mapping fed to eval/exec without success. Thank you for your help -- http://mail.python.org/mailman/listinfo/python-list
Re: executing a function with feeding its global variables
On Sat, Feb 12, 2011 at 7:25 PM, Peter Otten <__pete...@web.de> wrote: > Jean-Daniel wrote: > >> Hello, >> >> I am writing a small framework where the user which writes a function >> can expect some global variable to be set in the function namespace. >> >> The user has to write a function like this: >> """ >> # function.py >> from framework import, command, run >> >> @command >> def myfunc(): >> print HOST >> >> if __name__=="__main__": >> run() >> """ >> >> command() registers the function, and run() evaluates or execute the >> function within an environment or a namespace where HOST has been >> automagically set. >> >> Question: how can write run in a way that when using run() in a >> script, the decorated function will be run with the special names made >> available? >> >> Here is the code for this, which does not work as intended because the >> 'HOST' can not be found when evaluating the decorated function >> >> """ >> # framework.py >> HOST = '192.168.0.1' >> PORT = 12345 >> >> commands = [] >> >> def command(f): >> commands.append(f) >> return f >> >> def run(): >> for f in commands: >> assert globals()['HOST'] >> exec 'f()' in globals(),locals() >> >> if __name__=='__main__': >> >> @command >> def info(): >> print HOST,PORT >> >> run() >> """ >> >> Note that the assert makes sure the HOST variable is indeed present in >> the globals when running the function. When running function.py, I get >> an NameError exception. When I put the func function in the framework >> module and execute framework.py as a script, this works fine, the >> global HOST is available in the func namespace which gets printed. I >> tried many combinations of eval() or exec as well as many combinations >> for the globals() and locals() mapping fed to eval/exec without >> success. > > Every module has its own global namespace, and a function is looking for > global variables in the namespace it is defined in, not the one where the > function is called from. A function defined in Python carries its global > namespace with it as the __globals__ attribute (func_globals in older Python > versions). > > def run(): > for f in commands: > f.__globals__.update(HOST=HOST, PORT=PORT) > f() > > Note that every function in the function's module will see the extra > variables. Cool, thanks. I read here: http://docs.python.org/reference/datamodel.html about the func_globals and how it is a read only attribute. I incorrectly thought that this dictionary was read only because the reference was read only. > > Peter > -- > http://mail.python.org/mailman/listinfo/python-list > -- http://mail.python.org/mailman/listinfo/python-list
extra room in Paris in your are stuck at the airport
Hello, I live in Paris, my roommate and I would gladly host a poor soul blocked at the airport due to the ash cloud. See me for details, Cheers, PS: disambiguation: talking about real physical cloud here... :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Not this one the other one, from a dictionary
Building on the answers of the others, a simple one liner, no side
effect, not the fastest I guess:
>>> d={'a': 'bob', 'b': 'stu'}
>>> set( d.keys() ).difference( [ 'a' ] ).pop()
'b'
Note the square brackets for the parameter of difference(). 'The
string 'a' and the list [ 'a' ] are both iterable but really are
different.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Distributing Python-programs to Ubuntu users
Maybe the distutils list is more adapted for this question: The Zope community uses zc.sourcerelease to build rpm http://www.mail-archive.com/distutils-...@python.org/msg06599.html Buildout is said to have undocumented features to build packages. Tarek Ziade is working debian package with 'distribute'. Cheers, On Fri, Sep 25, 2009 at 8:15 AM, Olof Bjarnason wrote: > Hi! > > I write small games in Python/PyGame. I want to find a way to make a > downloadable package/installer/script to put on my webpage, especially > for Ubuntu users. > > I've skimmed a couple of tutorials on how to generate .deb-files, but, > wow, it's a whole new skill set to do that! > > Does anyone have any hint on a more economic way of creating > single-file distribution packages for Python+PyGame projects? Maybe > some GUI-tool that automates the .deb file creation process, but > targetting Python specifically and not C++. > > /Olof > -- > http://mail.python.org/mailman/listinfo/python-list > -- Rasterization Zion babylon -- http://mail.python.org/mailman/listinfo/python-list
