Python中对对列表中坐标对(2-元组)的有效重新排序

Question

我希望拉出一个具有新实体的实体列表，以生成一个坐标列表(2元组)，但我要保证，对于(i，j)，i

然而，我对我目前的解决办法并不十分满意：

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()提供一个2元组的列表，它会增加这些坐标发生的次数。对于我的用例，SciPy稀疏矩阵的运行速度慢了50倍，这让我感到沮丧.所以我很快就扔掉了。

所以不管怎么说，我对我的结果感到惊讶.我提出的第一个方法是zipij4和zipij5，但是它们仍然是最快的，尽管构建了一个普通的zip()，然后在更改值之后生成了一个新的压缩。相对而言，我对Python还很陌生(Alex Martelli，你能听到我说话吗？)，下面是我天真的结论：

• tuple(sorted([i, j]))是非常昂贵的(为什么that?)
• map(lambda ...)似乎总是比列表comp更糟糕(我想我已经读过这篇文章了，并且它使sense)
• Somehow zipij5()并不会慢很多，尽管检查列表两次以检查isn不等式)。(为什么？)

最后，我想知道哪一个是最有效的.或者我还没有想到任何其他快速和廉价的方法。谢谢。

当前最佳解决方案

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

为什么不直接内联您的ij()-function呢？

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

(这是0.64 ms，而不是我的计算机上的2.12 ms )

一些基准：

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

Answer 2

现行版本：

(在我的计算机上使用Python2.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 s= 0.828 ms中，而OP的当前解决方案是1.14ms。假设输入列表已排序(当然，测试用例是通常的)。

此二进制搜索实现返回给定列表中第一个元素的索引，该索引不小于要搜索的对象。因此，不需要将m注入mems并对整个事情进行排序(就像OP的当前解决方案中使用.index(m))，也不需要一步一步地遍历列表的开头(就像我以前做的那样)来找到应该分割它的偏移量。

先前的尝试：

这个怎么样？(建议的解决方案在下面的In [25]旁边，从zipij5 5的3.13ms到2.42ms。)

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:实施任择议定书提议的简化解决方案：

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

最新版本：

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):])

长椅对我来说比特鲁波的稍快一些，比米哈尔的要慢30%。

我可能已经找到了我的答案(暂时)。我好像忘了为` `zipij()制作一个list comp版本

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是结果列表的长度)：

当ordered

• Split mems将zip(part1, repeat(mem))

• Add mems分为两部分时，
• 找出mem适合于mems的指数，
• Do
• zip(repeat(mem), part2) to it

这基本上是对zipij4()的一个改进，这避免了N个额外的函数调用，但我不确定速度/内存是否比简洁的代价更好。如果我想出答案的话，我可能会把这个版本加到这个答案上。