0

I want to get all the maximum values from an iterator:

def max_val(iterator, key=None):
  # ???
it = (i for i in range(4))
assert max_val(it, key=lambda i: i%2) == [1, 3]

Note: this question is similar to what was asked before for a list.

There are 2 differences with the previous question:

1) I want this to work for an iterator, so I can't use the 2-pass approach that was both the fastest and the simplest solution to the list question.

2) I want to get the maximum values rather than indices. It might sound weird, but this is useful if I specify a key argument as in the above example (or if the objects have ordering based only on part of their internal state).

One solution is a slightly modified @martineau answer to the list question (it would need to store the values instead of indices), but I was wondering if there's a faster approach.

Community
  • 1
  • 1
max
  • 49,282
  • 56
  • 208
  • 355
  • In general, you *cannot* return the maximum value(s) as an iterator (in one pass), because there is no way for you to know if a potential value *is* a maximum until you have consumed the entire sequence. A special case in your example is when there is a known largest possible maximum value (here, you know that `i % 2 <= 1` for all `i`); once you find at least one value that obtains this maximum, you could start `yield`ing them. Otherwise, though, you need to accumulate maximums in memory (as in martineau's answer) until you know they are actually maximums. – chepner Dec 15 '16 at 01:50
  • @chepner Yes, the return value would be a list rather than an iterator (only the input is an iterator). And yes, it is necessary to consume the entire iterator and store intermediate results. – max Dec 15 '16 at 01:54
  • The part where you say "it would need to store the values instead of indices" doesn't make sense. The value at all the indices would be the same for all of them—the maximum value. – martineau Dec 15 '16 at 05:18
  • @martineau I meant if key is not the default (identity) function – max Dec 15 '16 at 05:28
  • Dunno, "the key is not the default (identity) function" doesn't make sense, to me either. The question you link to finds the indices of where the maximum value is stored. It doesn't have a `key` function although one could be added...fairly easily, I believe. Although I retracted my vote to close your question as unclear, I still think it is. Suggest you show some sample input and desired output. – martineau Dec 15 '16 at 05:40

1 Answers1

2
def max_val(iterator, key=None):
    try:
        ret = [iterator.next()]
    except StopIteration:
        return []
    for val in iterator:
        if key(val) < key(ret[0]):
            continue
        elif key(val) == key(ret[0]):
            ret.append(val)
        else:
            ret = [val]
    return ret

One pass, passes your assertion.

It just keeps the best set it's found until it finds one better, then starts over.

martineau
  • 119,623
  • 25
  • 170
  • 301
TemporalWolf
  • 7,727
  • 1
  • 30
  • 50
  • If there's no way to use builtin functions, then yes this is the only way. – max Dec 15 '16 at 02:15
  • @max: For the iterator `iterator = iter([1, 2, 6, 3, 4, 5, 6])` the results this produces—`[6, 6]`—illustrate why I claim your question doesn't really make any sense. In your question you say "I want to get the maximum values", but seem to not realize there's only going to be one of those. The question that was asked before, wants to find all the places (indices) where **the** maximum value occurs in a sequence (which can be indexed, and therefore "has" indices), which _does_ have some sensibility. – martineau Dec 15 '16 at 19:28
  • @martineau hmm maybe I'm missing something obvious, but look at my question's example: `max_val(it, key=lambda i: i%2)`. It should return `[1, 3]` because two different items `v` produced by the iterator evaluate to maximum in the sense of `key(v)`. I use `key` in the same sense as builtin `max` uses it. Using your example, the same `key = lambda i: i%2` should yield `[1, 3, 5]`. If you do not provide `key`, it uses the implied default `key = lambda i: i`, which of course makes my question meaningless in your example. That's why I said I assumed `key` was not left as default. – max Dec 15 '16 at 21:06
  • In what way are the elements of the list `[1, 3]`—the numeric values `1` and `3`—the _maximum_ values produced from applying the `key` function to the iterator? In what sense are they the "maximum" value(s)? The fact that the default value for the `key` function in your question is `None` instead of `key=lambda x: x` (the proper definition of an identity function) only further obfuscates your question (to me). – martineau Dec 15 '16 at 21:38
  • @max Yes, my original answer did not include any error handling which would be needed in a true implementation. martineau: his original key was `lambda i: i % 2`: `1 % 2 == 1`, `3 % 2 == 1` which are the maximum values you can obtain from `i % 2` – TemporalWolf Dec 15 '16 at 21:39