我有一个需要大量添加/删除的对象列表。我希望列表根据某个函数进行排序。
现在,每次添加新对象时,我都会:
list.add(obj1);
Collections.sort(list1, comparator);
删除对象不会“取消排序”列表,因此我只需要为添加操作执行此操作。
但是,Collections.sort
的时间复杂度为 O(>N),速度不是很快。
java中是否有任何结构可以让我从一开始就保留一个排序列表?
忘了提及
我尝试使用TreeSet
。它允许我传递一个比较器,该比较器将用于排序,但也将用于删除不是我想要的元素。我希望对其进行排序,但删除功能与列表相同。
最佳答案
如Alencar建议使用 Collections.binarySearch(yourList, key, comparator)
来查找正确的插入位置。这比查找整个列表要快得多,因为 binarySearch只需要log2(列表大小)查询即可找到正确的插入位置。
所以,如果您的插入代码是
void sortedInsert(List<T> list, T value, Comparator<T> comparator) {
int pos=0;
ListIterator<T> it=list.listIterator();
while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;
if (pos < it.previousIndex()) it.previous();
it.add(value);
}
...更快的版本是...
void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {
int pos = Collections.binarySearch(list, value, comparator);
if (pos < 0) {
pos = -pos -1; // returns negatives if not found; see javadoc
}
list.insert(value, pos);
}
请注意,差异可能不会那么大,因为插入非链接列表需要向上移动元素。因此,如果底层列表是 ArrayList,则平均将一半元素复制到右侧一个位置来为新元素腾出位置,会产生额外的 O(n)
复杂度每个副本的时间。如果列表是链接的,您仍然需要支付 O(n)
惩罚,但这次要执行二分搜索 - 在这种情况下,使用第一个版本可能会更好。
请注意,第一个版本使用 ListIterator
以防万一您决定使用链接列表。对于 ArrayLists,使用 list.get(pos) 和 list.add(pos, value) 会更容易,但这些是在迭代链表的上下文中这是一个非常糟糕的主意。
关于java - 从头开始对列表进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53285273/