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? cheers, Chris -- Simplistix - Content Management, Zope & Python Consulting - http://www.simplistix.co.uk
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... Sent from the Zope - Dev mailing list archive at Nabble.com.
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
--On 1. März 2007 09:52:53 +0000 Chris Withers <chris@simplistix.co.uk> 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
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...
"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... Sent from the Zope - Dev mailing list archive at Nabble.com.
On 3/1/07, Martin Aspeli <optilude@gmx.net> 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
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
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
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
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
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
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
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
[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#SECTION000630000000000000000
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.
participants (6)
-
Andreas Jung -
Chris Withers -
Fred Drake -
Gary Poster -
Martin Aspeli -
Tim Peters