How to modify this Python code (if needed) to make it more efficient?

Question

So you are given an integer n which corresponds to the number of loose socks you have. You are then given a list of socks with numbers corresponding to their tag/color.

For Example, the Sample input:

9
10 20 20 10 10 30 50 10 20

Would output:

3

The pairs in this case would be: (10,10), (20,20), (10,10) because each individual sock can only be used once.

I was able to find a solution to the problem by finding a pair and marking each tag to -1 to denote a sock that is already located in a pair. My first solution seemed inefficient, because the loops were iterating through values that also included the -1, so i made use of break and continue which i learned in class last week.

This is my most recent solution:

import sys


n = int(input().strip())
c = [int(c_temp) for c_temp in input().strip().split(' ')]

matching = 0
pairFound = True 

while pairFound:
    pairFound = False
    for i in range(len(c)):
        if c[i] == -1:
            continue
        for j in range(i+1,len(c)):
            if c[j] == -1:
                continue
            if c[i] == c[j] and c[i] != -1 and c[j] != -1:
                pairFound=True
                matching = matching + 1
                c[i]=-1
                c[j]=-1
            if c[i] == -1:
                break
print(matching)

How efficient is the code I have written?

I'm not really looking for an alternative solution, I am more interested in a way to tweak this to make my existing code better.

Thanks guys.

Answer 1

My solution make use of collections.Counter

>>> import collections
>>> c = [10, 20, 20, 10, 10, 30, 50, 10, 20]
>>> sum([int(i/2) for i in collections.Counter(c).values()])
>>> 3

If wanna get the details of the repeated pair, use code below.It show we got 4 occurence of 10, 3 occurence of 20 and so on is most occur order

>>> import collections
>>> c = [10, 20, 20, 10, 10, 30, 50, 10, 20]
>>> collections.Counter(c).most_common ()
>>> [(10, 4), (20, 3), (50, 1), (30, 1)]

Answer 2

Your approach is quite okay from a conceptual perspective for someone who is doing the first steps in programming:

• The good thing is, that you only take the subsequent list for each item from your first for loop into account and do not iterate over the entire list.

• The bad thing is, what probably lets you think that this can be improved, that you mark socks that have been assigned a pair instead of removing them from the list. Removing them would shorten the list and thus reduce the computation steps required to finish the task. However, removing items from a list while iterating over it is a bad idea, so you need something different here.

• Additionally, you can omit your enclosing while loop, because the first for loop will anyway end once the end of the sock sequence is reached. Watch out for IndexErrors when accessing the subsequent list when you reached the end.

I doubt that you have covered recursion in class yet, but this would be an efficient approach of iterating over changing lists and at the same time collecting items that cannot be assigned to a pair (i.e. lonely socks).

Recursion is about calling a function from itself:

Let socks be your input list. You can split it into its head (the first element) and rest (all other elements).

socks = [10, 20, 10, 40]
head = socks[0] # Here, head will be 10
rest = socks[1:] # Here, rest will be [20, 10, 40]

For the first step, you need to search for an element in rest that is equal to your head. Once found, you can remove it from rest as it cannot be paired more than once:

for i, s in enumerate(rest):
    if s == head:
        match = rest.pop(i)
        break

Now after this step, you know that you have found a pair consisting of the elements head and match. And, your rest list has changed: You have removed the matching part:

[20, 40]

You can repeat these steps until the rest list is of length <= 1, so we would need another run here, where head would be 20 and rest would be [40]. Iterating over rest would not yield a pair and we should return it as-is.

Once your iteration has reached the point where the length of rest is <= 1, you can exit, as you know that you must have found all pairs.

In code, this could look like this:

import random

def seek_pair(lst):
    if len(lst) <= 1:
        # Nothing to do if we cannot split list into head and rest
        return lst

    # Split list into head and rest
    head, rest = lst[0], lst[1:]

    # Iterate over rest and try to find a match
    match = None
    for i, s in enumerate(rest):
        if s == head:
            # We have found an element that equals our head
            # Remove it from the list and store it in variable 'match'
            match = rest.pop(i)
            # Break the loop as we have found a match
            break

    if match:
        # If there was a match in the 'rest' list, we can print it
        print('Pair: ({:d}, {:d})'.format(head, match))
        # And call the method 'seek_pair()' on the resulting 'rest'
        # Note that here, the matching element has already been
        # removed from the list 'rest'.
        return seek_pair(rest) # RECURSION
    else:
        # If no match was found, we still need to search the 'rest'
        # list for other matches.
        # And, since 'head' did not match any other element, we append
        # it to the beginning of our result list, which will hold all
        # elements without matches (i.e. lonely socks).
        return [head] + seek_pair(rest) # RECURSION

if __name__ == '__main__':
    # Randomly generate an input list of desired length
    n = 9
    socks = [random.randint(1, 9) * 10 for _ in range(n)]

    # Print the list
    print('Socks: {:s}'.format(', '.join([str(s) for s in socks])))
    # Call the function on the entire list and obtain its result,
    # that should contain all lonely socks.
    rest = seek_pair(socks)
    # Print lonely socks
    print('Rest: {:s}'.format(', '.join([str(s) for s in rest])))

The output of this code looks similar to this:

Socks: 30, 10, 30, 40, 30, 50, 40, 60, 70
Pair: (30, 30)
Pair: (40, 40)
Rest: 10, 30, 50, 60, 70

Answer 3

Your code is not overly efficient, since its runtime is proportional to the square of the number of elements (i.e. socks). You can achieve a linear runtime by just counting the elements and taking the sum of (number_elements // 2). If really interested in runtime, I would recommend to use Counter class from module collections.