如何在多个排序列表中检索第N个项目，就好像有一个完整的排序列表一样

Question

我正在处理一个分片问题。

• 想象一下我有10个列表
• 每个列表都有一系列独立排序的项目
• 我想得到第N个项目，就好像所有列表都在一个大列表中排序一样

我需要对列表进行整体排序以获得特定索引中的项目吗？

我解决了一个类似但不等价的问题：

• 10个列表
• 每个列表表示上一个列表之后的一系列项目

以下是迭代列表所有索引的代码：

/* code to iterate through all items in order
* threads refers to one of the lists */
int sizes[] = new int[threads.size()];
for (int i = 0 ; i < threads.size(); i++) {
sizes[i] = threads.get(i).data2.size();
}
int n = 0;
int thread = 0;
int size = threads.size();
int offset = 0;
long iterationStart = System.nanoTime();
while (thread < size) {
// System.out.println(String.format("%d %d", thread, offset + threads.get(thread).data.get(n)));
int current = offset + threads.get(thread).data.get(n);
n = n + 1;
if (n == sizes[thread]) {
offset += sizes[thread];
thread++;
n = 0;
}
}
long iterationEnd = System.nanoTime();
long iterationTime = iterationEnd - iterationStart;

以下是按索引查找项目的代码。

int lookupKey = 329131;
int current = lookupKey;
int currentThread = 0;
int total = 0;
while (current >= 0 && currentThread <= size - 1) {
int next = current - sizes[currentThread];
if (next >= 0) {
total += sizes[currentThread];
current -= sizes[currentThread];
currentThread++;
} else {
break;
}
}
long lookupEnd = System.nanoTime();
long lookupTime = lookupEnd - lookupStart;
System.out.println(String.format("%d %d",
currentThread,
total + threads.get(currentThread).data.get(current)));

我希望有一些排序集合的属性，我可以用来检索整个排序列表中的第N个项目。

实际上，我有多个偏序。

我还有一些其他代码，可以在多个排序列表之间进行N向合并。在查找索引的循环中运行此项的最快选项是什么？

int size1 = threads.size();
int[] positions = new int[size1];
Arrays.fill(positions, 0);
PriorityQueue<Tuple> pq = new PriorityQueue<>(new Comparator<Tuple>() {
@Override
public int compare(Tuple o1, Tuple o2) {
return o1.value.compareTo(o2.value);
}
});
long startOrderedIteration = System.nanoTime();
for (ShardedTotalRandomOrder thread : threads) {
for (int i = 0; i < 10; i++) {
//                System.out.println(thread.data2.get(i));
pq.add(thread.data2.get(i));
}
}
List<Integer> overall = new ArrayList<>();
while (!pq.isEmpty()) {
Tuple poll = pq.poll();
ArrayList<Tuple> data2 = threads.get(poll.thread).data2;
if (positions[poll.thread] < data2.size()) {
Tuple nextValue = data2.get(positions[poll.thread]++);
pq.offer(nextValue);
}
overall.add(poll.value);
// System.out.println(String.format("%d %d", poll.thread, poll.value));
}
System.out.println(overall);
long endOrderedIteration = System.nanoTime();
long orderedIterationTime = endOrderedIteration - startOrderedIteration;

Answer 1

您不需要使用它们。由于每个列表都已排序，因此可以按如下方式合并它们。这使用一种方法根据两个列表的相对值合并两个列表。然后，它返回该列表并将其反馈到方法中，以便将其与下一个列表合并。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Merging {
public static void main(String[] args) {
List<Integer> list1 = List.of(5,10,15,20,25,30,35,40,45,50);
List<Integer> list2 = List.of(2,4,6,8,10);
List<Integer> list3 = List.of(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);


int nth = 10;
List<List<Integer>> lists = List.of(list1,list2,list3);
List<Integer> merged = lists.get(0);
for (int i = 1; i < lists.size(); i++) {
merged = mergeLists(merged, lists.get(i));
}
System.out.println(merged.get(nth));
}

打印

7

• 这适用于实现Comparable接口的任何类型
• 它将循环，直到一个列表用完，或者直到两个索引都超过组合列表大小
• 一旦其中一个列表完成，就可以通过子列表附加另一个列表

public static <T extends Comparable<? super T>> List<T> mergeLists(List<T> list1, List<T> list2) {
List<T> merged = new ArrayList<>();
int i1 = 0;
int i2 = 0;
while (i1 + i2 < list1.size() + list2.size()) {
if (i1 >= list1.size()) {
merged.addAll(list2.subList(i2,list2.size()));
break;
}
if (i2 >= list2.size()) {
merged.addAll(list1.subList(i1,list1.size()));
break;
}
if(list1.get(i1).compareTo(list2.get(i2)) <= 0) {
merged.add(list1.get(i1++));
} else {
merged.add(list2.get(i2++));
}
}
return merged;
}
}

Answer 2

这里有一个相对高效的(相对于列表数量是线性的)算法，它利用了流的一些功能，但避免了完整的列表合并。

EDIT：为了解决数组长度检查、数组销毁和可读性等缺点，我改进了这个示例。为了更好地进行比较，我使用了与另一个答案相同的整数测试数据。

