Python Forum
Need to speed up my code.
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Need to speed up my code.
#1
I have to return a simple sum of the most present values in the array, ie [3,5,2,1,2,3,2,2] - > should return 4, because (2,2,2,2).
The array sometimes is crazy focking big, and I cannot pass the execution time limit on the website that im practicing.

My code now is like that:

def birthdayCakeCandles(ar):
    def count_em(x):
        fin = ar.count(x)
        ar.remove(x)
        return fin

    return max(map(count_em,ar))
ar.remove is to not repeat the iteration for every occurrence of a same value, but it doesnt even feel like a speed up, is it even cached in cpu this way?
Reply
#2
Try this

import collections
value = collections.Counter(ar).most_common(1)[0][1]
Reply
#3
The performance issues seem reasonably obvious: you're doing a count (which one would assume is O(n)) on each iteration and you're also doing a remove each iteration (which is also O(n)). So, you're doing O(n^2) operations, given that map will also be O(n). You can at least figure out the most common in a single pass over the array (it is left as an exercise to figure out exactly how!) and then do the summing after that.
Reply
#4
Hey. Sorry for my response time.
So the oneliner using collections.Counter seems to be fastest, but I cant understand why and how.

My fastest solution for this, without importing any external modules is like this:
def birthdayCakeCandles(ar):
    initial, results = 0, []
    dikk = {k:initial for k in ar}

    for x in ar:
        if x in results:
            dikk[x] += 1
        else:
            results.append(x)
            dikk[x] += 1
               
    return max(dikk.values())
And its still seems to be too slow, passes only 9/10 tests.
How to do this better with using just simple and readable basic python?
Reply
#5
(Jan-19-2020, 01:24 AM)blackknite Wrote: So the oneliner using collections.Counter seems to be fastest, but I cant understand why and how.
How to do this better with using just simple and readable basic python?

I believe that collections.Counter (and other stuff from built-in collections module) is worth of learning and should be considered as 'simple and readable basic Python'. This is special data structure for counting and it would be non-productive to invent a wheel. Just type help(collections.Counter) into interactive interpreter and you get description, examples etc.

If no Counter allowed or understood then it of course can be done 'manually' (and with O(n) - iterating only once over list):

>>> lst = [3,5,2,1,2,3,2,2]             # list to be iterated
>>> counts = dict()                     # dictionary for keeping counts of occurances
>>> for item in lst:                    # iterate all list items
...     try:                            # try +1 to value of key
...         counts[item] += 1
...     except KeyError:                # if key is not existing (raises KeyError)
...         counts[item] = 1            # add key and set value to 1 (first count)
... 
>>> counts[lst[-1]]                     # retrieve count of last item in lst from count dict
4
If try...except is not qualifying as 'simple readable and basic Python' then we can make it even simpler by not using 'advanced Python':

>>> counts = dict()
>>> for item in lst:
...     if item in counts:                  # if item already counted add one
...         counts[item] += 1
...     else:                               # else means that first time encountered
...         counts[item] = 1                # add key and set value to one
... 
>>> counts[lst[-1]]                         # get count of last item in lst
4
>>> counts                                  # whole counts dictionary
{3: 2, 5: 1, 2: 4, 1: 1}
There is also collections.defaultdict but in sense of 'basic Python' it's not any better than collections.Counter.

EDIT:

And of course there is always:

>>> lst = [3,5,2,1,2,3,2,2]                                                    
>>> lst.count(lst[-1])                                                            
4
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#6
Not sure that answers OPs question. That was to print the count of the most frequent item, not the frequency of the last item in the list. By that, you would need to sort the dictionary by value and then take the last dictionary item. If you add a 3 to the end of his list, the posted code yields 3 which is incorrect - the max is still 4, based on the most frequent item (2).
Add one step, sort by value, then print which item is most frequent and that item's frequency:
lst = [3,5,2,1,2,3,2,2,3]             # list to be iterated
counts = dict()                     # dictionary for keeping counts of occurances
for item in lst:                    # iterate all list items
    try:                            # try +1 to value of key
        counts[item] += 1
    except KeyError:                # if key is not existing (raises KeyError)
        counts[item] = 1            # add key and set value to 1 (first count)
counts = sorted(counts.items(), key = lambda kv:(kv[1], kv[0]))

print(f'Most common is {counts[-1][0]} with a frequency of {counts[-1][1]}')
Reply
#7
Mea culpa. I realise that I misunderstood OP-s problem. I interpreted 'sum of the most present values in the array' as 'most present value in the array i.e. last item present in list'. My bad. Counting part is still relevant but not finding the maximum count value.

Iterating jefsummers code: we can apply key to max function as well, so one can write:

>>> max_count = max(counts.items(), key = lambda kv:kv[1])[1]   # from key, value pair we take only value by using index [1]
>>> max_count
4   
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020