I am trying to solve the stable marriage problem in SPOJ in Python 3.
There are given \$n\$ men and \$n\$ women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange \$n\$ marriages in such a way that if a man \$m\$ prefers some woman \$w\$ more than his wife, then \$w\$ likes her husband more than \$m\$. In this way, no one leaves his partner to marry somebody else. This problem always has a solution and your task is to find one.
Input
The first line contains a positive integer \$t \le 100\$ indicating the number of test cases. Each test case is an instance of the stable marriage problem defined above. The first line of each test case is a positive integer \$n \le 500\$ (the number of marriages to find). The next \$n\$ lines are the woman's preferences: \$i\$th line contains the number \$i\$ (which means that this is the list given by the \$i\$th woman) and the numbers of men (the first choice of \$i\$th woman, the second choice,...). Then, the men's preferences follow in the same format.
Output
For each test case print \$n\$ lines, where each line contains two numbers \$m\$ and \$w\$, which means that the man number \$m\$ and the woman number \$w\$ should get married.
I have tried optimising the code as much as I can (remove slicing, keep it minimal array, remove printing one by one... etc).
But by far the best code I have been able to get runs in 0.13(s?) time and 33M(??) memory. But the best code for the same problem in Python 3 (submitted by @_@) runs in 0.09 time and 13M memory. So I would like suggestions on how to attain the best time and space usage with my code
from sys import stdin, stdout
def findWoman(manArray, womanArray, index, mpref, wpref):
for woman in mpref[index - 1]:
if(woman == 0):
continue
hub = womanArray[woman - 1]
if(hub == 0):
womanArray[woman - 1] = index
manArray[index - 1] = woman
return 0
elif(wpref[woman - 1].index(index) > wpref[woman - 1].index(hub)):
continue
else:
manArray[hub - 1] = 0
womanArray[woman - 1] = index
manArray[index - 1] = woman
return hub
out = ''
t = int(stdin.readline())
while(t > 0):
t -= 1
n = int(stdin.readline())
mpref = []
wpref = []
for _ in range(0, n):
w = list(map(int, stdin.readline().split()))
w[0] = 0
wpref.append(w)
for _ in range(0, n):
m = list(map(int, stdin.readline().split()))
m[0] = 0
mpref.append(m)
manArray = [0 for _ in range(n)]
womanArray = [0 for _ in range(n)]
for k in range(n):
hub = k + 1
while(hub != 0):
hub = findWoman(manArray, womanArray, hub, mpref, wpref)
for k in range(n):
out += str(k + 1) + ' ' + str(manArray[k]) + '\n'
stdout.write(out)
index
method infindWoman
which take time proportional to the length of the list. These could be sped up by making reverse lookup tables. \$\endgroup\$ – Gareth Rees Jan 28 '18 at 12:20