Hey everyone, I recently used list.count() in a coding interview and the question arose about how scale-able this solution was for sufficiently large input. Currently, list.count iterates through the list, incrementing the count as it goes and returning the value at the end. This does not lend itself well to large inputs. I propose either modifying the list struct to include a map of item -> count, or implementing a new structure with this information that is allocated separately when a list is instantiated. Maybe I'm just seeing this since it's an edge case that I recently dealt with, but I believe it would be a useful enhancement overall. Thoughts?
On Tue, Jan 14, 2020 at 10:03:24PM -0600, Hunter Jones wrote:
Hi Hunter, does collections.Counter meet your needs? https://docs.python.org/3.8/library/collections.html#collections.Counter best, --titus -- C. Titus Brown, ctbrown@ucdavis.edu
On Wed, 15 Jan 2020 at 13:37, Hunter Jones <hjones82493@gmail.com> wrote:
Personally, I don't think it's something that's needed often enough to justify the overhead on such a core Python data structure. If you have an application (or interview question!) that needs to maintain counts a lot, then I'd suggest that you might want to use a different data structure - maybe a collections.Counter, or implement your own "list plus count mapping" data structure the way you suggest. But without strong evidence that this would be used a lot, I don't think such a feature justifies the cost as part of the built in list data structure. Paul
On 1/14/2020 11:03 PM, Hunter Jones wrote:
That seems like a pretty niche requirement. In all of my years using Python I've never needed such a thing. I suggest that when you need this functionality you create your own data structure combining a list and a collections.Counter and keep track of this yourself. Eric
I concur with the usage of collections.Counter here. Storing the count for every single item in a list could end up being rather redundant with duplicate elements, so Counter ends up being much more space efficient. With it being implemented as a dictionary, the lookup speeds are incredibly quick for getting an on-demand count for any item within it. But, is it practically beneficial to combine the functionality of a list and collections.Counter instead of just using both data structures together? Here's a rough example of what I'm talking about. I recall using something vaguely similar to this before: ``` items = [...] counter = collections.Counter(items) for item in items: # use counter[item] instead of items.count(item) if count := counter[item] > x: # do something with item and its count ``` (Note: omit "count :=" if the count isn't needed for anything beyond the conditional check) On Wed, Jan 15, 2020 at 10:34 AM Eric V. Smith <eric@trueblade.com> wrote:
I meant by composing them in another class, which could then have whatever interface makes sense for this data structure.
Ah, I see. I had misunderstood you and thought you were advising the OP to combine list and Counter into their own new data structure, which seemed a bit overkill. That makes a lot more sense, thanks for the clarification. On Wed, Jan 15, 2020 at 8:20 PM Eric V. Smith <eric@trueblade.com> wrote:
On Tue, Jan 14, 2020 at 10:03:24PM -0600, Hunter Jones wrote:
Hi Hunter, does collections.Counter meet your needs? https://docs.python.org/3.8/library/collections.html#collections.Counter best, --titus -- C. Titus Brown, ctbrown@ucdavis.edu
On Wed, 15 Jan 2020 at 13:37, Hunter Jones <hjones82493@gmail.com> wrote:
Personally, I don't think it's something that's needed often enough to justify the overhead on such a core Python data structure. If you have an application (or interview question!) that needs to maintain counts a lot, then I'd suggest that you might want to use a different data structure - maybe a collections.Counter, or implement your own "list plus count mapping" data structure the way you suggest. But without strong evidence that this would be used a lot, I don't think such a feature justifies the cost as part of the built in list data structure. Paul
On 1/14/2020 11:03 PM, Hunter Jones wrote:
That seems like a pretty niche requirement. In all of my years using Python I've never needed such a thing. I suggest that when you need this functionality you create your own data structure combining a list and a collections.Counter and keep track of this yourself. Eric
I concur with the usage of collections.Counter here. Storing the count for every single item in a list could end up being rather redundant with duplicate elements, so Counter ends up being much more space efficient. With it being implemented as a dictionary, the lookup speeds are incredibly quick for getting an on-demand count for any item within it. But, is it practically beneficial to combine the functionality of a list and collections.Counter instead of just using both data structures together? Here's a rough example of what I'm talking about. I recall using something vaguely similar to this before: ``` items = [...] counter = collections.Counter(items) for item in items: # use counter[item] instead of items.count(item) if count := counter[item] > x: # do something with item and its count ``` (Note: omit "count :=" if the count isn't needed for anything beyond the conditional check) On Wed, Jan 15, 2020 at 10:34 AM Eric V. Smith <eric@trueblade.com> wrote:
I meant by composing them in another class, which could then have whatever interface makes sense for this data structure.
Ah, I see. I had misunderstood you and thought you were advising the OP to combine list and Counter into their own new data structure, which seemed a bit overkill. That makes a lot more sense, thanks for the clarification. On Wed, Jan 15, 2020 at 8:20 PM Eric V. Smith <eric@trueblade.com> wrote:
participants (5)
-
C. Titus Brown -
Eric V. Smith -
Hunter Jones -
Kyle Stanley -
Paul Moore