Performance of stable marriage solution in Python 3

Question

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)

Answer 1

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.

Answer 2

I have updated the code based on @Billal's suggestions and python code runs faster in a function

time: 0.12

memory: 33M

from sys import stdin, stdout


def find_woman(man_array, woman_array, index, mpref, wpref):
    for woman in mpref[index - 1]:
        if(woman == 0):
            continue
        hub = woman_array[woman - 1]
        if(hub == 0):
            woman_array[woman - 1] = index
            man_array[index - 1] = woman
            return 0
        elif(wpref[woman - 1].index(index) > wpref[woman - 1].index(hub)):
            continue
        else:
            man_array[hub - 1] = 0
            woman_array[woman - 1] = index
            man_array[index - 1] = woman
            return hub


def main():
    out = ''
    t = int(stdin.readline())
    while(t > 0):
        t -= 1
        n = int(stdin.readline())
        mpref = []
        wpref = []
        for _ in range(n):
            w = list(map(int, stdin.readline().split()))
            w[0] = 0
            wpref.append(w)
        for _ in range(n):
            m = list(map(int, stdin.readline().split()))
            m[0] = 0
            mpref.append(m)
        man_array = [0 for _ in range(n)]
        woman_array = [0 for _ in range(n)]
        for k in range(n):
            hub = k + 1
            while(hub != 0):
                hub = find_woman(man_array, woman_array, hub, mpref, wpref)
        for k in range(n):
            out += str(k + 1) + ' ' + str(man_array[k]) + '\n'
    stdout.write(out)


if(__name__ == "__main__"):
    main()

Answer 3

Your code is too obscure for me, I can't seem to wrap my head around it on a Monday morning. What I do understand is the way you parse the inputs. That way I do this is overwrite te builtin input during testing.

Define the sample data

input_str = '''2
4
1 4 3 1 2
2 2 1 3 4
3 1 3 4 2
4 4 3 1 2
1 3 2 4 1
2 2 3 1 4
3 3 1 2 4
4 3 2 4 1
7
1 3 4 2 1 6 7 5
2 6 4 2 3 5 1 7
3 6 3 5 7 2 4 1
4 1 6 3 2 4 7 5
5 1 6 5 3 4 7 2
6 1 7 3 4 5 6 2
7 5 6 2 4 3 7 1
1 4 5 3 7 2 6 1
2 5 6 4 7 3 2 1
3 1 6 5 4 3 7 2
4 3 5 6 7 2 4 1
5 1 7 6 4 3 5 2
6 6 3 7 5 2 4 1
7 1 7 4 2 6 5 3'''

Define how a line of data is parsed

def parse_people(input, people):
    for _ in range(people):
        person, *prefs = map(int, input().split())
        yield person, prefs

combine it

if(__name__ == "__main__"):
    input = iter(input_str.split('\n')).__next__
    test_cases = int(input())
    for _ in range(test_cases):
        people = int(input())
        women = dict(parse_people(input, people))
        men = dict(parse_people(input, people))
        print(people, men, women)

Then all you need to do when submitting, is removing or commenting the input = iter(input_str.split('\n')).__next__

I've also adopted more descriptive variable names, and instead of

w = list(map(int, stdin.readline().split()))
w[0] = 0
wpref.append(w)

I work with a generator and a dict. The result of my parsin is:

 women

{1: [3, 4, 2, 1, 6, 7, 5],
 2: [6, 4, 2, 3, 5, 1, 7],
 3: [6, 3, 5, 7, 2, 4, 1],
 4: [1, 6, 3, 2, 4, 7, 5],
 5: [1, 6, 5, 3, 4, 7, 2],
 6: [1, 7, 3, 4, 5, 6, 2],
 7: [5, 6, 2, 4, 3, 7, 1]}

That way you don't have to do the if(woman == 0):, and a lot of the indexing becomes easier. 0 or 1- indexing, or even names for input will not make a difference like this.

