damned-lies r1469 - in trunk: . common vertimus

[stephaner svn gnome org]

Author: stephaner
Date: Thu Mar  5 13:21:52 2009
New Revision: 1469
URL: http://svn.gnome.org/viewvc/damned-lies?rev=1469&view=rev

Log:
2009-03-05  StÃphane Raimbault  <stephane raimbault gmail com>

	* common/utils.py: New version of merge_sorted_by_field using only
	iterators.	
	* vertimus/feeds.py: Use the new function with islice.


Modified:
   trunk/ChangeLog
   trunk/common/utils.py
   trunk/vertimus/feeds.py

Modified: trunk/common/utils.py
==============================================================================
--- trunk/common/utils.py	(original)
+++ trunk/common/utils.py	Thu Mar  5 13:21:52 2009
@@ -34,8 +34,6 @@
     Each call returns the next item, sorted by field in ascending order or in
     descending order if the field name begins by a minus sign.
 
-    The lists of objects must be already sorted in the same order as field.
-
     >>> from datetime import datetime
     >>> import itertools
     >>> class Foo(object):
@@ -44,16 +42,16 @@
     ...     def __repr__(self):
     ...         return str(self.num)
     ...
-    >>> l1 = (Foo(1), Foo(4), Foo(5))
+    >>> l1 = (Foo(1), Foo(8), Foo(5))
     >>> l2 = (Foo(1), Foo(2), Foo(4), Foo(4), Foo(6))
     >>> merge_sorted_by_field(l1, l2, 'num')
-    [1, 1, 2, 4, 4, 4, 5, 6]
+    [1, 1, 2, 4, 4, 5, 6, 8]
     >>> merge_sorted_by_field(l1, l2, 'num')[:3]
     [1, 1, 2]
-    >>> l1 = (Foo(5), Foo(4), Foo(1))
+    >>> l1 = (Foo(3), Foo(9), Foo(5))
     >>> l2 = (Foo(6), Foo(4), Foo(4), Foo(2), Foo(1))
     >>> [el.num for el in merge_sorted_by_field(l1, l2, '-num')]
