[Tutor] how to keep track of sorted lists

[Dave Angel]

On 11/03/2012 09:04 AM, Albert-Jan Roskam wrote:
> Hello,

(I haven't run the code, as it was not presented in a form that I could
do a single copy/paste.  So I may have missed some subtlety in the code.)

> I want to make a get() method that uses a binary search. This requires the data to be sorted which is an expensive operation, so I would like to do this no more often than needed.
> Which of the to classes below is the best way to keep track of the sorted lists? TestOne stores them in separate attributes, while TestTwo uses one sorted_ attribute that is a dictionary that contains all the sorted data, with keys as, well, keys. I am inclined to think that TestTwo is less messy. Btw, I am aware that, either way, it may not be a good idea to store all these potentially huge sorted lists.
>
> Python 2.7.0+ (r27:82500, Sep 15 2010, 18:04:55) 
> [GCC 4.4.5] on linux2

Thanks for telling us the version and OS.

>>>> import bisect
>>>> class TestOne(object):
>     def __init__(self, param="x"):
>         self.param = param
>         self.data = range(10, 1, -1)
>     def get(self, key):
>         sorted_ = "sorted_" + self.param
>         if not hasattr(self, sorted_):
>             setattr(self, sorted_, sorted(self.data))
>         return bisect.bisect_right(getattr(self, sorted_), x=key)

Why have multiple copies of the sorted data, when there's only one list?

>>>> t = TestOne("x")
>>>> t.get(1)
> 0
>>>> class TestTwo(object):
>     def __init__(self, param="x"):
>         self.param = param
>         self.data = range(10, 1, -1)
>     def get(self, key):
>         k = "sorted_" + self.param
>         if not hasattr(self, "sorted_"):
This will only work for the first param.  After that, the attribute will
exist and the  the setattr will be skipped.
>             setattr(self, "sorted_", {k: sorted(self.data)})
>         return bisect.bisect_right(getattr(self, "sorted_")[k], x=key)
>>>> t = TestTwo("x")
>>>> t.get(1)
> 0
>  
>

Good job simplifying the problem.  But it's so simple i can't see what
the real goal is without some textual description.  Is a single instance
of this class intended to hold a single, unchanging list?  If not, are
you intending to delete the sorted_ attribute each time it changes?

The param value would make sense to me if it affected the sort.  But
otherwise, what's the point of having multiple sorted copies of a list,
when they'll all be identical?  And if param is constant for any given
instance of the class, then what's the point of all this indirection on it?

-- 

DaveA