Efficient reordering of coordinate pairs (2-tuples) in a list of pairs in Python

Question

I am wanting to zip up a list of entities with a new entity to generate a list of coordinates (2-tuples), but I want to assure that for (i, j) that i < j is always true.

However, I am not extremely pleased with my current solutions:

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]

Output for above:

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

Instead of normally:

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

Timings: snipped (no longer relevant, see much faster results in answers below)

For len(mems) == 5, there is no real issue with any solution, but for zipij5() for instance, the second list comprehension is needlessly going back over the first four values when i > j was already evaluated to be True for those in the first comprehension.

For my purposes, I'm positive that len(mems) will never exceed ~10000, if that helps form any answers for what solution is best. To explain my use case a bit (I find it interesting), I will be storing a sparse, upper-triangular, similarity matrix of sorts, and so I need the coordinate (i, j) to not be duplicated at (j, i). I say of sorts because I will be utilizing the new Counter() object in 2.7 to perform quasi matrix-matrix and matrix-vector addition. I then simply feed counter_obj.update() a list of 2-tuples and it increments those coordinates how many times they occur. SciPy sparse matrices ran about 50x slower, to my dismay, for my use cases... so I quickly ditched those.

So anyway, I was surprised by my results... The first methods I came up with were zipij4 and zipij5, and yet they are still the fastest, despite building a normal zip() and then generating a new zip after changing the values. I'm still rather new to Python, relatively speaking (Alex Martelli, can you hear me?), so here are my naive conclusions:

• tuple(sorted([i, j])) is extremely expensive (Why is that?)
• map(lambda ...) seems to always do worse than a list comp (I think I've read this and it makes sense)
• Somehow zipij5() isn't much slower despite going over the list twice to check for i-j inequality. (Why is this?)

And lastly, I would like to know which is considered most efficient... or if there are any other fast and memory-inexpensive ways that I haven't yet thought of. Thank you.

---

Current Best Solutions

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

Timings

# 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

Timings were using mems = range(1, 10000, 2), which is only ~5000 in length. sorted() will probably become worse at higher values, and with lists that are more shuffled. random.shuffle() was used for the "Unsorted" timings.

Answer 1

Most recent version:

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

Benches slightly faster for me than truppo's, slower by 30% than Michal's. (Looking into that now)

---

I may have found my answer (for now). It seems I forgot about making a list comp version for `zipij()``:

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

It still relies on my silly ij() helper function, so it doesn't win the award for brevity, certainly, but timings have improved:

# 10000
1.27s
# 50000
6.74s

So it is now my current "winner", and also does not need to generate more than one list, or use a lot of function calls, other than the ij() helper, so I believe it would also be the most efficient.

However, I think this could still be improved... I think that making N ij() function calls (where N is the length of the resultant list) is not needed:

• Find at what index mem would fit into mems when ordered
• Split mems at that index into two parts
• Do zip(part1, repeat(mem))
• Add zip(repeat(mem), part2) to it

It'd basically be an improvement on zipij4(), and this avoids N extra function calls, but I am not sure of the speed/memory benefits over the cost of brevity. I will maybe add that version to this answer if I figure it out.

Answer 2

Current version:

(Fastest at the time of posting with Python 2.6.4 on my machine.)

Update 3: Since we're going all out, let's do a binary search -- in a way which doesn't require injecting m into 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:])

This runs in 828 µs = 0.828 ms on my machine vs the OP's current solution's 1.14 ms. Input list assumed sorted (and the test case is the usual one, of course).

This binary search implementation returns the index of the first element in the given list which is not smaller than the object being searched for. Thus there's no need to inject m into mems and sort the whole thing (like in the OP's current solution with .index(m)) or walk through the beginning of the list step by step (like I did previously) to find the offset at which it should be divided.

---

Earlier attempts:

How about this? (Proposed solution next to In [25] below, 2.42 ms to zipij5's 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

Update: This appears to be just about exactly as fast as the OP's self-answer. Seems more straighforward, though.

Update 2: An implementation of the OP's proposed simplified solution:

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

Also, truppo's solution runs in 1.36 ms on my machine. I guess the above is the fastest so far. Note you need to sort mems before passing them into this function! If you're generating it with range, it is of course already sorted, though.

Answer 3

Why not just inline your ij()-function?

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

(This runs in 0.64 ms instead of 2.12 ms on my computer)

Some benchmarks:

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]

Sorted:

>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

Unsorted:

>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