Performance of stable marriage solution in Python 3 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) &gt; 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 &gt; 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)
I feel lazy to go through the details of your code, but here are few notes you should think about:


Your code, as it is, is not scalable. You should re-design it in terms of functions (I think functions are enough for your case, even in some other situations OOP may be a better choice). Functions allow also your code to be reused.
In terms of UX, I think you have some more work to do. For instance, when I run your code, I was waiting for something to happen, until I guessed to type in something, but then I had to check your code to see what it expects me to code. That is bad: imagine every software you use, you have to read its code to guess what you have to write or where to click.
You should throw a look to PEP 8 (for example, the naming conventions you use are camelCase, Python developers do not like that and you have to comply to the philosophy of Python)
Interesting if you throw a glance to: What does if __name__ == “__main__”: do?


That is the big picture I want to share with you for the moment ... maybe I can come back later to provide more useful help, or maybe other members may dive deeper into your code.