Algorithm to calculate 'initial lists' in O(m*log m)

Question

Goal is to write an algorithm that calculates 'initial lists' (a data-structure) in a complexity class better than O(m^2)

What are initial list?

Let U be a set of tuples (for example {(2,5), (5,1), (9,0), (6,4)} ).

Step 1:

L1 is ordered by the first element of the tuple:

L1 = [ (2,5), (5,1), (6,4), (9,0) ]

and L2 by the second:

L2 = [ (9,0), (5,1), (6,4), (2,5) ]

Step 2:

Add the indices of tuple e in the second list to the tuple e in the first list:

L1 = [ (2,5,3), (5,1,1), (6,4,2), (9,0,0) ]

and the other way:

L2 = [ (9,0,3), (5,1,1), (6,4,2), (2,5,0) ]

L1 and L2 are called the initial lists of U now.

---

The first implementation idea of course is an exhaustive algorithm in O(m^2)

U = {(2,5), (5,1), (9,0), (6,4)}

m = len(U)

#step 1:
L1 = [e for e in U]
L1.sort()
L2 = [e for e in U]
L2.sort(key=lambda tup: tup[1])

#step 2:
help = []*len(L1)
for i in range(len(L1)):
    help[i] = L1[i][0], L1[i][1], L2.index(L1[i])

for i in range(len(L2)):
    L2[i] = L2[i][0], L2[i][1], L1.index(L2[i])

L1 = help

# >>> L1
# [(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]
# >>> L2
# [(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]

So this works. But calling index ( O(m) ) in a for-loop ( O(m) ) makes its complexity quadratic. But how to write an algorithm for that in O(m*log m)?

Answer 1

I see room for some optimisation here.

• Sort twice as before, but create two dictionaries for looking up the index (this is linear in time).
• You can also use operator.itemgetter to remove the lambdas.
• You also can junk the copy calls, they're not needed when you call sorted anyway, because sorted returns a copy of your data.

from operator import itemgetter
ip = {(2,5), (5,1), (9,0), (6,4)}

# step 1 - sort `ip` and create L1
L1 = sorted(ip)
# step 2 - create index lookup for L2
idx_L1 = {k : v for v, k in enumerate(L1)}

# step 3, 4 - repeat for L2
L2 = sorted(ip, key=itemgetter(1))
idx_L2 = {k : v for v, k in enumerate(L2)}

# step 5 - augment L1 and L2 with respective indexes from other lists
L1 = [(*x, idx_L2[x]) for x in L1]   # starred unpacking - python3.6+ syntax
L2 = [(*x, idx_L1[x]) for x in L2]   # use `x + (idx_L2[x],)` for older versions

>>> L1
[(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]    
>>> L2
[(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]