Thread: [Jython-checkins] SF.net SVN: jython: [3447] branches/newcompiler/PyASM

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Revision: 3447
          http://jython.svn.sourceforge.net/jython/?rev=3447&view=rev
Author:   zyasoft
Date:     2007-08-22 21:57:07 -0700 (Wed, 22 Aug 2007)

Log Message:
-----------
Added relational algebra test, based on Jim's cookbook recipe, to test generator expressions

Modified Paths:
--------------
    branches/newcompiler/PyASM/test/with.py

Added Paths:
-----------
    branches/newcompiler/PyASM/new_itertools.py
    branches/newcompiler/PyASM/new_operator.py
    branches/newcompiler/PyASM/test/relalg.py

Added: branches/newcompiler/PyASM/new_itertools.py
===================================================================

--- branches/newcompiler/PyASM/new_itertools.py	                        (rev 0)
+++ branches/newcompiler/PyASM/new_itertools.py	2007-08-23 04:57:07 UTC (rev 3447)
@@ -0,0 +1,57 @@
+import itertools as base_it
+
+count = base_it.count
+cycle = base_it.cycle
+dropwhile = base_it.dropwhile
+ifilter = base_it.ifilter
+ifilterfalse = base_it.ifilterfalse
+imap = base_it.imap
+islice = base_it.islice
+izip = base_it.izip
+repeat = base_it.repeat
+starmap = base_it.starmap
+takewhile = base_it.takewhile
+
+def chain(*iterables):
+    for it in iterables:
+        for element in it:
+            yield element
+
+class groupby(object):
+    def __init__(self, iterable, key=None):
+        if key is None:
+            key = lambda x: x
+        self.keyfunc = key
+        self.it = iter(iterable)
+        self.tgtkey = self.currkey = self.currvalue = xrange(0)
+    def __iter__(self):
+        return self
+    def next(self):
+        while self.currkey == self.tgtkey:
+            self.currvalue = self.it.next() # Exit on StopIteration
+            self.currkey = self.keyfunc(self.currvalue)
+        self.tgtkey = self.currkey
+        return (self.currkey, self._grouper(self.tgtkey))
+    def _grouper(self, tgtkey):
+        while self.currkey == tgtkey:
+            yield self.currvalue
+            self.currvalue = self.it.next() # Exit on StopIteration
+            self.currkey = self.keyfunc(self.currvalue)
+
+def izip(*iterables):
+    iterables = map(iter, iterables)
+    while iterables:
+        result = [it.next() for it in iterables]
+        yield tuple(result)
+
+def tee(iterable):
+    def gen(next, data={}, cnt=[0]):
+        for i in count():
+            if i == cnt[0]:
+                item = data[i] = next()
+                cnt[0] += 1
+            else:
+                item = data.pop(i)
+            yield item
+    it = iter(iterable)
+    return (gen(it.next), gen(it.next))

Added: branches/newcompiler/PyASM/new_operator.py
===================================================================
--- branches/newcompiler/PyASM/new_operator.py	                        (rev 0)
+++ branches/newcompiler/PyASM/new_operator.py	2007-08-23 04:57:07 UTC (rev 3447)
@@ -0,0 +1,9 @@
+import operator as base_op
+
+concat = base_op.concat
+eq = base_op.eq
+
+def itemgetter(*args):
+    def f(item):
+        return item[args[0]]
+