indexing

Following Gareth Rees' comment, instead of returning lists, you could let parse_people yield a lookup table, changing the call to .index to a dict lookup

def parse_people(input, people):
    for _ in range(people):
        person, *prefs = map(int, input().split())
        yield person, {k: i for i, k in enumerate(prefs)}

women

{1: {1: 3, 2: 2, 3: 0, 4: 1, 5: 6, 6: 4, 7: 5},
 2: {1: 5, 2: 2, 3: 3, 4: 1, 5: 4, 6: 0, 7: 6},
 3: {1: 6, 2: 4, 3: 1, 4: 5, 5: 2, 6: 0, 7: 3},
 4: {1: 0, 2: 3, 3: 2, 4: 4, 5: 6, 6: 1, 7: 5},
 5: {1: 0, 2: 6, 3: 3, 4: 4, 5: 2, 6: 1, 7: 5},
 6: {1: 0, 2: 6, 3: 2, 4: 3, 5: 4, 6: 5, 7: 1},
 7: {1: 6, 2: 2, 3: 4, 4: 3, 5: 0, 6: 1, 7: 5}}

Actual algorithm

After some thinking, I've taken a stab at your algorithm, converting the list-based approach to a dict-based one

parsing people

changed the input to a lookup table:

def parse_people(input, people):
    for _ in range(people):
        person, *prefs = map(int, input().split())
        yield person, {k: i for i, k in enumerate(prefs)}

Find the partners

the part in your main routine, the main difference is that I work with an OrderedDict as lookup table, instead of a list, and I use None as sentinel value instead of 0

def find_partners(people, prefs_women, prefs_men):
    from collections import OrderedDict
    choices_women = OrderedDict(((key, None ) for key in prefs_women))
    choices_men = OrderedDict(((key, None) for key in prefs_men))

    for k in choices_men:
        hub = k
        while(hub is not None):
            hub = find_woman(choices_women, choices_men, hub, prefs_women, prefs_men)
#             print(hub, choices_women)
    return choices_women, choices_men

finding the woman

Here I just tried to convert your code to the different indexing and lookup. By changing the comparison, you can omit the continue statement

def find_woman(choices_women, choices_men, index_man, prefs_women, prefs_men):
    for woman in prefs_men[index_man]:
        hub = choices_women[woman]
        if hub is None:
            choices_women[woman] = index_man
            choices_men[index_man] = woman
            return None
        elif prefs_women[woman][index_man] <= prefs_women[woman][hub]:
            choices_men[hub] = None
            choices_women[woman] = index_man
            choices_men[index_man] = woman
            return hub

combining it

if(__name__ == "__main__"):
    input = iter(input_str.split('\n')).__next__
    from collections import OrderedDict
    test_cases = int(input())
    for _ in range(test_cases):
        people = int(input())
        women = OrderedDict(parse_people(input, people, 'woman', 'man'))
        men = OrderedDict(parse_people(input, people, 'man', 'woman'))
#         print('-----preferences: ', women, men)
        choices_women, choices_men = find_partners(people, women, men)

        for man, woman in choices_men.items():
            print(man, ' ', woman)

I adapted my earlier version slightly

1   3
2   2
3   1
4   4
1   4
2   5
3   1
4   3
5   7
6   6
7   2

NB: for Python 3.6, you can use dict instead of OrderedDict, but that is an implementation detail

bughunting

Since the names of the men and women are the same, to hunt for a bug I changed the parse_people temporary to this:

def parse_people(input, people, sex1='man', sex2 = 'woman'):
    for _ in range(people):
        # person, *prefs = map(int, input().split())
        person, *prefs = input().split()
        # yield person, {k: i for i, k in enumerate(prefs)}
        yield sex1 + '_' + person, {sex2 + '_' + k: i for i, k in enumerate(prefs)}

for a more verbose output. This way I found out I had changed the order of women and men somewhere