Team. Coco - 1 year ago 48
Python Question

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

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.

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 `IndexError`s 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]
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):
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

# Iterate over rest and try to find a match
match = None
for i, s in enumerate(rest):
# 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
# 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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download