StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>Current version:</h2> <p>(Fastest at the time of posting with Python 2.6.4 on my machine.)</p> <p>Update 3: Since we're going all out, let's do a binary search -- in a way which doesn't require injecting <code>m</code> into <code>mems</code>:</p> <pre><code>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:]) </code></pre> <p>This runs in <strong>828 µs</strong> = 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).</p> <p>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 <code>m</code> into <code>mems</code> and sort the whole thing (like in the OP's current solution with <code>.index(m)</code>) 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.</p> <hr> <h2>Earlier attempts:</h2> <p>How about this? (Proposed solution next to <code>In [25]</code> below, 2.42 ms to zipij5's 3.13 ms.)</p> <pre><code>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 </code></pre> <p>Update: This appears to be just about exactly as fast as the OP's self-answer. Seems more straighforward, though.</p> <p>Update 2: An implementation of the OP's proposed simplified solution:</p> <pre><code>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 </code></pre> <p>Also, truppo's solution runs in 1.36 ms on my machine. I guess the above is the fastest so far. Note <strong>you need to sort <code>mems</code> before passing them into this function</strong>! If you're generating it with <code>range</code>, it is of course already sorted, though.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload