在Python中高效重排坐标对（2元组）列表中的元素

Question

我想把一组实体和一个新实体组合起来，生成一系列坐标（成对的数字），但我想确保对于每一对 (i, j)，总是有 i < j 的关系。

不过，我对我现在的解决方案不是很满意：

from itertools import repeat

mems = range(1, 10, 2) 
mem = 8

def ij(i, j):
  if i < j:
    return (i, j)
  else:
    return (j, i)

def zipij(m=mem, ms=mems, f=ij):
  return map(lambda i: f(i, m), ms)

def zipij2(m=mem, ms=mems):
  return map(lambda i: tuple(sorted([i, m])), ms)

def zipij3(m=mem, ms=mems):
  return [tuple(sorted([i, m])) for i in ms]

def zipij4(m=mem, ms=mems):
  mems = zip(ms, repeat(m))
  half1 = [(i, j) for i, j in mems if i < j]
  half2 = [(j, i) for i, j in mems[len(half1):]]

  return half1 + half2

def zipij5(m=mem, ms=mems):
  mems = zip(ms, repeat(m))
  return [(i, j) for i, j in mems if i < j] + [(j, i) for i, j in mems if i > j]

上面的输出结果：

>>> print zipij() # or zipij{2-5}  
[(1, 8), (3, 8), (5, 8), (7, 8), (8, 9)]

而不是通常的：

>>> print zip(mems, repeat(mem))
[(1, 8), (3, 8), (5, 8), (7, 8), (9, 8)]

时间记录：省略（不再相关，下面的答案中有更快的结果）

对于 len(mems) == 5 的情况，任何解决方案都没有什么大问题，但比如说 zipij5() 的第二个列表推导式在 i > j 的情况下，还是多次检查了前四个值，而这些在第一个推导式中已经被判断为 True 了。

就我而言，我可以确定 len(mems) 不会超过大约 10000，如果这对找到最佳解决方案有帮助的话。为了稍微解释一下我的使用场景（我觉得很有趣），我会存储一个稀疏的、上三角的相似度矩阵，所以我需要坐标 (i, j) 不会在 (j, i) 中重复。我说是“相似度矩阵”是因为我会在 2.7 中使用新的 Counter() 对象来进行类似矩阵与矩阵、矩阵与向量的加法。然后我只需将 counter_obj.update() 传入一个二元组的列表，它就会统计这些坐标出现的次数。对于我的使用场景，SciPy 的稀疏矩阵慢了大约 50 倍，这让我很失望……所以我很快就放弃了它们。

总之，我对我的结果感到惊讶……我最初想到的方法是 zipij4 和 zipij5，尽管它们是通过构建一个普通的 zip() 然后再生成一个新的 zip 来改变值，但它们仍然是最快的。我相对来说还是比较新手（Alex Martelli，你能听到我吗？），所以这是我一些幼稚的结论：

• tuple(sorted([i, j])) 的开销非常大（这是为什么呢？）
• map(lambda ...) 的表现似乎总是比列表推导式差（我想我读过这个，确实有道理）
• 奇怪的是，尽管 zipij5() 要检查两次 i-j 的不等式，但它的速度并没有慢很多。（这是为什么呢？）

最后，我想知道哪种方法被认为是最有效的……或者是否还有其他快速且占用内存少的方法是我还没想到的。谢谢。

---

当前最佳解决方案

## Most BRIEF, Quickest with UNSORTED input list:
## truppo's
def zipij9(m=mem, ms=mems):
  return [(i, m) if i < m else (m, i) for i in ms]

## Quickest with pre-SORTED input list:
## Michal's
def zipij10(m=mem, ms=mems):
  i = binsearch(m, ms)  ## See Michal's answer for binsearch()
  return zip(ms[:i], repeat(m)) + zip(repeat(m), ms[i:])

时间记录

# Michal's  
Presorted - 410µs per loop
Unsorted - 2.09ms per loop  ## Due solely to the expensive sorted()

# truppo's
Presorted - 880µs per loop
Unsorted - 896µs per loop  ## No sorted() needed

时间记录是使用 mems = range(1, 10000, 2)，这只有大约 5000 的长度。sorted() 在更高的值和更乱的列表中可能会变得更慢。random.shuffle() 被用来进行“未排序”的时间记录。

Answer 1

最新版本：

def zipij7(m=mem, ms=mems):
  cpy = sorted(ms + [m])
  loc = cpy.index(m)

  return zip(ms[:(loc)], repeat(m)) + zip(repeat(m), ms[(loc):])

对我来说，这个版本的速度比truppo的稍快，但比Michal的慢了30%。（我现在正在调查这个问题）

---

我可能找到了我的答案（暂时）。看起来我忘记为`zipij()`做一个列表推导版本了：

def zipij1(m=mem, ms=mems, f=ij):
  return [f(i, m) for i in ms]

