Производительность стабильный брак решение в Python 3


Я пытаюсь решить проблему стабильного брака в SPOJ в Python 3.

Даны \ФП\$ мужчин и $\Н\$ женщин. Каждая женщина оценивает всех мужчин в порядке ее предпочтения (первый ее выбор, ее выбор, и так далее). Аналогично, каждый мужчина сортирует женщин в соответствии с его предпочтениями. Цель состоит в том, чтобы организовать \ФП\$ браков таким образом, что если человек \$м\$ предпочитает какую-то женщину \Вт\$ больше, чем его жена, затем \$ш\$ любит мужа больше, чем \$М\$. Таким образом, никто не покидает своего партнера, чтобы выйти замуж за кого-то другого. Эта проблема всегда имеет решение, и ваша задача-найти один.

Вход

Первая строка содержит целое положительное число \$Т \Ле 100\$ показывающее количество тестов. Каждый тест является экземпляром задача стабильного брака определено выше. Первая строка каждого теста-это целое положительное число \$п \Ле 500\$ (число браков, чтобы найти). Следующий \ФП\$ линии женского предпочтения: \$я$я строка содержит числа $\я\$ (что означает, что это список дается \$я$е женщины) и мужчин (первый выбор \$я$е женщину, второе на выбор,...). Затем, предпочтений мужчины следуют в аналогичном формате.

Выход

Для каждого теста вывести \ФП\$ строк, каждая строка содержит два числа \$м$ и $\Вт\$, что означает, что человек числа $\м\ долл., а женщина числа $\Вт\$ должны пожениться.

Я пробовал оптимизировать код так, как я могу (удалить нарезки, минимальное время, удалить печать по одному... и т. д.).

Но однозначно лучший код, который я смог сделать, работает в 0.13(ы?) время и 33М(??) памяти. Но лучший код для той же задачи в Python 3 (представленный @_@) выполняется в 0.09 времени и 13М памяти. Поэтому я хотел бы предложения о том, как достичь наилучшего времени и использования пространства с мой код

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)


Комментарии
3 ответа

Я чувствую, что лень идти через детали вашего кода, но вот некоторые заметки, которые вы должны думать о:


  • Ваш код, как это, не масштабируемый. Вы должны ре-дизайн ее в терминах функций (я думаю, что функций достаточно для вашего случая, даже в некоторых других ситуациях ООП может быть лучшим выбором). Функции позволяют также ваш код, чтобы быть повторно использованы.

  • С точки зрения УБ, я думаю, у вас есть больше работы, чтобы сделать. Например, когда я запускаю свой код, я ждал что-то случится, пока я не догадался что-нибудь ввести, но тогда я должен был проверить свой код, чтобы увидеть, что он ждет от меня код. Что плохо: представьте, что каждая программа, которую вы используете, вы должны прочитать его код, чтобы догадаться, что надо писать или куда нажать.

  • Вы должны бросить взгляд на ПЭП 8 (например, Соглашения об именовании, которые вы используете верблюжьего, питона разработчикам не нравится, что и вы должны соответствовать философии питона)

  • Интересно, если бросить взгляд на: что значит если __имя__ == “__основной__”: Что делать?

Это картину я хочу поделиться с вами на данный момент ... может быть, я могу вернуться позже, чтобы обеспечить более полезный, или, может быть, другие участники могут погрузиться глубже в код.

6
ответ дан 28 января 2018 в 08:01 Источник Поделиться

Я обновил код, основанный на @Billal предложения и Python код работает быстрее в функции

время: 0.12

память: 33М

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()

3
ответ дан 28 января 2018 в 11:01 Источник Поделиться

Ваш код является слишком неясным для меня, я не могу показаться, чтобы обернуть мою голову вокруг него в понедельник утром. Я понимаю то, как вы разбираете входов. Таким образом, я сделать это переписать те встроенные input во время испытания.

Определить образец данных

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'''

Определить, как разобранные линии данных

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

сочетать его

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)

Тогда все что вам нужно сделать для подачи, удаления или комментирования input = iter(input_str.split('\n')).__next__

Я также принял более описательные имена переменных, и вместо

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

Я работаю с генератором и дикт. Результат моего парсин является:


 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]}

Таким образом, вы не должны делать if(woman == 0):и много индексирования будет легче. 0 или 1 - индексации, или даже имена для входа не будет разницы такой.

индексация

Следующим Гарет Риз комментарий, Вместо того, чтобы возвращать списки, вы могли бы дать parse_people урожайность таблица, изменения вызова .index к дикт поиска

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}}

Фактический алгоритм

После некоторых раздумий, я принял удар на свой алгоритм, преобразование listподход к dict-на основе

парсинг людей

изменил входные данные для таблицы подстановки:

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)}

Найти партнеров

часть в main подпрограмма, основное различие заключается в том, что я работаю с OrderedDict как таблица, а не список, и я использую не в качестве дозорного значение вместо 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

найти женщину

Здесь я просто пытался преобразовать ваш код в разных индексирования и поиска.
Изменяя сравнение, можно опустить continue заявление

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

сочетая его

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)

Я слегка адаптированная моей предыдущей версии

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

Примечание: для Python 3.6, вы можете использовать dict вместо OrderedDictно это деталь реализации

bughunting

Поскольку имена мужчины и женщины одинаковы, чтобы охотиться за ошибка, Я изменил parse_people временный следующему:

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)}

для более подробного вывода. Таким образом я узнала, что у меня изменился порядок women и men где-то

0
ответ дан 29 января 2018 в 10:01 Источник Поделиться