Write this accumuator in a functional style
Steve D'Aprano
steve+python at pearwood.info
Wed Jul 12 00:18:00 EDT 2017
On Tue, 11 Jul 2017 04:58 pm, Chris Angelico wrote:
> On Tue, Jul 11, 2017 at 4:11 PM, Steven D'Aprano <steve at pearwood.info> wrote:
[...]
>> accumulator = {'blue': [], 'green': [], 'red': []}
>> for parrot in parrots:
>> accumulator[parrot.colour].append(parrot)
[...]
> It's a partitioning filter. (Three way, not the usual two, but same
> same.) I've actually often wanted a quick way to write that - where
> you divide a list into two according to "passes predicate" vs "fails
> predicate". So if you find a really nice solution, I'm interested.
That is one of my colleague's complaints too: he says this is a common task and
there ought to be a built-in or at least std lib functional solution for it,
akin to map/filter/itertools.
Although I often say "not every two or three line function needs to be a
built-in", in this case I'm inclined to agree with him. Now that I have a name
for it, I am even more inclined to agree.
It's an N-way partitioning filter. My example shows only three, but the real
code we're using has more than that.
def partition(iterable, keyfunc=bool):
accumulator = {}
for item in iterable:
accumulator.setdefault(keyfunc(item), []).append(item)
return accumulator
Alternatives:
- itertools.groupby requires you to sort the entire input stream
before starting; that's expensive, O(N log N) rather than just O(N).
- Greg's dict comprehension version requires N+1 passes through the data,
one to convert to a list, and 1 per each possible key.
- Terry's solution scares me :-)
- Alain's solution appears to require list concatenation, which implies
that in the worst case this will be O(N**2).
Any other thoughts?
--
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.
More information about the Python-list
mailing list