0

I have an algorithm encoutering the following situation; I would like to know if some improvement seems possible (I don't think it is possible, but I may be wrong).

I have a list L of objets. I have two different (and independant) keys for sorting them: mykey1 and mykey2. I can actually sort in both ways the list at the beginning of the algorithm with no significant cost; thus, I have two lists:

A = sorted(L, key=mykey1)
B = sorted(L, key=mykey2)

(Python syntax, but I think anybody can understand). I could perfectly do anything more (intialize new variables) at this stage as long as the complexity remains below O(n log n).

I need to extract many sublists of A; instead of actually copy the sublists, I would like to use indices (start and end) during the main loop of my algorithm for obvious reasons.

Now, for any arbitrary sublist of A (known by the two indices), is there some tricky way to iterate over its objects according the corresponding order (of the very same objects) in B?

Here is a quick and dirty example:

L = [(7,2), (4,3), (5,9), (1,8)]
mykey1 = lambda e: e[0]
mykey2 = lambda e: e[1]
A = sorted(L, key=mykey1) # A = [(1,8), (4,3), (5,9), (7,2)]
B = sorted(L, key=mykey2) # B = [(7,2), (4,3), (1,8), (5,9)]

when working on the sublist made of A[0:2] which is [(1,8), (4,3)], is there some tricky way to iterate over [(4,3), (1,8)] (since the object (4,3) comes before object (1,8) according to the key mykey2. I would like to avoid iterating over any other object than those actually belonging to A[0:2] for that purpose?

I can do it with complexity O(n) by iterating over the whole B and checking if the object is in the sublist (which is not difficult to achieve by adding some field to the object giving its position in A); can I do better?

2 Answers 2

0
I would suggest the next code snippet:

    L = [(7,2), (4,3), (5,9), (1,8)]
    mykey1 = lambda e: e[0]
    mykey2 = lambda e: e[1]
    A = sorted(L, key=mykey1)
    C = [sorted(_, key=mykey2) for _ in (A[0:_] for _ in (_ for _ in range(1, len(A) + 1)))]

C will be a list containing the sub-lists:
[[(1, 8)],
 [(4, 3), (1, 8)],
 [(4, 3), (1, 8), (5, 9)],
 [(7, 2), (4, 3), (1, 8), (5, 9)]]

Or, if we want to make C a [generator][1] (instead of a list); for lists we are keeping all elements in memory (performance issue) :

    C = (sorted(_, key=mykey2) for _ in (A[0:_] for _ in (_ for _ in range(1, len(A) + 1))))

Hope it helps.
1
  • This assumes he is only interested in sublists of A starting at the first item in A.
    – user4843530
    Jan 29, 2016 at 16:05
0

It has been a very long time since i used Python, but wouldn't something like this work?

C = sorted(A[0:2], key=mykey2)

then iterate over C after applying this "B" sort/key to the A sublist to generate it, or you could instead subtract the lists

C = B - A[2:2]

If your sublists can be generated incrementally, this could be a simple way to generate them, already in B sorted order. Rather than start from A sublists and try to iterate through them in B order, turn it around and start from B and generate the sublists by taking away items in A order.

Or am I missing something here. This seems too simple an answer.

4
  • Hummm, I think you will introduce O(n log n) complexity (though I have to check it since you sort a smaller list); I think the O(n) solution (iterating over B and checking if it belongs to the sublist) would be still better. I would like rather to pre-compute as many things as possible before entering the algorithm. Jan 29, 2016 at 15:46
  • How are you selecting out sublists? The trick might be in that operation. If you can start from B and extract A[4], you would have A[0:3] ordered in B order. If you take this further, you could incrementally generate your sublists by taking out the pieces that you don't want. just another idea.
    – user4843530
    Jan 29, 2016 at 15:58
  • I have to think about that; it may indeed help. I need a little time to figure it out. Jan 29, 2016 at 16:06
  • It is the only thing I can think of to take advantage of the fact that you already have B in the order you want the A sublists. Turn the problem around so that you are generating the sublists starting with B and taking out items in A order, rather than starting with A, generating the sublist and then trying to iterate/sort them in B order.
    – user4843530
    Jan 29, 2016 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.