Более быстрое или более эффективное решение для памяти в Python для этой проблемы Codejam

Question

Я попробовал свои силы в этой Google Codejam Africa (конкурс уже завершен, я только что сделал это, чтобы улучшить свои навыки программирования).

Проблема:

Вы устраиваете вечеринку с гостями G и обратите внимание, что есть нечетное число гостей! При планировании вечеринки вы намеренно приглашены только пары и дал каждой паре уникальный номер C на их приглашение. Вы хотели бы выделить кого бы то ни было просить всех гостей за их пригласительные номера.

Вход:

Первая строка ввода дает количество случаев, N. N тестовых случаев. Для каждого теста будет:

• Одна строка, содержащая значение G the число гостей.
• Одна строка, содержащая разделенный пробелами список G целых чисел. Каждое целое число C обозначает пригласительный код гостя. Выход

Для каждого теста выведите одну строку содержащий "Case #x:", сопровождаемый число C гостя, который один.

Пределы:

• 1 ≤ N ≤ 50
• 0

Маленький набор данных

3 ≤ G <100 </p>

Большой набор данных

3 ≤ G <1000 </p>

Пример ввода:

3
3
1 2147483647 2147483647
5
3 4 7 4 3
5
2 10 2 10 5

Пример вывода:

Case #1: 1
Case #2: 7
Case #3: 5

Вот решение, которое я придумал:

with open('A-large-practice.in') as f:
    lines = f.readlines()

with open('A-large-practice.out', 'w') as output:
    N = int(lines[0])
    for testcase, i in enumerate(range(1,2*N,2)):
        G = int(lines[i])
        for guest in range(G):
            codes = map(int, lines[i+1].split(' '))
            alone = (c for c in codes if codes.count(c)==1)
        output.write("Case #%d: %d\n" % (testcase+1, alone.next()))

Он запускается на моей машине за 12 секунд с большим вводом .

Теперь мой вопрос: можно ли улучшить это решение в Python, чтобы оно работало в более короткие сроки или использовало меньше памяти? анализ проблемы дает некоторые указания о том, как сделать это в Java и C ++, но я не могу перевести эти решения обратно в Python.

Edit:

Включая советы Алекса Мартелли и IVlad ниже, у меня теперь есть это решение, которое работает в 0.079s:

with open('A-large-practice.in') as f:
    lines = f.readlines()

with open('A-large-practice.out', 'w') as output:
    N = int(lines[0])
    for testcase, i in enumerate(range(1,2*N,2)):
        codes = map(int, lines[i+1].split(' '))
        alone = 0
        for c in codes: alone ^= c
        output.write("Case #%d: %d" % (testcase+1, alone))

Answer 1

Я не знаю про python, но сама проблема классическая. Учитывая 2K - 1 чисел, каждое из которых, кроме одного, появляется четное число раз, найти то, которое появляется нечетное число раз.

Необходимые формулы:

1. x xor x == 0 for all x
2. x xor y == y xor x for all x and y
3. x xor (y xor z) == (x xor y) xor z (associativity)
4. x xor 0 == x for all x

Итак xor все числа. Результатом записи всех чисел будет ваш ответ. Я не знаю, как вы это сделаете в python, в языках C оператор xor равен ^.

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

Вы можете проверить, что: 3 ^ 4 ^ 7 ^ 4 ^ 3 == 7, 2 ^ 10 ^ 2 ^ 10 ^ 5 == 5 и т. Д.

Answer 2

Моя машина медленнее вашей - ваш код (вставленный в функцию main) занял 19 секунд на моей машине. Очевидная оптимизация удаления ненужного внутреннего for сокращает это до 0,46 секунды; изменяя сердце кода на

      alone = 0
      for c in codes: alone ^= c

сокращает время до 0,08 секунды. Я уверен, что дальнейшая оптимизация возможна, но с кодом, который уже в 235 раз быстрее, я думаю, этого может быть достаточно;

Answer 3

Учтите это:

codes = map(int, lines[i+1].split(' '))

Зачем заново делить строку для каждого значения guest? Линия не изменится.

Также учтите это:

for guest in range(G):
    codes = map(int, lines[i+1].split(' '))
    alone = (c for c in codes if codes.count(c)==1)

Ни один из кодов в этом цикле не зависит от guest. Почему это в цикле?

Answer 4

Да, как объясняет страница анализа, вы можете использовать постоянную память, хотя любой подход будет выполняться за O (n) времени. Вот как будет работать решение с постоянной памятью в Python:

numbers = [1, 1, 2, 2, 3, 3, 4, 4, 12345]
missingOne = 0
for number in numbers:
    missingOne = missingOne ^ number
assert missingOne == 12345

Ключ к пониманию того, что делает оператор xor. Любое число, записанное с нулем, само по себе. И любое число xor'ed с самим собой равно нулю. Если вы посмотрите на таблицу истинности для xor, вы сможете убедить себя в обоих этих фактах, а затем доказать, что при сохранении чисел в списке, начиная с нуля, будет получено не дублированное число.

Answer 5

Это заканчивается мгновенно для меня с теми же результатами:

src = open('A-large-practice.in')
dst = open('A-large-practice.out', 'w')

n = int(src.readline().rstrip())
for i in xrange(n):
    src.readline() # skip g
    nums = src.readline().split()
    seen = set()
    for n in nums:
        if n in seen:
            seen.remove(n)
        else:
            seen.add(n)
    dst.write("Case #%d: %s\n" % (i+1, tuple(seen)[0]))

src.close()
dst.close()

Блин, я люблю хеш-карты!