Python中针对这个Codejam问题的更快或更节省内存的解决方案

Question

我尝试解决这个Google Codejam Africa的问题（比赛已经结束，我只是为了提高我的编程技能而做的）。

问题描述：

你正在举办一个聚会，邀请了G位客人，但你发现客人的数量是奇数！在策划聚会时，你特意只邀请了情侣，并给每对情侣的邀请函上都标了一个独特的号码C。你想通过询问所有客人的邀请号码，找出那些单独来的客人。

输入内容：

第一行输入的是案例的数量N。接下来有N个测试案例。每个测试案例包含：

• 一行包含客人数量G的值。
• 一行包含G个整数，数字之间用空格分开。每个整数C表示一个客人的邀请代码。

对于每个测试案例，输出一行，格式为“Case #x: ”后面跟着那个单独来的客人的号码C。

限制条件：

• 1 ≤ N ≤ 50
• 0 < C ≤ 2147483647

小数据集

3 ≤ G < 100

大数据集

3 ≤ G < 1000

示例输入：

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。

编辑：

根据下面Alex Martelli和IVlad的建议，我现在有了这个解决方案，运行时间为0.079秒：

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

考虑一下这个：

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 2

我的电脑比你的慢——你的代码（放在一个main函数里）在我这台机器上运行了19秒。显而易见的优化是去掉那个没用的内层for循环，这样时间就缩短到0.46秒；如果把代码的核心部分改成

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

那么时间就能再缩短到0.08秒。我相信还可以进一步优化，但代码已经快了235倍，我觉得这样应该差不多了;-).

Answer 3

我对Python不太了解，但这个问题本身是个经典问题。给你 2K - 1 个数字，其中除了一个数字外，其他数字都出现了偶数次，你需要找出那个出现了奇数次的数字。

需要用到的公式：

1. x xor x == 0 对于所有的 x 都成立
2. x xor y == y xor x 对于所有的 x 和 y 都成立
3. x xor (y xor z) == (x xor y) xor z（结合律）
4. x xor 0 == x 对于所有的 x 都成立

所以你可以把所有的数字进行 异或运算。把所有数字进行异或运算的结果就是你的答案。我不知道在Python中怎么做，在C语言中，异或运算符是 ^。

这真的是最有效的方法，因为你只需要做一个简单的位运算，甚至不需要存储这些数字。

你可以验证一下： 3 ^ 4 ^ 7 ^ 4 ^ 3 == 7，2 ^ 10 ^ 2 ^ 10 ^ 5 == 5 等等。