这个由(可能)不可变数组支持的虚拟队列不会发生变异或其他

public class VirtualQueue<T> {
private List<T> list;
private int index=0;
public VirtualQueue(List<T> list) { this.list = list; }
public boolean hasMore() { return index < list.size(); }
public T pop() { return list.get(index++); }
public T peek() { return list.get(index);}
}

(我怀疑有一种更简单的方法可以用标准集合做到这一点)

List<Integer> list1 = List.of(5,10,15,20,25,30,35,40,45,50);
List<Integer> list2 = List.of(2,4,6,8,10);
List<Integer> list3 = List.of(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);
List<VirtualQueue<Integer>> listList = List.of(
new VirtualQueue<>(list1),
new VirtualQueue<>(list2),
new VirtualQueue<>(list3));
int n=10;
var value = IntStream.range(0,n)
.mapToObj(i -> listList.stream()
.filter(VirtualQueue::hasMore)
.min(Comparator.comparing(l -> l.peek()))
.get().pop())
.skip(n-1).findFirst().get();
//value is now the nth item in a hypothetical merged list.

Answer 3

假设您有k排序的列表，并且您需要从聚合列表中获得n(但合并列表本身不需要)，那么这个问题可以在O(n*log k)时间内解决，并使用O(k)额外的空间。

注意：

• 如果下面的代码看起来涉及太多，下面是其背后的基本原理。该解决方案比直接比较每个列表中的元素更具性能，这些元素可以在这个和这个答案中观察到，其时间复杂性O(n*k)(与O(n*log k)相反)。适度的额外复杂性是以性能提升为代价的，请注意，它仍然是可维护的
• 如果您需要具体化合并的排序列表(下面的解决方案不是这样做的)，您可以简单地将列表组合在一起，并通过List.sort()使用内置的Timsort算法实现。Timsort非常善于发现排序的运行，因此对由排序块组成的列表进行排序将具有线性时间复杂性

为了在O(n*log k)时间内解决问题，我们可以维护一个大小始终为k或更小的PriorityQueue(因此入队/出队操作的成本为O(log k))。一开始，应该通过添加每个List中的第一个元素来初始化Queue。

然后我们需要执行n迭代(以找到目标元素)。在每个迭代步骤中，队列的Head元素都应该被移除，来自同一列表的下一个元素应该被添加到队列中(即，如果假设第三列表中的第七个元素看起来是队列的头，那么在移除它之后，我们需要将第三列表的第八个元素排队)。

为了能够跟踪每个元素来自哪个List，以及它在List中的索引是什么，我们可以定义一个自定义类型：

public class ElementWrapper<V extends Comparable<V>> implements Comparable<ElementWrapper<V>> {
private V value;
private int listIndex;
private int elementIndex;

// all-args constructor, getters

@Override
public int compareTo(ElementWrapper<V> o) {
return value.compareTo(o.getValue());
}
}

下面是如何实现这个用于查找第7个CCD_元素的算法。正如我所说，时间复杂性是O(n*log k)，因为我们需要n迭代步骤，每个步骤的成本都是O(log k)。仅维护k元素的Queue所需的额外内存。

public static <T extends Comparable<T>> T getNElement(List<List<T>> lists, int n) {
Queue<ElementWrapper<T>> queue = initializeWithFirstElements(lists);

T result = null;
int count = 1;

while (!queue.isEmpty()) {
ElementWrapper<T> current = queue.remove();

if (count == n) { // target index was reached
result = current.getValue();
break;
}
count++;

if (hasNext(current, lists)) {
addNext(current, lists, queue);
}
}
return result;
}
public static <T extends Comparable<T>> Queue<ElementWrapper<T>>
initializeWithFirstElements(List<List<T>> lists) {

Queue<ElementWrapper<T>> queue = new PriorityQueue<>();
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i).isEmpty()) continue;
queue.add(new ElementWrapper<>(lists.get(i).get(0), i, 0));
}
return queue;
}
public static <T extends Comparable<T>> boolean
hasNext(ElementWrapper<T> current, List<List<T>> lists) {

return current.getElementIndex() + 1 < lists.get(current.getListIndex()).size();
}
public static <T extends Comparable<T>> void
addNext(ElementWrapper<T> current, List<List<T>> lists,
Queue<ElementWrapper<T>> queue) {

ElementWrapper<T> next = new ElementWrapper<>(
lists.get(current.getListIndex()).get(current.getElementIndex() + 1),
current.getListIndex(),
current.getElementIndex() + 1
);
queue.add(next);
}

用法示例：

public static void main(String[] args) {
List<List<Integer>> input =
List.of(List.of(1, 3), List.of(),
List.of(2, 6, 7), List.of(10), List.of(4, 5, 8, 9)
);

System.out.println(getNElement(input, 1));
System.out.println(getNElement(input, 3));
System.out.println(getNElement(input, 9));
}

输出：

1    // 1st
3    // 3rd
9    // 9th

注意：根据您希望第n个元素的索引方式，getNElement()方法中的count变量应相应初始化，即如果您希望使用基于1的索引，则使用1；如果您希望n基于0，则使用0