Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #61678

Re: min max from tuples in list

Show all headers | View raw

On Thu, Dec 12, 2013 at 6:25 PM, Robert Voigtländer
<r.voigtlaender@gmail.com> wrote:
> I need to find a -performant- way to transform this into a list with tuples (a[0],[a[0][1]min],[a[0][1]max]).
>
> Hard to explaint what I mean .. [0] of the first three tuples is 52. [1] is 193,193 and 192.
> What I need as result for these three tuples is: (52,192,193).
>
> For the next five tuples it is (51,188,193).
>
>
> Extra challenges:
> - This list is sorted. For performance reasons I would like to keep it unsorted.
> - There may be tuples where min=max.
> - There my be tupples where [0] only exists once. So mix is automatically max

Yep, I see what you mean! Apart from the first of the challenges,
which is ambiguous: do you mean you'd rather be able to work with it
unsorted, or is that a typo, "keep it sorted"?

This is a common task of aggregation. Your list is of (key, value)
tuples, and you want to do some per-key statistics. Here are three
variants on the code:

# Fastest version, depends on the keys being already grouped
# and the values sorted within each group. It actually returns
# the last and first, not the smallest and largest.
def min_max_1(lst):
    prev_key = None
    for key, value in lst:
        if key != prev_key:
            if prev_key is not None: yield prev_key, value, key_max
            key_max = value
    if prev_key is not None: yield prev_key, value, key_max

# This version depends on the keys being grouped, but
# not on them being sorted within the groups.
def min_max_2(lst):
    prev_key = None
    for key, value in lst:
        if key != prev_key:
            if prev_key is not None: yield prev_key, key_min, key_max
            key_min = key_max = value
        else:
            key_min = min(key_min, value)
            key_max = min(key_max, value)
    if prev_key is not None: yield prev_key, key_min, key_max

# Slowest version, does not depend on either the keys
# or the values being sorted. Will iterate over the entire
# list before producing any results. Returns tuples in
# arbitrary order, unlike the others (which will retain).
def min_max_3(lst):
    data = {}
    for key, value in lst:
        if key not in data:
            data[key]=(value, value)
        else:
            data[key][0] = min(data[key][0], value)
            data[key][1] = min(data[key][1], value)
    for key, minmax in data.items():
        yield key, minmax[0], minmax[1]

Each of these is a generator that yields (key, min, max) tuples. The
third one needs the most memory and execution time; the others simply
take the input as it comes. None of them actually requires that the
input be a list - any iterable will do.

ChrisA

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

min max from tuples in list Robert Voigtländer <r.voigtlaender@gmail.com> - 2013-12-11 23:25 -0800
  Re: min max from tuples in list Chris Angelico <rosuav@gmail.com> - 2013-12-12 19:18 +1100
  Re: min max from tuples in list Robert Voigtländer <r.voigtlaender@gmail.com> - 2013-12-12 00:34 -0800
    Re: min max from tuples in list Chris Angelico <rosuav@gmail.com> - 2013-12-12 19:43 +1100
  Re: min max from tuples in list Peter Otten <__peter__@web.de> - 2013-12-12 09:35 +0100
  Re: min max from tuples in list Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-12-12 10:52 +0200
  Re: min max from tuples in list Peter Otten <__peter__@web.de> - 2013-12-12 10:03 +0100
  Re: min max from tuples in list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-12 11:44 +0000
    Re: min max from tuples in list Tim Chase <python.list@tim.thechases.com> - 2013-12-12 06:04 -0600
    Re: min max from tuples in list MRAB <python@mrabarnett.plus.com> - 2013-12-12 12:36 +0000
      Re: min max from tuples in list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-12 23:25 +0000
    Re: min max from tuples in list Peter Otten <__peter__@web.de> - 2013-12-12 13:54 +0100
      Re: min max from tuples in list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-13 02:36 +0000
    Re: min max from tuples in list Roy Smith <roy@panix.com> - 2013-12-12 10:02 -0500
      Re: min max from tuples in list Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-12-12 15:13 +0000
        Re: min max from tuples in list Robert Voigtländer <r.voigtlaender@gmail.com> - 2013-12-12 22:28 -0800
          Re: min max from tuples in list rusi <rustompmody@gmail.com> - 2013-12-13 10:06 -0800
            Re: min max from tuples in list Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2013-12-13 19:30 -0500
              Re: min max from tuples in list Tim Roberts <timr@probo.com> - 2013-12-14 19:41 -0800
                Re: min max from tuples in list Chris Angelico <rosuav@gmail.com> - 2013-12-16 23:08 +1100
                Re: min max from tuples in list rusi <rustompmody@gmail.com> - 2013-12-16 07:49 -0800
                Re: min max from tuples in list Ned Batchelder <ned@nedbatchelder.com> - 2013-12-16 10:59 -0500
                Re: min max from tuples in list Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2013-12-17 11:49 +1300
  Re: min max from tuples in list Denis McMahon <denismfmcmahon@gmail.com> - 2013-12-13 01:33 +0000

csiph-web