Unique can be done by
set(items)
as long as the items are hashable. If you want a list back, just do
list(set(items))
This is O(n).
Flatten can be done by
sum(lists, [])
but it's O(n**2). Then again, so is your first definition of flatten
because you're popping from arbitrary list indexes inside a loop. I
think your flatten_original might be O(n**2) as well, and I'm not even
going to try to decipher flatten_continuation. ;)
On 4/3/08, Paul Jobs <[EMAIL PROTECTED]> wrote:
>
> def flatten(l, ltypes=(list, tuple)):
>
> """http://rightfootin.blogspot.com/2006/09/more-on-python-flatten.html""";
> i = 0
> while i < len(l):
> while isinstance(l[i], ltypes):
> if not l[i]:
> l.pop(i)
> if not len(l):
> break
> else:
> l[i:i+1] = list(l[i])
> i += 1
> return l
>
> def flatten_original(inlist, type=type, ltype=(list,tuple), maxint=
> sys.maxint):
> """Flatten out a list, code developed by myself and modified by Tim
> Peters, then by me again :)
> There is a very simple and quick flattener that can be found in the
> basictypes folder in the latebind.py script by Mike C. Fletcher. The source
> can be downloaded from
> http://sourceforge.net/project/showfiles.php?group_id=87034&package_id=90541&release_id=288585
> """
> try:
> # for every possible index
> for ind in xrange( maxint):
> # while that index currently holds a list
> while isinstance( inlist[ind], ltype):
> # expand that list into the index (and subsequent indicies)
> inlist[ind:ind+1] = list(inlist[ind])
> #ind = ind+1
> except IndexError:
> pass
> return inlist
>
>
> def flatten_continuation(a):
> """Flatten a list. Danny Yoo"""
> return bounce(flatten_k(a, lambda x: x))
>
>
> def bounce(thing):
> """Bounce the 'thing' until it stops being a callable."""
> while callable(thing):
> thing = thing()
> return thing
>
>
> def flatten_k(a, k):
> """CPS/trampolined version of the flatten function. The original
> function, before the CPS transform, looked like this:
>
> def flatten(a):
> if not isinstance(a,(tuple,list)): return [a]
> if len(a)==0: return []
> return flatten(a[0])+flatten(a[1:])
>
> The following code is not meant for human consumption.
> """
> if not isinstance(a,(tuple,list)):
> return lambda: k([a])
> if len(a)==0:
> return lambda: k([])
> def k1(v1):
> def k2(v2):
> return lambda: k(v1 + v2)
> return lambda: flatten_k(a[1:], k2)
> return lambda: flatten_k(a[0], k1)
>
> def unique(s):
> """Return a list of the elements in s, but without duplicates.
>
> For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
> unique("abcabc") some permutation of ["a", "b", "c"], and
> unique(([1, 2], [2, 3], [1, 2])) some permutation of
> [[2, 3], [1, 2]].
>
> For best speed, all sequence elements should be hashable. Then
> unique() will usually work in linear time.
>
> If not possible, the sequence elements should enjoy a total
> ordering, and if list(s).sort() doesn't raise TypeError it's
> assumed that they do enjoy a total ordering. Then unique() will
> usually work in O(N*log2(N)) time.
>
> If that's not possible either, the sequence elements must support
> equality-testing. Then unique() will usually work in quadratic
> time.
> """
>
> n = len(s)
> if n == 0:
> return []
>
> # Try using a dict first, as that's the fastest and will usually
> # work. If it doesn't work, it will usually fail quickly, so it
> # usually doesn't cost much to *try* it. It requires that all the
> # sequence elements be hashable, and support equality comparison.
> u = {}
> try:
> for x in s:
> u[x] = 1
> except TypeError:
> del u # move on to the next method
> else:
> return u.keys()
>
> # We can't hash all the elements. Second fastest is to sort,
> # which brings the equal elements together; then duplicates are
> # easy to weed out in a single pass.
> # NOTE: Python's list.sort() was designed to be efficient in the
> # presence of many duplicate elements. This isn't true of all
> # sort functions in all languages or libraries, so this approach
> # is more effective in Python than it may be elsewhere.
> try:
> t = list(s)
> t.sort()
> except TypeError:
> del t # move on to the next method
> else:
> assert n > 0
> last = t[0]
> lasti = i = 1
> while i < n:
> if t[i] != last:
> t[lasti] = last = t[i]
> lasti += 1
> i += 1
> return t[:lasti]
>
> # Brute force is all that's left.
> u = []
> for x in s:
> if x not in u:
> u.append(x)
> return u
>
> >
>
--
Gary
http://blog.extracheese.org
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"web.py" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/webpy?hl=en
-~----------~----~----~----~------~----~------~--~---
