代码之家 › 专栏 › 技术社区 › user136565

在python的成对列表中高效地重新排序坐标对(2个元组)

tuples sorting python

user136565 · 技术社区 · 16 年前

我想用一个新的实体压缩一个实体列表,以生成一个坐标列表(2元组),但我想保证对于(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 i > j True

len(mems) (i, j) (j, i) Counter() counter_obj.update()

zipij4 zipij5 zip()

tuple(sorted([i, j]))
map(lambda ...)
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) sorted() random.shuffle()

3 回复 | 直到 16 年前

mthurlin 16 年前

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

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

MichaÅ Marczyk 16 年前

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

对整个问题进行排序(就像在OP当前的解决方案中 .index(m) )或者一步一步地浏览列表的开头(就像我以前做的那样),以找到应该划分的偏移量。

早期尝试:

这个怎么样?(旁边的建议解决方案 In [25] 以下,2.42 ms到Zipij5的3.13 ms。)

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毫秒。我想以上是目前为止最快的。注释 你需要分类 微机电系统 在将它们传递到此函数之前 !如果你用 range 当然,它已经排序了。

user136565 16 年前

最新版本:

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()'制作列表组件版本:

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 当订购时
将索引处的MEM分为两部分
做 zip(part1, repeat(mem))
添加 zip(repeat(mem), part2) 对它

这基本上是对 zipij4() 这样就避免了N个额外的函数调用,但是我不确定速度/内存比简洁性的成本有什么好处。如果我想出来的话,我可能会在这个答案中加上这个版本。