Re: [Zope-dev] difference between OOSet and OOTreeSet?
Gary Poster wrote: Okay, so I want a persistent, ordered sequence which is quick to find items in and which doesn't re-store the whole sequence when an item is inserted or removed. What should I be using? Ordered, as in sorted? Or ordered, as in user-determined order? Ordered as in sorted, thankfully :-) If sorted, use BTreeSet (or the keys of a BTree). As in OOTreeSet, right? Even though my assertion is right semantically for Set, this is a BTreeSet, and I don't see this behavior changing ever. *phew* No, it isn't a sequence, so `reversed` won't work, but `list` will always give you the same order. Well, you can iterate over it... Am I right in thinking I can get the reversed semantics I want by negating the numeric part of insert? s = OOTreeSet() s.insert(-myvalue) s.insert(-someothervalue) ...I just have to remember to re-negate them when I get 'em out? Set does not match the doesn't re-store the whole sequence when an item is inserted or removed requirement. But OOTreeSet does, right? In both cases, IMO you'll want your data to be of homogenous types. Yep, DateTimes all the way, or if you can't negate them, DateTime.timeTime's cheers, Chris -- Simplistix - Content Management, Zope Python Consulting - http://www.simplistix.co.uk ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
On Mar 2, 2007, at 2:42 AM, Chris Withers wrote: Gary Poster wrote: Okay, so I want a persistent, ordered sequence which is quick to find items in and which doesn't re-store the whole sequence when an item is inserted or removed. What should I be using? Ordered, as in sorted? Or ordered, as in user-determined order? Ordered as in sorted, thankfully :-) :-) If sorted, use BTreeSet (or the keys of a BTree). As in OOTreeSet, right? Yes. Even though my assertion is right semantically for Set, this is a BTreeSet, and I don't see this behavior changing ever. *phew* No, it isn't a sequence, so `reversed` won't work, but `list` will always give you the same order. Well, you can iterate over it... Am I right in thinking I can get the reversed semantics I want by negating the numeric part of insert? s = OOTreeSet() s.insert(-myvalue) s.insert(-someothervalue) ...I just have to remember to re-negate them when I get 'em out? Yeah, that would work. Set does not match the doesn't re-store the whole sequence when an item is inserted or removed requirement. But OOTreeSet does, right? Yes. In both cases, IMO you'll want your data to be of homogenous types. Yep, DateTimes all the way, or if you can't negate them, DateTime.timeTime's Cool. I doubt you can negate the old Zope DateTimes, but who knows what tricks that class has up its sleeve. ;-) Gary ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
Chris Withers wrote: Hi All, Wondering if someone could tell me the difference between an OOSet and an OOTreeSet? They seem to have different interfaces and yet seem to be used in similar circumstances in PluginIndexes/common/UnIndex.py... I'm looking for a set-like data structure which will likely get pretty large over time and so I don't want the whole data structure written to disk each time I add a new item to the set. What should I be using? I'll bet one is backed by a hashtable and the other is backed by an r/b tree, meaning the Set is O(1) lookups, possibly a bit less space efficient and non-ordered, and the TreeSet is O(logN) lookups, possibly a bit more space efficient when the set is sparse, and sorted in key order. Martin -- View this message in context: http://www.nabble.com/difference-between-OOSet-and-OOTreeSet--tf3327097.html#a9251011 Sent from the Zope - Dev mailing list archive at Nabble.com. ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
On Mar 1, 2007, at 9:04 AM, Chris Withers wrote: Hi All, Wondering if someone could tell me the difference between an OOSet and an OOTreeSet? They seem to have different interfaces and yet seem to be used in similar circumstances in PluginIndexes/common/UnIndex.py... I'm looking for a set-like data structure which will likely get pretty large over time and so I don't want the whole data structure written to disk each time I add a new item to the set. What should I be using? TreeSet. FWIW, here's an excerpt from the ZODB trunk BTrees/Interface.py class IBTreeModule(Interface): These are available in all modules (IOBTree, OIBTree, OOBTree, IIBTree, IFBTree, LFBTree, LOBTree, OLBTree, and LLBTree). BTree = Attribute( The IBTree for this module. Also available as [prefix]BTree, as in IOBTree.) Bucket = Attribute( The leaf-node data buckets used by the BTree. (IBucket is not currently defined in this file, but is essentially IDictionaryIsh, with the exception of __nonzero__, as of this writing.) Also available as [prefix]Bucket, as in IOBucket.) TreeSet = Attribute( The ITreeSet for this module. Also available as [prefix]TreeSet, as in IOTreeSet.) Set = Attribute( The ISet for this module: the leaf-node data buckets used by the TreeSet. Also available as [prefix]BTree, as in IOSet.) Gary ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
Martin Aspeli wrote: I'll bet one is backed by a hashtable and the other is backed by an r/b tree, meaning the Set is O(1) lookups, possibly a bit less space efficient and non-ordered, Well, Set's are definitely ordered, same as normal python sets... Chris -- Simplistix - Content Management, Zope Python Consulting - http://www.simplistix.co.uk ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
Hi Gary, Gary Poster wrote: What should I be using? TreeSet. Interesting, okay, so how should I work around this bogosity? Is this a bug? from BTrees.OOBTree import OOTreeSet,OOSet for i in OOSet((1,2,3)): print i, 1 2 3 for i in OOTreeSet((1,2,3)): print i, 1 2 3 for i in reversed(OOSet((1,2,3))): print i, 3 2 1 for i in reversed(OOTreeSet((1,2,3))): print i, Traceback (most recent call last): File stdin, line 1, in ? TypeError: argument to reversed() must be a sequence cheers, Chris -- Simplistix - Content Management, Zope Python Consulting - http://www.simplistix.co.uk ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
--On 1. März 2007 09:52:53 + Chris Withers [EMAIL PROTECTED] wrote: Martin Aspeli wrote: I'll bet one is backed by a hashtable and the other is backed by an r/b tree, meaning the Set is O(1) lookups, possibly a bit less space efficient and non-ordered, Well, Set's are definitely ordered, same as normal python sets... That's likely an implementation invariant but not a feature by design. -aj pgpbjoerFnmWj.pgp Description: PGP signature ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
Chris Withers wrote: Martin Aspeli wrote: I'll bet one is backed by a hashtable and the other is backed by an r/b tree, meaning the Set is O(1) lookups, possibly a bit less space efficient and non-ordered, Well, Set's are definitely ordered, same as normal python sets... From http://docs.python.org/lib/types-set.html: A set object is an unordered collection of immutable values. Which makes sense. Sets in the mathematical sense are not ordered either, nor are sets in other languages (notably Java's Collections API), nor is zope.schem.Set. Tuples and Lists are ordered. Sets may turn out to be *sorted* if they're implemented with trees, but I don't think the implementation promises that either. Martin -- View this message in context: http://www.nabble.com/difference-between-OOSet-and-OOTreeSet--tf3327097.html#a9254167 Sent from the Zope - Dev mailing list archive at Nabble.com. ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
On Mar 1, 2007, at 12:01 PM, Chris Withers wrote: Hi Gary, Gary Poster wrote: What should I be using? TreeSet. Interesting, okay, so how should I work around this bogosity? Is this a bug? from BTrees.OOBTree import OOTreeSet,OOSet for i in OOSet((1,2,3)): print i, 1 2 3 for i in OOTreeSet((1,2,3)): print i, 1 2 3 for i in reversed(OOSet((1,2,3))): print i, 3 2 1 for i in reversed(OOTreeSet((1,2,3))): print i, Traceback (most recent call last): File stdin, line 1, in ? TypeError: argument to reversed() must be a sequence The fact that this works for the OOSet is an implementation accident. As discussed elsewhere in this thread, sets are not sequences. The fact that the elements are ordered is an implementation detail (although given that these sets are essentially the keys of a BTree, it's unsurprising that they are). You could argue that reversed(OOSet((1,2,3))) should raise an exception. IMO, why bother. Gary ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
On 3/1/07, Martin Aspeli [EMAIL PROTECTED] wrote: Sets may turn out to be *sorted* if they're implemented with trees, but I don't think the implementation promises that either. The BTrees implementation definitely does promise the sorting relationship for the results of iteration, which is useful. Python's built-in set types do not make that promise (and they happen to be hash-based). -Fred -- Fred L. Drake, Jr.fdrake at gmail.com Every sin is the result of a collaboration. --Lucius Annaeus Seneca ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
Gary Poster wrote: Traceback (most recent call last): File stdin, line 1, in ? TypeError: argument to reversed() must be a sequence The fact that this works for the OOSet is an implementation accident. As discussed elsewhere in this thread, sets are not sequences. The fact that the elements are ordered is an implementation detail (although given that these sets are essentially the keys of a BTree, it's unsurprising that they are). You could argue that reversed(OOSet((1,2,3))) should raise an exception. IMO, why bother. *grunt* Okay, so I want a persistent, ordered sequence which is quick to find items in and which doesn't re-store the whole sequence when an item is inserted or removed. What should I be using? cheers, Chris -- Simplistix - Content Management, Zope Python Consulting - http://www.simplistix.co.uk ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
On Mar 1, 2007, at 3:18 PM, Chris Withers wrote: Gary Poster wrote: Traceback (most recent call last): File stdin, line 1, in ? TypeError: argument to reversed() must be a sequence The fact that this works for the OOSet is an implementation accident. As discussed elsewhere in this thread, sets are not sequences. The fact that the elements are ordered is an implementation detail (although given that these sets are essentially the keys of a BTree, it's unsurprising that they are). You could argue that reversed(OOSet((1,2,3))) should raise an exception. IMO, why bother. *grunt* Okay, so I want a persistent, ordered sequence which is quick to find items in and which doesn't re-store the whole sequence when an item is inserted or removed. What should I be using? Ordered, as in sorted? Or ordered, as in user-determined order? If sorted, use BTreeSet (or the keys of a BTree). Even though my assertion is right semantically for Set, this is a BTreeSet, and I don't see this behavior changing ever. No, it isn't a sequence, so `reversed` won't work, but `list` will always give you the same order. Set does not match the doesn't re-store the whole sequence when an item is inserted or removed requirement. If user-determined (like a list) then you are currently out of luck. I actually have a implementation of this (which I think is cool) with some tests, but I regard it as experimental and am refactoring it in my spare (ha) time. (I would not mind you looking at what I have, but I don't particularly recommend it yet for production, so I expect it is useless to you.) In both cases, IMO you'll want your data to be of homogenous types. Gary ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
Re: [Zope-dev] difference between OOSet and OOTreeSet?
[Chris Withers] Wondering if someone could tell me the difference between an OOSet and an OOTreeSet? OOSet is to OOTreeSet as OOBucket is to OOBTree. An OOTreeSet is built out of leaf-level OOSets in exactly the same way an OOBTree is built out of leaf-level OOBuckets. More at: http://wiki.zope.org/ZODB/guide/node6.html#SECTION00063 They seem to have different interfaces ? and yet seem to be used in similar circumstances in PluginIndexes/common/UnIndex.py... I'm looking for a set-like data structure which will likely get pretty large over time and so I don't want the whole data structure written to disk each time I add a new item to the set. What should I be using? OOTreeSet. ___ Zope-Dev maillist - Zope-Dev@zope.org http://mail.zope.org/mailman/listinfo/zope-dev ** No cross posts or HTML encoding! ** (Related lists - http://mail.zope.org/mailman/listinfo/zope-announce http://mail.zope.org/mailman/listinfo/zope )