-    [6, 5, 4, 4, 4, 2, 1, 1]
+    [9, 6, 5, 4, 4, 3, 2, 1]
     """
     import itertools
     if field is not None and field[0] == '-':
@@ -67,6 +65,88 @@
                   key=lambda x: getattr(x, field),
                   reverse=reverse)
 
+def imerge_sorted_by_field(object_list1, object_list2, field):
+    """
+    Each call returns the next item, sorted by field in ascending order or in
+    descending order if the field name begins by a minus sign.
+
+    This function is faster (only one comparison by iteration) and uses less
+    memory than merge_sorted_by_field (iterator) but the lists of objects must
+    be already sorted in the same order as field.
+
+    >>> from datetime import datetime
+    >>> import itertools
+    >>> class Foo(object):
+    ...     def __init__(self, num):
+    ...         self.num = num
+    ...     def __repr__(self):
+    ...         return str(self.num)
+    ...
+    >>> l1 = (Foo(1), Foo(3), Foo(5))
+    >>> l2 = (Foo(1), Foo(2), Foo(4), Foo(6), Foo(8))
+    >>> [el.num for el in imerge_sorted_by_field(l1, l2, 'num')]
+    [1, 1, 2, 3, 4, 5, 6, 8]
+    >>> [el.num for el in itertools.islice(imerge_sorted_by_field(l1, l2, 'num'), 3)]
+    [1, 1, 2]
+    >>> l1 = []
+    >>> [el.num for el in imerge_sorted_by_field(l1, l2, 'num')]
+    [1, 2, 4, 6, 8]
+    >>> l1 = (Foo(5), Foo(4), Foo(1))
+    >>> l2 = (Foo(6), Foo(4), Foo(4), Foo(2), Foo(1))
+    >>> [el.num for el in imerge_sorted_by_field(l1, l2, '-num')]
+    [6, 5, 4, 4, 4, 2, 1, 1]
+    """
+    import operator
+        
+    if field is not None and field[0] == '-':
+        # Reverse the sort order
+        field = field[1:]
+        op = operator.gt
+    else:
+        op = operator.lt
+
+    iter1, iter2 = iter(object_list1), iter(object_list2)
+    
+    # Too many try/except couples to my taste but I don't know how to filter the
+    # StopIteration to find the source.
+
+    try:
+        el1 = iter1.next()
+    except StopIteration:
+        # Finish the other list
+        while True:
+            el2 = iter2.next()
+            yield el2
+
+    try:
+        el2 = iter2.next()
+    except StopIteration:
+        # Finish the other list
+        while True:
+            # el1 is already fetched
+            yield el1
+            el1 = iter1.next()
+
+    while True:
+        if op(getattr(el1, field), getattr(el2, field)):
+            yield el1
+            try:
+                el1 = iter1.next()
+            except StopIteration:
+                # Finish the other list
+                while True:
+                    yield el2
+                    el2 = iter2.next()
+        else:
+            yield el2
+            try:
+                el2 = iter2.next()
+            except StopIteration:
+                # Finish the other list
+                while True:
+                    yield el1
+                    el1 = iter1.next()
+
 if __name__ == "__main__":
     import doctest
     doctest.testmod()

Modified: trunk/vertimus/feeds.py
==============================================================================
--- trunk/vertimus/feeds.py	(original)
+++ trunk/vertimus/feeds.py	Thu Mar  5 13:21:52 2009
@@ -18,6 +18,7 @@
 # along with Damned Lies; if not, write to the Free Software Foundation, Inc.,
 # 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
+from itertools import islice
 from django.core import urlresolvers
 from django.core.exceptions import ObjectDoesNotExist
 from django.contrib.syndication.feeds import Feed, FeedDoesNotExist
@@ -26,7 +27,7 @@
 from languages.models import Language
 from teams.models import Team
 from vertimus.models import ActionDb, ActionDbBackup
-from common.utils import merge_sorted_by_field
+from common.utils import imerge_sorted_by_field
 
 class LatestActionsByLanguage(Feed):
     title_template = 'feeds/actions_title.html'
@@ -56,7 +57,8 @@
         actions_db = ActionDb.objects.filter(state_db__language=obj.id).select_related('state').order_by('-created')[:20]
         archived_actions_db = ActionDbBackup.objects.filter(state_db__language=obj.id).select_related('state').order_by('-created')[:20]
 
-        return (action_db.get_action() for action_db in merge_sorted_by_field(actions_db, archived_actions_db, '-created')[:20])
+        # islice avoid to fetch too many objects
+        return (action_db.get_action() for action_db in islice(imerge_sorted_by_field(actions_db, archived_actions_db, '-created'), 20))
 
     def item_link(self, item):
         return urlresolvers.reverse('vertimus-names-view', 
@@ -100,7 +102,12 @@
         actions_db = ActionDb.objects.filter(state_db__language__team=obj.id).select_related('state').order_by('-created')[:20]
         archived_actions_db = ActionDbBackup.objects.filter(state_db__language__team=obj.id).select_related('state').order_by('-created')[:20]
 
-        return (action_db.get_action() for action_db in merge_sorted_by_field(actions_db, archived_actions_db, '-created')[:20])
+        import pdb; pdb.set_trace()
+
+        a = imerge_sorted_by_field(actions_db, archived_actions_db, '-created')
+        b = islice(imerge_sorted_by_field(actions_db, archived_actions_db, '-created'), 20)
+        # islice avoid to fetch too many objects
+        return (action_db.get_action() for action_db in islice(imerge_sorted_by_field(actions_db, archived_actions_db, '-created'), 20))
 
     def item_link(self, item):
         return urlresolvers.reverse('vertimus-names-view',