Added: branches/newcompiler/PyASM/test/relalg.py
===================================================================
--- branches/newcompiler/PyASM/test/relalg.py	                        (rev 0)
+++ branches/newcompiler/PyASM/test/relalg.py	2007-08-23 04:57:07 UTC (rev 3447)
@@ -0,0 +1,241 @@
+"""
+Iterator algebra implementations of join algorithms: hash join, merge
+join, and nested loops join, as well as a variant I dub "bisect join".
+
+Requires Python 2.4.
+
+Author: Jim Baker, jb...@zy...
+
+Define some relations to join:
+>>> accounts = [
+...    ('spender', 'Big', 'Spender', '123-456-7890'),
+...    ('saver', 'Thrifty', 'Saver', '234-567-8901'),
+...    ('nobody', 'A', 'Nobody', '999-999-9999')]
+>>> transactions = [
+...    ('spender', 'deposited', 100),
+...    ('spender', 'withdraw', 40),
+...    ('spender', 'withdraw', 15),
+...    ('spender', 'withdraw', 25),
+...    ('saver',  'deposited', 30)]
+
+Given the above data, a useful join predicate is the first element of
+each tuple. This will give us a usable equijoin:
+>>> def first(x): return x[0]
+
+Test that the implemented join methods are equivalent:
+>>> nj = set(nested_loops_join(accounts, transactions, first))
+>>> hj = set(hash_join(accounts, transactions, first))
+>>> bj = set(bisect_join(accounts, transactions, first))
+>>> nj == hj
+True
+>>> bj == hj
+True
+
+Perform a Cartesian join. In this case, we need a predicate that
+returns the same value for every tuple, so in this case returning True
+is arbitrary:
+>>> def always(x): return True
+
+With 5 tuples in transactions and 3 tuples in accounts, we should get
+15 tuples:
+>>> len(list(hash_join(accounts, transactions, always)))
+15
+
+With semijoins and outer joins, we now see the power of the
+iterator approach. A left join will return a tuple even if there is
+not a match on the predicate:
+>>> lj = set(hash_join(accounts, transactions, first, 
+...                    join=lambda X: left(X, when_empty=tuple([None]*3))))
+>>> len(lj)
+6
+
+A full outer join is simply the union of a left join and a right
+join. Let's make a right join by reversing the order of the join. We
+will also to need to reverse how we combine the tuples:
+>>> rj = set(nested_loops_join(transactions, accounts, first,
+...                            combine=lambda r, s: s + r,
+...                            join=lambda X: left(X, when_empty=tuple([None]*2))))
+>>> len(rj)
+5
+
+Note that we have no activity in this example without an accompanying
+account, so it's the same as an inner join. Now let's compute the full
+outer join:
+>>> foj = lj | rj
+>>> len(foj)
+6
+
+A semijoin will return only the first matching tuple:
+>>> len(list(hash_join(accounts, transactions, first, semi)))
+2
+
+
+Semijoins are useful, especially in conjunction with hierarchical
+queries. In SQL, if supported, they are the efficient alternative to
+writing 'select distinct', although they make one's code difficult to
+understand by the unversed.  Hopefully showing this with procedural
+code can make this useful feature less mysterious.
+
+"""
+
+import new_operator as operator
+import sets.Set as set
+
+def sorted(X):
+    temp = list(X)
+    temp.sort()
+    return temp
+
+def identity(x):
+    """x -> x
+
+    As a predicate, this function is useless, but it provides a
+    useful/correct default.
+
+    >>> identity(('apple', 'banana', 'cherry'))
+    ('apple', 'banana', 'cherry')
+    """
+    return x
+
+def inner(X):
+    """
+    >>> X = [1, 2, 3, 4, 5]
+    >>> list(inner(X))
+    [1, 2, 3, 4, 5]
+    """
+    for x in X:
+        yield x
+
+def semi(X):
+    """Returns X[0] if X is not empty
+
+    >>> X = [1, 2, 3, 4, 5]
+    >>> list(semi(X))
+    [1]
+    """
+    
+    for x in X:
+        yield x
+        break
+
+def left(X, when_empty=()):
+    empty = True
+    for x in X:
+        yield x
+        empty = False
+    if empty:
+        yield when_empty
+        
+
+# Xp can mean X-prime or X-with-predicate; we use both meanings
+# interchangeably here in the shorthand of this code.
+# Xp -> (p(x0), x0), (p(x1), x1), ... 
+
+# throughout, we assume S is the smaller relation of R and S.
+
+def hash_join(R, S, predicate=identity, join=inner, combine=operator.concat):
+    hashed = {}
+    for s in S:
+        hashed.setdefault(predicate(s),[]).append(s)
+    for r in R:
+        for s in join(hashed.get(predicate(r),())):
+            yield combine(r, s)
+
+def nested_loops_join(R, S, predicate=identity, join=inner,
+                      combine=operator.concat, theta=operator.eq):
+    Sp = [(predicate(s), s) for s in S]
+    for r in R:
+        rp = predicate(r) 
+        for s in join(s for sp, s in Sp if theta(rp, sp)):
+            yield combine(r, s)
+
+def bisect_join(R, S, predicate=identity, join=inner, combine=operator.concat):
+    """
+    I have not found discussion of this variant on the sort-merge join anywhere.
+    """
+
+    from bisect import bisect_left
+
+    def consume(Sp, si, rp):
+        """This needs a better name..."""
+        length = len(S)
+        while si < length:
+            sp, s = Sp[si]
+            if rp == sp:
+                yield s
+            else:
+                break
+            si += 1
+
+    Rp = sorted((predicate(r), r) for r in R)
+    Sp = sorted((predicate(s), s) for s in S)
+
+    for rp, r in Rp:
+        si = bisect_left(Sp, (rp,))
+        for s in join(consume(Sp, si, rp)):
+            yield combine(r, s)
+
+
+def merge_join(R, S, predicate=identity, join=inner, combine=operator.concat):
+    """
+    For obvious reasons, we depend on the predicate providing a
+    sortable relation.
+
+    Compare this presentation using iterator algebra with the much
+    more difficult to follow presentation (IMHO) in
+    http://en.wikipedia.org/wiki/Sort-Merge_Join
+    """
+
+    from new_itertools import groupby
+
+    def advancer(Xp):
+        """A simple wrapper of itertools.groupby, we simply need
+        to follow our convention that Xp -> (xp0, x0), (xp1, x1), ...
+        """
+
+        for k, g in groupby(Xp, key=operator.itemgetter(0)):
+            yield k, list(g)
+    
+    R_grouped = advancer(sorted((predicate(r), r) for r in R))
+    S_grouped = advancer(sorted((predicate(s), s) for s in S))
+
+    # in the join we need to distinguish rp from rk in the unpack, so
+    # just use rk, sk
+    rk, R_matched = R_grouped.next()
+    sk, S_matched = S_grouped.next()
+
+    while R_grouped and S_grouped:
+        comparison = cmp(rk, sk)
+        if comparison == 0:
+            # standard Cartesian join here on the matched tuples, as
+            # subsetted by the join method
+            for rp, r in R_matched:
+                for sp, s in join(S_matched):
+                    yield combine(r, s)
+            rk, R_matched = R_grouped.next()
+            sk, S_matched = S_grouped.next()
+        elif comparison > 0:
+            sk, S_matched = S_grouped.next()
+        else:
+            rk, R_matched = R_grouped.next()
+
+
+if __name__ == "__main__":
+    accounts = [
+        ('spender', 'Big', 'Spender', '123-456-7890'),
+        ('saver', 'Thrifty', 'Saver', '234-567-8901'),
+        ('nobody', 'A', 'Nobody', '999-999-9999')]
+    transactions = [
+        ('spender', 'deposited', 100),
+        ('spender', 'withdraw', 40),
+        ('spender', 'withdraw', 15),
+        ('spender', 'withdraw', 25),
+        ('saver',  'deposited', 30)]
+    
+    def first(x): return x[0]
+
+    print 'NJ', set(nested_loops_join(accounts, transactions, first))
+    print 'HJ', set(hash_join(accounts, transactions, first))
+    print 'BJ', set(bisect_join(accounts, transactions, first))
+    print 'MJ', set(merge_join(accounts, transactions, first))
+

Modified: branches/newcompiler/PyASM/test/with.py
===================================================================
--- branches/newcompiler/PyASM/test/with.py	2007-08-22 22:10:51 UTC (rev 3446)
+++ branches/newcompiler/PyASM/test/with.py	2007-08-23 04:57:07 UTC (rev 3447)
@@ -1,6 +1,6 @@
 from __future__ import with_statement
 
-print "with_statement:", with_statement
+#print "with_statement:", with_statement
 
 class ContextGuard(object):
     def __init__(self, name, ret):


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




Thread: [Jython-checkins] SF.net SVN: jython: [3447] branches/newcompiler/PyASM

jython-checkins