Algorithms in Python, #n+1
I have continued my research in literature algorithms in Python. The
algorithms in Knuth's volumes 1 -- 3 either have been incorporated
into Python, or they can be easily implemented with Python. Quite as
John Nagle said here. However, the Fascicles in Vol. 4 to my opinion
contain nontrivially useful material.
And, Vol. 2 has something interesting, however -- e. g. the statistical
tests on random number generators.
I have included in this entry a working Python program which carries
out the chi squared test on different random number generators. It
demonstrates the paradigm of building Knuth's equations directly into
one's Python program, instead of the DFA/FSA approach. Moreover,
someone over there may wish to test his/her random number generators.
Therefore, I feel that it is relevant to show this program (which is
about two pages long) in this context.
I have carried out the chi squared test on Python's own random number
generator, which to my knowledge is based on the Mersenne twister:
http://en.wikipedia.org/wiki/Mersenne_twister
and Knuth's (old) Linear Congruential method:
http://en.wikipedia.org/wiki/Linear_congruential_generator
If you run the program (with Python 3) you will see that the both
generators will pass the chi squared test.
# Random number generation and analysis after D. E. Knuth.
#
# See The Art of Computer Programming, VOL 2, Seminumerical Algorithms,
# 3rd Edition, pp. 1 --
#
# AJY 05-16-2012.
import math, random
# First do the MIX simulator.
# AJY 05-16-2012.
# -
# Python based MIX simulator.
#
# Written in the object oriented manner.
#
# AJY 05-16-2012.
#
# Do as follows:
#
# MIX_computer = MIXSIM(memory_size, word_size)
# A, X = MIX_computer.MUL(A, X)
#
# etc etc. in the same vein.
# This constitutes just a maximally simple demo.
class MIXSIM(object):
""" Maximally simple object oriented MIX simulator. """
def __init__(self, mem_size, word_size):
self.mem_size = mem_size
self.word_size = word_size
self.w = 10**word_size # Assume a base 10 computer,
after Knuth.
# No other methods in this class. I said it only constitutes a demo.
# --
class LCRNG(object):
""" The Linear Congruential Random Number Generator. AJY
05-16-2012. """
def __init__(self, modulus, multiplier, increment, seed):
self.modulus= modulus# Modulus == m in Knuth's text.
self.multiplier = multiplier # Multiplier == a in Knuth's text.
self.increment = increment # Increment == c in Knuth.
# Seed == X0 in Knuth.
self.reg_X = seed # Initial value X0 to Register X.
self.MIX= MIXSIM(5000, 12) # Demo sample MIX computer.
def rand(self):
# See Knuth VOL 2 on p. 12.
# Following calculate the next pseudo random integer:
self.reg_A = (self.multiplier * self.reg_X) % (self.MIX.w + 1)
# Transfer A to X for the next round.
self.reg_X = self.reg_A
# And now return a floating point number x such that 0 <= x < 1.
return float(self.reg_A) / float (self.modulus)
class chi_squared_test(object):
""" Instances are chi squared tests of random number generators. """
def __init__(self, generator_f, buckets, iterations, name):
self.generator_f = generator_f # The function to be tested.
self.buckets = buckets # How many discrete buckets are
used
self.iterations = iterations # The # of random numbers
generated.
self.name= name # name of this test.
self.B = [0] * self.buckets # initially all buckets are empty
def run_test(self):
""" Generate random numbers and place them in buckets. """
for i in range(self.iterations):
random_nr = self.generator_f() # Random number, in interval
[0, 1)
ind_bucket = int(self.buckets * random_nr) # Index, 0 ..
#buckets-1
self.B[ind_bucket] += 1
def chi2test(self):
""" Carry out the chi squared test of the material generated. """
# Calculate the chi squared statistics value. See Knuth VOL 2
# on Page 43.
Vsum = 0
for i in range(self.buckets):
Vsum += (self.B[i] - self.iterations * (1.0 /
float(self.buckets)))**2 \
/ (self.iterations * (1.0 / float(self.buckets)))
V = Vsum
print("\n Chi squared test. Name = ", self.name)
print("\n Chi squared value V = ", V)
print("\n Degrees of fr
Algorithms in Python, cont'd
I wrote here about some straightforward ways to program D. E. Knuth in Python, and John Nagle answered that the value of Knuth's book series to the programmer has been significantly diminished by the fact that many functionalities such as sorting and hashing have either been built in the Python language, or are available in libraries (à propos, as an aside, very many functionalities are available notably in the CPAN, the Comprehensive Perl Language Network. I wonder what were the corresponding repository with the Python language) Nagle's comment is to my opinion very true. So I carried out a search procedure -- and found two good sources of algorithms for the Python programmer: 1) Cormen-Leiserson-Rivest-Stein: Introduction to Algorithms, 2nd edition, ISBN 0-262-53196-8. The 3rd edition has been published, I don't know which one is the most recent one. 2) Atallah-Blanton: Algorithms and Theory of Computation Handbook, Second Edition, 2 books, ISBNs 978-1-58488-822-2 and 978-1-58488-820-8. This one in particular is really good as a general computer science source. The point of this entry is that my answer to Nagle's criticism is that numerous such more or less sophisticated algorithm reference books can be found. I intended to write some demonstrations in Python -- I chose the RSA cryptosystem from Cormen et al's book and the linear programming ellipsoid algorithm from Atallah-Blanton's book -- but I have not yet done so, it would have been straightforward but too time-consuming. yours, and V/R, Antti J Ylikoski Helsinki, Finland, the EU -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
On Thu, Jan 26, 2012 at 2:22 AM, Martin Schöön wrote: > On 2012-01-25, Chetan Harjani wrote: >> Thanks Alec for the link. U know I wanted to read this book by Simon >> Singh -> The Code Book, I hear its good. >> > It indeed is. I only remember one error, an error every Scandinavian > would have spotted. > > His book on Fermat's theorem is even better. I have read the Fermat's theorem, it is really good. -- Chetan H Harjani IIT Delhi -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
On 2012-01-25, Chetan Harjani wrote: > Thanks Alec for the link. U know I wanted to read this book by Simon > Singh -> The Code Book, I hear its good. > It indeed is. I only remember one error, an error every Scandinavian would have spotted. His book on Fermat's theorem is even better. /Martin -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
Thanks Alec for the link. U know I wanted to read this book by Simon Singh -> The Code Book, I hear its good. Thanks Nizamov for the link, I am really looking forward to join the class, and since its free, it is totally an asset. Yes Thijs I have seen this book, and since its such a big book, I am avoiding it right now but I really liked the author's style when I read his book on python language. Thanks Visgean, the links seem really valuable Thanking all with regards Chetan H Harjani IIT Delhi -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
There is this book (it´s free ebook) http://www.brpreiss.com/books/opus7/html/book.html , you can also check this list: http://programming-motherfucker.com/become.html#Python or if you want something more official then there is official wiki page: http://wiki.python.org/moin/PythonBooks ... 2012/1/25 Chetan Harjani > Is there any book or site on python algorithms which asks more and > teaches less, I don't want to get bored, and at the same time I want > to learn and act more. I use ubuntu. (just in case if its needed). > #ALGORITHMS > > > > -- > Chetan H Harjani > IIT Delhi > -- > http://mail.python.org/mailman/listinfo/python-list > -- PGP pub key: http://keyserver.pgp.com/vkd/SubmitSearch.event?SearchCriteria=visgean%40gmail.com http://www.abclinuxu.cz/lide/visgean/gpg A453 B7F3 33D9 3BE6 2B8A | F014 5347 EBAC 0A5A 3E92 Jabber: visg...@jabber.org | visg...@jabber.cz Github: http://github.com/Visgean -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
I assume you have seen this book? http://www.apress.com/9781430232377 Thijs On Wed, Jan 25, 2012, at 15:36, Chetan Harjani wrote: > Is there any book or site on python algorithms which asks more and > teaches less, I don't want to get bored, and at the same time I want > to learn and act more. I use ubuntu. (just in case if its needed). > #ALGORITHMS > > > > -- > Chetan H Harjani > IIT Delhi > -- > http://mail.python.org/mailman/listinfo/python-list > -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
2012/1/25 Chetan Harjani : > Is there any book or site on python algorithms which asks more and > teaches less, I don't want to get bored, and at the same time I want > to learn and act more. I use ubuntu. (just in case if its needed). > #ALGORITHMS There is a Stanford online class on Algorithms, which will start really soon. It is stated that Python may be used for home assignments. Maybe you are not too late. http://www.algo-class.org/ Best regards, S.Nizamov -- http://mail.python.org/mailman/listinfo/python-list
Re: Algorithms in Python
The thing about algorithms is they are applicable to many programming languages (in general). Read http://en.wikipedia.org/wiki/Turing_machine On Wed, Jan 25, 2012 at 9:06 PM, Chetan Harjani wrote: > Is there any book or site on python algorithms which asks more and > teaches less, I don't want to get bored, and at the same time I want > to learn and act more. I use ubuntu. (just in case if its needed). > #ALGORITHMS > > > > -- > Chetan H Harjani > IIT Delhi > -- > http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Algorithms in Python
Is there any book or site on python algorithms which asks more and teaches less, I don't want to get bored, and at the same time I want to learn and act more. I use ubuntu. (just in case if its needed). #ALGORITHMS -- Chetan H Harjani IIT Delhi -- http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
I'm not an expert on this, but wouldn't it be more dependent on the platform
than python version? Perhaps it is Windows 7 that is very slow. Perhaps my
processor architecture. Not sure...
Here are some for 3.1.2x64
>>> import timeit
>>> timeit.timeit('Lock()', 'from threading import Lock')
1.4162585386092708
>>> timeit.timeit('dict()', 'from threading import Lock')
0.2730348901369162
>>> timeit.timeit('list()', 'from threading import Lock')
0.1719480219512306
-Zac
On Fri, Jul 2, 2010 at 1:26 PM, Antoine Pitrou wrote:
> On Mon, 28 Jun 2010 16:46:41 -0700
> Zac Burns wrote:
> > In my experience it is far more expensive to allocate a lock in python
> then
> > it is the types that use them. Here are some examples:
> >
> > >>> timeit.timeit('Lock()', 'from threading import Lock')
> > 1.4449114807669048
> >
> > >>> timeit.timeit('dict()')
> > 0.2821554294221187
> >
> > >>> timeit.timeit('list()')
> > 0.17358153222312467
>
> I'm not sure what Python version on what machine you are using, but
> here (Python 2.7):
>
> >>> timeit.timeit('Lock()', 'from threading import Lock')
> 0.09944796562194824
> >>> timeit.timeit('dict()')
> 0.17817902565002441
> >>> timeit.timeit('list()')
> 0.19633007049560547
> >>> timeit.timeit('{}')
> 0.03823709487915039
> >>> timeit.timeit('[]')
> 0.05156302452087402
>
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
--
http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
On Mon, 28 Jun 2010 16:46:41 -0700
Zac Burns wrote:
> In my experience it is far more expensive to allocate a lock in python then
> it is the types that use them. Here are some examples:
>
> >>> timeit.timeit('Lock()', 'from threading import Lock')
> 1.4449114807669048
>
> >>> timeit.timeit('dict()')
> 0.2821554294221187
>
> >>> timeit.timeit('list()')
> 0.17358153222312467
I'm not sure what Python version on what machine you are using, but
here (Python 2.7):
>>> timeit.timeit('Lock()', 'from threading import Lock')
0.09944796562194824
>>> timeit.timeit('dict()')
0.17817902565002441
>>> timeit.timeit('list()')
0.19633007049560547
>>> timeit.timeit('{}')
0.03823709487915039
>>> timeit.timeit('[]')
0.05156302452087402
--
http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
On 29 Jun, 05:11, Ryan Kelly wrote: > Very interesting idea. Will it work if accessed through ctypes? > > ticker = ctypes.c_int.in_dll(ctypes.pythonapi,"_Py_Ticker") > ticker.value = 0x7fff > > Or does ctypes muck with the GIL in a way that would break this idea? > >>> ctypes.pythonapi It's a PyDLL, so it should not mock with the GIL. from contextlib import contextmanager import ctypes _Py_Ticker = ctypes.c_int.in_dll(ctypes.pythonapi,"_Py_Ticker") @contextmanager def atomic(): tmp = _Py_Ticker.value _Py_Ticker.value = 0x7fff yield _Py_Ticker.value = tmp - 1 Now we can do with atomic(): # whatever pass Just make sure we don't call extension code that releases the GIL :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
On Mon, 2010-06-28 at 19:45 -0700, sturlamolden wrote: > > > Many lockless algorithms that I have looked at thusfar require a > > > "Compare and Swap" operation. Does python have an equivalent to this? > > > Is python high level enough that it has something better than this or > > > it simply doesn't need it? > > Python does have a GIL, and contrary to the title, this has a lot to > do with the GIL. Specifically, any set of operations protected by the > GIL are atomic in the CPython interpreter. > > We can therefore get global synchronization 'for free', allowing 'lock > free' data structures that avoid using threading.Lock, and replaces it > with, well, nothing. :) > > How to do it (it takes tiny amounts of C or Cython): > > Take at look at page 14: > >http://www.dabeaz.com/python/UnderstandingGIL.pdf > > The critical part is the variable _Py_Ticker in Python's source file > ceval.c, which is declared volatile int. As it is not declared static > it is a global variable, and we can actually manipulate its value from > a C extension: > >extern volatile int _Py_Ticker; // evil!!! > > Now imagine temporarily setting _Py_Ticker to some ridiculous high > value like 0x7fff. That locks out all other threads, practically > forever, until we restore _Py_Ticker back to it's original value. > > What this gives us is global synchronization for free! The GIL is > there anyway, so it adds no additional overhead. Very interesting idea. Will it work if accessed through ctypes? ticker = ctypes.c_int.in_dll(ctypes.pythonapi,"_Py_Ticker") ticker.value = 0x7fff Or does ctypes muck with the GIL in a way that would break this idea? Ryan -- Ryan Kelly http://www.rfk.id.au | This message is digitally signed. Please visit r...@rfk.id.au| http://www.rfk.id.au/ramblings/gpg/ for details signature.asc Description: This is a digitally signed message part -- http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
> > Many lockless algorithms that I have looked at thusfar require a > > "Compare and Swap" operation. Does python have an equivalent to this? > > Is python high level enough that it has something better than this or > > it simply doesn't need it? Python does have a GIL, and contrary to the title, this has a lot to do with the GIL. Specifically, any set of operations protected by the GIL are atomic in the CPython interpreter. We can therefore get global synchronization 'for free', allowing 'lock free' data structures that avoid using threading.Lock, and replaces it with, well, nothing. :) How to do it (it takes tiny amounts of C or Cython): Take at look at page 14: http://www.dabeaz.com/python/UnderstandingGIL.pdf The critical part is the variable _Py_Ticker in Python's source file ceval.c, which is declared volatile int. As it is not declared static it is a global variable, and we can actually manipulate its value from a C extension: extern volatile int _Py_Ticker; // evil!!! Now imagine temporarily setting _Py_Ticker to some ridiculous high value like 0x7fff. That locks out all other threads, practically forever, until we restore _Py_Ticker back to it's original value. What this gives us is global synchronization for free! The GIL is there anyway, so it adds no additional overhead. By messing with _Py_Ticker we can force blocks of Python code to become atomic in the interpreter. With this hack we can therefore create data structures that are lock free relative to the CPython interpreter. It is evil, but very cheap compared to using threading.Lock. In fact it has exactly zero overhead: the GIL is there anyway, and it is already acquired! The safest placement of a _Py_Ticker hack is in a context manager. We have to make sure it gets restored to a sane value, even in presence of an exception. Enjoy :) P.S. If you get smart and think sys.setcheckinterval(sys.maxint) would do the trick, you are actually not that smart. It will lock our own thread out with a Poisson rate of 1./sys.getcheckinterval(). Thus we have to attack _Py_Ticker from C. P.P.S. And when we have taken control over the GIL, don't do anything that might release it from C (like reading from a file). We cannot afford to loose it :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
> > Many lockless algorithms that I have looked at thusfar require a > > "Compare and Swap" operation. Does python have an equivalent to this? > > Is python high level enough that it has something better than this or > > it simply doesn't need it? Python does have a GIL, and contrary to the title, this has a lot to do with the GIL. Specifically, any set of operations protected by the GIL are atomic in the CPython interpreter. We can therefore get global synchronization 'for free', allowing 'lock free' data structures that avoid using threading.Lock, and replaces it with, well, nothing. :) How to do it (it takes tiny amounts of C or Cython): Take at look at page 14: http://www.dabeaz.com/python/UnderstandingGIL.pdf The critical part is the variable _Py_Ticker in Python's source file ceval.c, which is declared volatile int. As it is not declared static it is a global variable, and we can actually manipulate its value from a C extension: extern volatile int _Py_Ticker; // evil!!! Now imagine temporarily setting _Py_Ticker to some ridiculous high value like 0x7fff. That locks out all other threads, practically forever, until we restore _Py_Ticker back to it's original value. What this gives us is global synchronization for free! The GIL is there anyway, so it adds no additional overhead. By messing with _Py_Ticker we can force blocks of Python code to become atomic in the interpreter. With this hack we can therefore create data structures that are lock free relative to the CPython interpreter. It is evil, but very cheap compared to using threading.Lock. In fact it has exactly zero overhead: the GIL is there anyway, and it is already acquired! The safest placement of a _Py_Ticker hack is in a context manager. We have to make sure it gets restored to a sane value, even in presence of an exception. Enjoy :) P.S. If you get smart and think sys.setcheckinterval(sys.maxint) would do the trick, you are actually not that smart. It will lock our own thread out with a Poisson rate of 1./sys.getcheckinterval(). Thus we have to attack _Py_Ticker from C. P.P.S. And when we have taken control over the GIL, don't do anything that might release it from C (like reading from a file). We cannot afford to loose it :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
On Mon, 2010-06-28 at 18:27 -0700, Zac Burns wrote:
>
>
>
> I've managed to avoid locking in some cases by using
> dict.setdefault() as a kind of atomic test-and-set operation.
> It's not a full compare-and-swap but you could implement a
> simple locking scheme using it like this:
>
>
> class PretendLock:
> def __init__(self):
> self.d = dict()
> def acquire(self):
> myid = threading.currentThread().ident
> while self.d.setdefault("owner",myid) != myid:
> pass
> def release(self):
> del self.d["owner"]
>
>
> This depends on some peculiarities of the CPython
> implementation that aren't guaranteed by the language spec -
> namely that thread switches can't happen while executing C
> code, that dict.setdefault is implemented in C, and that is
> can calculate the hash of a string key without calling back
> out to python code.
>
>
> Thanks Ryan,
>
> Agreed, I was timing the wrong thing - but largely because I wasn't
> sure what to time against. setdefault certainly seems to be a
> candidate for something to time. Even so, setdefault wins.
>
> Though, I wouldn't want to use PretendLock in this case... it doesn't
> seem that having the spin loop would justify reducing reducing the
> lock allocation overhead in a no-contention scenario.
Oh totally - nobody reading this should even consider using that
PretendLock class for anything. It's just an example of how to use
setdefault as a test-and-set kind of operator.
Ryan
--
Ryan Kelly
http://www.rfk.id.au | This message is digitally signed. Please visit
r...@rfk.id.au| http://www.rfk.id.au/ramblings/gpg/ for details
signature.asc
Description: This is a digitally signed message part
--
http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
>
> Sure, but I think you're timing the wrong thing here. You would only
> allocate the lock relatively rarely - it's the overhead of *acquiring*
> the lock that's the real problem.
>
> r...@durian:~$ python -m timeit -s "from threading import Lock; l =
> Lock()" "l.acquire(); l.release()"
> 100 loops, best of 3: 0.378 usec per loop
>
> Compare to one of my favourite dict methods, setdefault:
>
> r...@durian:~$ python -m timeit -s "d = dict()"
> "d.setdefault('hello','world')"
> 1000 loops, best of 3: 0.189 usec per loop
>
>
> In the same ballpark really.
>
>
>
> I've managed to avoid locking in some cases by using dict.setdefault()
> as a kind of atomic test-and-set operation. It's not a full
> compare-and-swap but you could implement a simple locking scheme using
> it like this:
>
>
> class PretendLock:
> def __init__(self):
> self.d = dict()
> def acquire(self):
> myid = threading.currentThread().ident
> while self.d.setdefault("owner",myid) != myid:
> pass
> def release(self):
> del self.d["owner"]
>
>
> This depends on some peculiarities of the CPython implementation that
> aren't guaranteed by the language spec - namely that thread switches
> can't happen while executing C code, that dict.setdefault is implemented
> in C, and that is can calculate the hash of a string key without calling
> back out to python code.
>
> Usually, it's not worth it. The one time I use this regularly is for
> lazy object initialisation, e.g. something like this:
>
> def get_my_object(key):
> try:
> return objects[key]
> except KeyError:
> return objects.setdefault(key,create_my_object(key))
>
> If two threads happen to try initialising the object at the same time,
> only one will wind up in the dict and being used; the other will be
> discarded and garbage-collected.
>
Thanks Ryan,
Agreed, I was timing the wrong thing - but largely because I wasn't sure
what to time against. setdefault certainly seems to be a candidate for
something to time. Even so, setdefault wins.
Though, I wouldn't want to use PretendLock in this case... it doesn't seem
that having the spin loop would justify reducing reducing the lock
allocation overhead in a no-contention scenario.
Yes, get_my_object is a good trick. I did just that to avoid instantiating
extra locks in one scenario.
--
Zachary Burns
(407)590-4814
Aim - Zac256FL
Production Engineer
Zindagi Games
--
http://mail.python.org/mailman/listinfo/python-list
Re: Lockless algorithms in python (Nothing to do with GIL)
On Mon, 2010-06-28 at 16:46 -0700, Zac Burns wrote:
> In my experience it is far more expensive to allocate a lock in python
> then it is the types that use them. Here are some examples:
>
> >>> timeit.timeit('Lock()', 'from threading import Lock')
> 1.4449114807669048
>
> >>> timeit.timeit('dict()')
> 0.2821554294221187
>
> >>> timeit.timeit('list()')
> 0.17358153222312467
>
>
> Granted, I know these types do not allocate a lock - but a similarly
> defined user type would need to allocate a lock to guarantee
> thread-safety.
Sure, but I think you're timing the wrong thing here. You would only
allocate the lock relatively rarely - it's the overhead of *acquiring*
the lock that's the real problem.
r...@durian:~$ python -m timeit -s "from threading import Lock; l = Lock()"
"l.acquire(); l.release()"
100 loops, best of 3: 0.378 usec per loop
Compare to one of my favourite dict methods, setdefault:
r...@durian:~$ python -m timeit -s "d = dict()"
"d.setdefault('hello','world')"
1000 loops, best of 3: 0.189 usec per loop
In the same ballpark really.
> I have not done a great deal of research into lockless algorithms
> thusfar, but would it be worthwhile to investigate implementing some
> of them in python to optimize performance critical sections of code?
>
> Many lockless algorithms that I have looked at thusfar require a
> "Compare and Swap" operation. Does python have an equivalent to this?
> Is python high level enough that it has something better than this or
> it simply doesn't need it?
I've managed to avoid locking in some cases by using dict.setdefault()
as a kind of atomic test-and-set operation. It's not a full
compare-and-swap but you could implement a simple locking scheme using
it like this:
class PretendLock:
def __init__(self):
self.d = dict()
def acquire(self):
myid = threading.currentThread().ident
while self.d.setdefault("owner",myid) != myid:
pass
def release(self):
del self.d["owner"]
This depends on some peculiarities of the CPython implementation that
aren't guaranteed by the language spec - namely that thread switches
can't happen while executing C code, that dict.setdefault is implemented
in C, and that is can calculate the hash of a string key without calling
back out to python code.
Usually, it's not worth it. The one time I use this regularly is for
lazy object initialisation, e.g. something like this:
def get_my_object(key):
try:
return objects[key]
except KeyError:
return objects.setdefault(key,create_my_object(key))
If two threads happen to try initialising the object at the same time,
only one will wind up in the dict and being used; the other will be
discarded and garbage-collected.
Cheers,
Ryan
--
Ryan Kelly
http://www.rfk.id.au | This message is digitally signed. Please visit
r...@rfk.id.au| http://www.rfk.id.au/ramblings/gpg/ for details
signature.asc
Description: This is a digitally signed message part
--
http://mail.python.org/mailman/listinfo/python-list
Lockless algorithms in python (Nothing to do with GIL)
In my experience it is far more expensive to allocate a lock in python then
it is the types that use them. Here are some examples:
>>> timeit.timeit('Lock()', 'from threading import Lock')
1.4449114807669048
>>> timeit.timeit('dict()')
0.2821554294221187
>>> timeit.timeit('list()')
0.17358153222312467
Granted, I know these types do not allocate a lock - but a similarly defined
user type would need to allocate a lock to guarantee thread-safety.
I have not done a great deal of research into lockless algorithms thusfar,
but would it be worthwhile to investigate implementing some of them in
python to optimize performance critical sections of code?
Many lockless algorithms that I have looked at thusfar require a "Compare
and Swap" operation. Does python have an equivalent to this? Is python high
level enough that it has something better than this or it simply doesn't
need it?
--
Zachary Burns
(407)590-4814
Aim - Zac256FL
Production Engineer
Zindagi Games
--
http://mail.python.org/mailman/listinfo/python-list
Re: genetic algorithms in Python?
Terry Reedy wrote: Esmail wrote: Hello, Anyone using Python for coding up genetic algorithms? If so, would you share your favorite modules/libraries/tools? Search 'Python genetic algorithm' on Google or elsewhere. Hi Terry, I did that first, and I came up with a number of hits. The "problem" with Python is that there's so much available and it's sometimes hard to decide what to select, so I was looking for some folks who had use some of the tools and could share their experiences. Esmail ps: the "problem" is a good thing to have all things considered :-) -- http://mail.python.org/mailman/listinfo/python-list
Re: genetic algorithms in Python??
R. David Murray wrote: Esmail wrote: Hello Mohammed, Yes, that would great. While I am comfortable with GAs, I'm still rather inexperienced with Python so seeing some implementation examples would be very useful. A google for 'python genetic algorithms' turns up a number of interesting hits. Agreed .. I did that and came up with a number of hits, but the "problem" :-) with Python is a plethora of choices, so I wasn't quite sure which of the finds might be the most promising/useful. Nothing like a testimony from someone who uses or has used a tool. I also remember seeing at least one package announced on python-announce that referred to genetic algorithms, so you might check the archives of that mailing list as well. Yes, that's a good idea, thanks, Esmail -- http://mail.python.org/mailman/listinfo/python-list
Re: genetic algorithms in Python?
Esmail wrote: Hello, Anyone using Python for coding up genetic algorithms? If so, would you share your favorite modules/libraries/tools? Search 'Python genetic algorithm' on Google or elsewhere. -- http://mail.python.org/mailman/listinfo/python-list
Re: genetic algorithms in Python??
Esmail wrote: > Hello Mohammed, > > Yes, that would great. While I am comfortable with GAs, > I'm still rather inexperienced with Python so seeing some > implementation examples would be very useful. A google for 'python genetic algorithms' turns up a number of interesting hits. I also remember seeing at least one package announced on python-announce that referred to genetic algorithms, so you might check the archives of that mailing list as well. -- R. David Murray http://www.bitdance.com -- http://mail.python.org/mailman/listinfo/python-list
Re: genetic algorithms in Python??
Hello Mohammed, Yes, that would great. While I am comfortable with GAs, I'm still rather inexperienced with Python so seeing some implementation examples would be very useful. Thanks, Esmail -- Date: Wed, 8 Apr 2009 17:08:48 +0200 Subject: Re: genetic algorithms in Python? From: medmedi...@gmail.com To: ebo...@hotmail.com CC: python-list@python.org I have done something in this direction. I will be happy to share my experience. However, my code is not generic and needs many things to be manually introduced. My GA is standard (selection by roulette wheel or tournament, single point cross). Let me know if you are interested! On Wed, Apr 8, 2009 at 3:25 PM, Esmail wrote: Hello, Anyone using Python for coding up genetic algorithms? If so, would you share your favorite modules/libraries/tools? Thanks, Esmail -- http://mail.python.org/mailman/listinfo/python-list
Re: genetic algorithms in Python?
I have done something in this direction. I will be happy to share my experience. However, my code is not generic and needs many things to be manually introduced. My GA is standard (selection by roulette wheel or tournament, single point cross). Let me know if you are interested! On Wed, Apr 8, 2009 at 3:25 PM, Esmail wrote: > Hello, > > Anyone using Python for coding up genetic algorithms? If > so, would you share your favorite modules/libraries/tools? > > Thanks, > Esmail > > -- > http://mail.python.org/mailman/listinfo/python-list > -- http://mail.python.org/mailman/listinfo/python-list
genetic algorithms in Python?
Hello, Anyone using Python for coding up genetic algorithms? If so, would you share your favorite modules/libraries/tools? Thanks, Esmail -- http://mail.python.org/mailman/listinfo/python-list
Re: Optimal Control Algorithms in Python
Not exactly but I am aware of Python code for nonlinear optimization algorithms. Check the nlpy project at http://nlpy.sf.net It is specifically targeted at finite-dimensional problems. However the current trend in optimal control algorithms is to use grid-refinement and iteratively solve finite-dimensional problems. You may thus find nlpy useful. The missing part is the collocation/discretization part. That may be available some place else. Similarly, SciPy has some optimization algorithms ready for use but, as far as I know, nothing for control. Good luck, Dominique -- http://mail.python.org/mailman/listinfo/python-list
Optimal Control Algorithms in Python
Is anyone aware of Python code for Optimal Control Algorithms based on Pontryagin's Maximum Principle? Thanks in advance for any leads on this. -- http://mail.python.org/mailman/listinfo/python-list
