python - 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) 处被复制。我说 of sorts 是因为我将利用 2.7 中新的 Counter() 对象来执行准矩阵-矩阵和矩阵-向量加法。然后我简单地向 counter_obj.update() 提供一个二元组列表，它会增加这些坐标出现的次数。令我沮丧的是，对于我的用例，SciPy 稀疏矩阵的运行速度慢了大约 50 倍......所以我很快就放弃了它们。

所以无论如何，我对我的结果感到惊讶......我想到的第一个方法是 zipij4 和 zipij5，但它们仍然是最快的，尽管构建一个普通的 zip()，然后在更改值后生成一个新的 zip。相对而言，我对 Python 还是比较陌生(Alex Martelli，你能听到我说话吗？)，所以这是我天真的结论:

• tuple(sorted([i, j])) 非常昂贵(为什么？)
• map(lambda ...) 似乎总是比 list comp 做得更差(我想我已经读过这个并且它是有道理的)
• 尽管遍历列表两次以检查 i-j 不等式，但 zipij5() 并没有慢多少。 (这是为什么？)

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

---

当前最佳解决方案

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

当前版本:

(在我的机器上使用 Python 2.6.4 发布时最快。)

更新 3:由于我们要全力以赴，所以让我们进行二进制搜索——以一种不需要将 m 注入(inject) 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 µs = 0.828 毫秒，而 OP 当前解决方案的运行时间为 1.14 毫秒。假定输入列表已排序(当然，测试用例是通常的)。

此二分搜索实现返回给定列表中第一个元素的索引，该索引不小于要搜索的对象。因此，无需将 m 注入(inject) mems 并对整个事物进行排序(就像在 OP 当前的 .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 的 self 回答一样快。不过，看起来更直接。

更新 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 生成它，那么它当然已经排序了。