Я видел здесь много вопросов о производительности Java lambdas, но большинство из них похоже на "Lambdas немного быстрее, но становятся медленнее при использовании закрытий" или "Разминка против времени выполнения отличается" или другое подобное вещи.
Однако, я нахожу здесь довольно странную вещь. Рассмотрим эту проблему LeetCode:
Учитывая набор неперекрывающихся интервалов, вставьте новый интервал в интервалы (при необходимости, слить).
Вы можете предположить, что интервалы были сначала отсортированы в соответствии с их время начала.
Проблема была сильно помечена, поэтому я предположил, что линейный подход не то, что они там хотят. Поэтому я решил придумать умный способ комбинировать двоичный поиск с изменениями в списке ввода. Теперь проблема не очень ясна в изменении входного списка - он говорит "вставить", хотя для подписи требуется вернуть ссылку на список, но на этот раз не обращайте внимания. Здесь полный код, но только первые несколько строк относятся к этому вопросу. Я оставил здесь все, чтобы кто-нибудь мог попробовать:
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
int start = Collections.binarySearch(intervals, newInterval,
(i1, i2) -> Integer.compare(i1.start, i2.start));
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
new Interval(newInterval.end, 0),
(i1, i2) -> Integer.compare(i1.start, i2.start));
if (end >= 0) {
end += skip; // back to original indexes
} else {
end -= skip; // ditto
}
int newStart = newInterval.start;
int headEnd;
if (-start - 2 >= 0) {
Interval prev = intervals.get(-start - 2);
if (prev.end < newInterval.start) {
// the new interval doesn't overlap the one before the insertion point
headEnd = -start - 1;
} else {
newStart = prev.start;
headEnd = -start - 2;
}
} else if (start >= 0) {
// merge the first interval
headEnd = start;
} else { // start == -1, insertion point = 0
headEnd = 0;
}
int newEnd = newInterval.end;
int tailStart;
if (-end - 2 >= 0) {
// merge the end with the previous interval
newEnd = Math.max(newEnd, intervals.get(-end - 2).end);
tailStart = -end - 1;
} else if (end >= 0) {
newEnd = intervals.get(end).end;
tailStart = end + 1;
} else { // end == -1, insertion point = 0
tailStart = 0;
}
intervals.subList(headEnd, tailStart).clear();
intervals.add(headEnd, new Interval(newStart, newEnd));
return intervals;
}
Это работало нормально и приняло его, но с временем выполнения 80 мс, тогда как большинство решений составляли 4-5 мс и около 18-19 мс. Когда я посмотрел на них, все они были линейными и очень примитивными. Не то, что можно было бы ожидать от проблемы с тегом "hard".
Но возникает вопрос: мое решение также линейно в худшем случае (потому что операции добавления/очистки являются линейным временем). Почему это медленнее? И затем я сделал это:
Comparator<Interval> comparator = new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
return Integer.compare(i1.start, i2.start);
}
};
int start = Collections.binarySearch(intervals, newInterval, comparator);
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
new Interval(newInterval.end, 0),
comparator);
От 80 мс до 4 мс! Что здесь происходит? К сожалению, я понятия не имею, какие тесты LeetCode запускаются или в какой среде, но все же, не в 20 раз слишком много?
