python bijection
in [Python]
|
Prev: Python/HTML integration: phileas v0.3 released
Next: scanning under windows WIA with custom settings (dpi / etc )
From: Gabriel Genellina on 27 Nov 2009 21:36 En Fri, 27 Nov 2009 15:12:36 -0300, Francis Carr <coldtortuga(a)gmail.com> escribi�: > I was really inspired by this discussion thread! :-) > > After much tinkering, I think I have a simpler solution. Just make > the inverse mapping accessible via an attribute, -AND- bind the > inverse of -THAT- mapping back to the original. The result is a > python dict with NO NEW METHODS except this inverse-mapping > attribute. I have posted it on code.activestate.com as <a > href="http://code.activestate.com/recipes/576968/">Recipe 576968: > Flipdict -- python dict that also maintains a one-to-one inverse > mapping</a> Nice idea! Just a couple of comments: Instead of: self._flip = dict.__new__(self.__class__) I'd write: self._flip = self.__class__() unless I'm missing something (but see the next point). Also, although Python's GC is able to handle them, I prefer to avoid circular references like those between x and x._flip. Making self._flip a weak reference (and dereferencing it in the property) should be enough. -- Gabriel Genellina
From: Joshua Bronson on 28 Nov 2009 04:30 On Nov 27, 9:36 pm, "Gabriel Genellina" <gagsl-py2(a)yahoo.com.ar> wrote: > En Fri, 27 Nov 2009 15:12:36 -0300, Francis Carr <coldtortuga(a)gmail.com> > escribió: > > > I was really inspired by this discussion thread! :-) > > > After much tinkering, I think I have a simpler solution. Just make > > the inverse mapping accessible via an attribute, -AND- bind the > > inverse of -THAT- mapping back to the original. The result is a > > python dict with NO NEW METHODS except this inverse-mapping > > attribute. I have posted it on code.activestate.com as <a > > href="http://code.activestate.com/recipes/576968/">Recipe 576968: > > Flipdict -- python dict that also maintains a one-to-one inverse > > mapping</a> > > Nice idea! Indeed! Thanks for sharing! I liked this so much I added something similar in http://bitbucket.org/jab/toys/src/tip/bidict.py (I made the inverse available via a .inv property, as well as via the unary ~ operator (by analogy to bitwise inverse)). I also got rid of getinv, popinv, et al. to keep the API leaner as you recommend. I've kept the slice syntax though as well as namedbidect, so for now I guess I'm allowing for many ways to skin this cat. > Just a couple of comments: > > Instead of: > self._flip = dict.__new__(self.__class__) > I'd write: > self._flip = self.__class__() > unless I'm missing something (but see the next point). How would this not cause infinite recursion? > Also, although Python's GC is able to handle them, I prefer to avoid > circular references like those between x and x._flip. Making self._flip a > weak reference (and dereferencing it in the property) should be enough. If both self._flip and self._flip._flip are weak references, no strong references to the inverse mapping survive leaving the constructor scope. Unless I'm missing something, only one of these can be a weak reference, and then you'd have to do something like this in the property to prevent "TypeError: FlipDict is not callable": @property def flip(self): try: # we're an inverse, self._flip is a weak reference return self._flip() except TypeError: # we're a forward mapping, self._flip is a strong reference return self._flip
From: Patrick Maupin on 28 Nov 2009 10:31 On Nov 19, 8:36 pm, Ben Finney <ben+pyt...(a)benfinney.id.au> wrote: > Carl Banks <pavlovevide...(a)gmail.com> writes: > > On Nov 19, 3:24 pm, Joshua Bronson <jabron...(a)gmail.com> wrote: > > Apart from the GPL, it seems perfectly fine to release, and looks like > > an interesting strategy. I've wanted one of those once in a while, > > never enough to bother looking for one or writing one myself. > > I would think GPL is an excellent choice for such a library then, if the > author's intention is to encourage more software to be free software so > that it can incorporate a unique library like this. Well, yes and no. This bidict class sounds nice and full-featured, especially after the changes prompted by the fruitful discussion. I personally use inverse mappings on a regular basis, but for the most part, my data doesn't change all that dynamically (or performance doesn't really matter), so when I need to go backwards I often do something like: inverse_mapping = dict((y, x) for (x, y) in forward_mapping.iteritems ()) Having said that, if I ever actually *need* something more full- featured to add to non-GPLed software, I'd just write it (and release it under a permissive license). IMHO, GPLing something this simple is really the tail trying to wag the dog. Case in point: I was just using rst2pdf to combine some restructured text and SVG images, using svglib. svglib had some bugs and didn't work right on my PDFs. svglib is not developed publicly, and the author is somewhat slow to accept patches. Since svglib is reasonably small, if it had been released under a permissive license, or even the LGPL, I probably would have just copied it into the rst2pdf repository and fixed it. If it were any smaller, I would have rewritten it. I don't own the rst2pdf package, and didn't really want a license discussion about 1K of source lines dictating a license change on 15K lines. As it is, I figure the svglib author will probably get around to fixing the bug at some point anyway, and for now I can easily use PDFs for my graphics input format, so I cleaned up and added to some old PDF code I had lying around, and released it as the open source pdfrw package, and now rst2pdf can use that to import PDFs as vector images without rasterizing them -- a new capability. So in this case, the GPL spurred open-source development, in exactly the same way that proprietary licenses do... I'm quite happy to *use* GPLed software (and greatly appreciate the authors' efforts), and I'm even sometimes willing to debug or add features and submit patches to GPLed software, and I might even have a (business, not political) reason to release some software under the GPL myself someday. But if I ever did release something under the GPL for business reasons, it would be because I also had the right to also offer a proprietary version. This would require that I owned _all_ the code in the package, so the implication is: I'm not going to use your tiny little GPLed code in any major software I write for release, whether my software is GPLed or not. The LGPL is different. I view the LGPL as a statement of "if you ever add related functionality to this or fix a bug in this in a shipping product, I'd like to see the fix, please" and I could even see myself releasing something with this license under the right circumstances. Now if I were doing a web service, it would be a different story. I would be quite happy to add your GPLed software into the mix, so if that's a terrible thing, perhaps you should consider affero for your future offerings :-) Best regards, Pat
From: Joshua Bronson on 1 Dec 2009 13:31 On Nov 27, 1:12 pm, Francis Carr <coldtortuga(a)gmail.com> wrote: > I was really inspired by this discussion thread! :-) > > After much tinkering, I think I have a simpler solution. Just make > the inverse mapping accessible via an attribute, -AND- bind the > inverse of -THAT- mapping back to the original. The result is a > python dict with NO NEW METHODS except this inverse-mapping > attribute. I have posted it on code.activestate.com as <a > href="http://code.activestate.com/recipes/576968/">Recipe 576968: > Flipdict -- python dict that also maintains a one-to-one inverse > mapping</a> > > -- F. Carr I noticed the phonebook example in your ActiveState recipe and thought you might consider changing it to something like husbands to wives, since the names-to-phone-numbers relation is many-to-many. The built- in htmlentifydefs module provides fodder for a real-world example: It maintains name2codepoint and codepoint2name as two separate dicts. Raymond, do you think there might be any future in including a built- in bidict data structure in Python? At least there's one built-in module that might benefit from it. P.S. I moved bidict to its own repo at http://bitbucket.org/jab/bidict/ and released it to PyPI as http://pypi.python.org/pypi/bidict.
From: Raymond Hettinger on 1 Dec 2009 14:11
[Joshua Bronson] > Raymond, do you think there might be any future in including a built- > in bidict data structure in Python? I don't think so. There are several forces working against it: * the recipe is new, so it hasn't had a chance to mature or to gain a fan club. * there are many approaches to the solving the problem and there is no reason to assume this one is the best. * it extends the language with arcane syntax tricks instead of using the language as designed by Guido. That makes it harder to learn and remember. * we've already got one (actually two). The two dictionary approach uses plain python, requires no new learning, and is more flexible. Also, sqlite3 provides another way to use multiple lookups to a single record. The database approach is much more general (extending to trijections, allowing multiple sort orders, providing persistence, etc). * the semantics of a bijection aren't obvious: b['x'] = 'ex' # first record: ('x', 'ex') b['y'] = 'why' # second record: ('y', 'why') b[:'why'] = 'x' # do two records collapse into one? is there an error? * the proposed syntax doesn't address the issue covered in my previous post. Since bijections are symmetrical, they do not have an obvious direction (which is the primary key, the husband or the wife?). The syntax needs to allow user names to make it clear which is being accessed: marriages.h2w['john'] = 'amy' marriages.w2h['amy'] = 'john' Contrast this with: marriages['jordan'] = 'taylor' # are you sure you got the order correct? marriages[:'taylor'] = 'jordan' # this is easy to get backwards Raymond |