它仍然依赖于我那个傻乎乎的ij()辅助函数，所以在简洁性上并不算优秀，但运行时间有所改善：

# 10000
1.27s
# 50000
6.74s

所以现在这是我当前的“赢家”，而且它不需要生成多个列表，也不需要很多函数调用，除了ij()这个辅助函数，所以我认为它也是最有效率的。

不过，我觉得这还是可以进一步改进……我认为进行N次ij()函数调用（N是结果列表的长度）其实是不必要的：

• 找出mem在有序的mems中适合插入的位置索引
• 在那个索引处将mems分成两部分
• 做zip(part1, repeat(mem))
• 再把zip(repeat(mem), part2)加上去

这基本上是对zipij4()的改进，这样可以避免N次额外的函数调用，但我不确定在简洁性和速度/内存的好处之间的权衡。我可能会在搞清楚后把这个版本加到这个回答里。

Answer 2

当前版本：

（在我这台机器上，使用 Python 2.6.4 时，这是最快的。）

更新 3：既然我们要全力以赴，那就来做一个二分查找——以一种不需要把 m 放进 mems 的方式：

def binsearch(x, lst):
    low, high = -1, len(lst)
    while low < high:                                                           
        i = (high - low) // 2
        if i > 0:
            i += low
            if lst[i] < x:
                low = i
            else:
                high = i
        else:
            i = high
            high = low
    return i

def zipij(m=mem, ms=mems):
    i = binsearch(m, ms)
    return zip(ms[:i], repeat(m)) + zip(repeat(m), ms[i:])

在我这台机器上，这段代码运行时间为828 微秒 = 0.828 毫秒，而 OP 当前的解决方案是 1.14 毫秒。假设输入列表是已经排好序的（当然测试用例也是常见的那种）。

这个二分查找的实现会返回给定列表中第一个不小于要查找对象的元素的索引。因此，不需要像 OP 当前的解决方案那样把 m 放进 mems 并对整个列表进行排序（就像使用 .index(m) 的那种），也不需要像我之前那样一步一步地遍历列表的开头来找到应该分割的位置。

---

早期尝试：

这个怎么样？（在下面 In [25] 旁边提出的解决方案，运行时间为 2.42 毫秒，比 zipij5 的 3.13 毫秒快。）

In [24]: timeit zipij5(m = mem, ms = mems)
100 loops, best of 3: 3.13 ms per loop

In [25]: timeit [(i, j) if i < j else (j, i) for (i, j) in zip(mems, repeat(mem))]
100 loops, best of 3: 2.42 ms per loop

In [27]: [(i, j) if i < j else (j, i) for (i, j) in zip(mems, repeat(mem))] == zipij5(m=mem, ms=mems)
Out[27]: True

更新：看起来这个方案的速度几乎和 OP 自己的答案一样快。不过似乎更简单明了。

更新 2：这是 OP 提出的简化方案的实现：

def zipij(m=mem, ms=mems):
    split_at = 0
    for item in ms:
        if item < m:
            split_at += 1
        else:
            break
    return [(item, m) for item in mems[:split_at]] + [(m, item) for item in mems[split_at:]]

In [54]: timeit zipij()
1000 loops, best of 3: 1.15 ms per loop

另外，truppo 的方案在我这台机器上运行时间为 1.36 毫秒。我想上面的方案是目前为止最快的。请注意在将 mems 传入这个函数之前，你需要先对它进行排序！不过如果你是用 range 生成的，那它当然已经排好序了。

Answer 3

为什么不直接把你的 ij() 函数写在代码里呢？

def zipij(m=mem, ms=mems):
  return [(i, m) if i < m else (m, i) for i in ms]

（在我的电脑上，这样运行的时间是0.64毫秒，而不是2.12毫秒）

一些性能测试：

zipit.py：

from itertools import repeat

mems = range(1, 50000, 2)
mem = 8

def zipij7(m=mem, ms=mems):
  cpy = sorted(ms + [m])
  loc = cpy.index(m)

  return zip(ms[:(loc)], repeat(m)) + zip(repeat(m), ms[(loc):])

def zipinline(m=mem, ms=mems):
  return [(i, m) if i < m else (m, i) for i in ms]

已排序：

>python -m timeit -s "import zipit" "zipit.zipinline()"
100 loops, best of 3: 4.44 msec per loop

>python -m timeit -s "import zipit" "zipit.zipij7()"
100 loops, best of 3: 4.8 msec per loop

未排序：

>python -m timeit -s "import zipit, random; random.shuffle(zipit.mems)" "zipit.zipinline()"
100 loops, best of 3: 4.65 msec per loop

p>python -m timeit -s "import zipit, random; random.shuffle(zipit.mems)" "zipit.zipij7()"
100 loops, best of 3: 17.1 msec per loop