按两个不同键排序的列表的子列表

Question

我有一个算法包含以下情况；我想知道是否有可能有所改进（我认为不可能，但我可能错了）。

我有一个对象列表。我有两个不同的（独立的）键来对它们进行排序：mykey1和mykey2。实际上，我可以在算法开始时以两种方式对列表进行排序，而无需花费大量成本；因此，我有两份清单：

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

（Python语法，但我认为任何人都能理解）。在这个阶段，只要复杂性保持在O（nlogn）以下，我完全可以做更多的事情（初始化新变量）。

我需要提取A的许多子列表；由于明显的原因，我希望在算法的主循环中使用索引（开始和结束），而不是实际复制子列表。

现在，对于A的任意子列表（由两个索引知道），是否有一些棘手的方法可以根据B中相应的顺序（非常相同的对象）迭代其对象？

下面是一个简单的例子：

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

当处理由A[0:2]构成的子列表时，是否有一些棘手的方法来迭代[（4,3), (1,8)]（因为对象（4,3）在对象之前（1,8）根据键mykey2。为此，我想避免迭代任何其他对象，而不是那些实际属于A[0:2]的对象？

我可以通过迭代整个B并检查对象是否在子列表中（通过向对象添加一些字段来给出其在A中的位置，这并不难实现），来实现复杂度O（n）；我能做得更好吗？

Answer 1

自从我使用Python以来已经有很长一段时间了，但是像这样的东西不管用吗？

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

然后在将这个“B”排序/键应用于A子列表后，在C上迭代以生成它，或者您可以将列表减去

C = B - A[2:2]

如果您的子列表可以增量生成，那么这可能是一种生成它们的简单方法，已经按B排序。与其从一个子列表开始并尝试按B顺序遍历它们，不如将它转过来，从B开始，通过按顺序删除项目来生成子列表。

或者我在这里遗漏了什么。这个答案似乎太简单了。

Answer 2

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.