Следующий алгоритм является самым чистым, который я могу придумать, который имеет разумную производительность. Я ожидаю, что с конкретным примером массива, который вы дали, этот код и тот, который вы дали выше, будут иметь одинаковые уровни производительности, но если вы начнете использовать большие массивы, вы увидите здесь прирост производительности по сравнению с вашим. Без набора тестовых случаев трудно сказать наверняка.
Так или иначе, общая идея выглядит следующим образом. Давайте назовем Partition отсортированный массив непересекающихся интервалов, который охватывает все целые числа от -Infinity до Infinity.
type Partition = Array<Interval>;
Если у нас есть значение partition типа Partition, мы знаем, что partition[0].start === -Infinity, partition[partition.length-1].end === Infinity и для любого индекса i < partition.length - 1, partition[i].end + 1 === partition[i+1].start.
Хорошая особенность раздела состоит в том, что он всегда будет содержать ровно один интервал, охватывающий любой данный position. Это исключает класс крайних случаев. Итак, учитывая partition: Partition и position: number, давайте найдем индекс интервала внутри partition, который его содержит:
// binary search of the partition to find the index of the interval containing position
// startIndex is a hint, where partition[startIndex].start <= position
// endIndex is a hint, where partition[startIndex].end > position
function findIndex(
partition: Partition,
position: number,
startIndex: number = 0,
endIndex: number = partition.length
) {
while (true) {
let i = (startIndex + endIndex) >> 1;
let cur = partition[i];
if (cur.end <= position) {
startIndex = i;
} else if (cur.start > position) {
endIndex = i;
} else {
return i;
}
}
}
Этот алгоритм является двоичным поиском, и он позволяет вам дать он намекает на начальный и конечный индексы, если вы уже знаете, где в разделе может быть правильный интервал. Если длина раздела равна ?, тогда этот алгоритм должен быть ? (??? ?).
Другая полезная операция - разделить partition на конкретный position. Если раздел уже содержит интервал, начинающийся с позиции, вам не нужно ничего делать. В противном случае вам нужно найти интервал, который охватывает позицию, и разделить его на две части:
// ensure that the partition contains an interval starting at position
// startIndex is a hint, where partition[startIndex].start <= position
// return the index of the interval starting at position
function splitAt(partition: Partition, position: number, startIndex: number = 0) {
let i = findIndex(partition, position, startIndex);
let cur = partition[i];
if (cur.start < position) {
partition.splice(i, 1,
{ start: cur.start, end: position - 1, type: cur.type.slice() },
{ start: position, end: cur.end, type: cur.type }
)
i++;
}
return i;
}
Этот алгоритм использует findIndex(), поэтому он также должен быть ? (??? ?). (редактировать ... Я думаю, это зависит от splice(), так что, возможно, это просто ? (?)).
Учитывая partition: Partition и interval: Interval, как мы можем объединить интервал в раздел? Нам нужно разделить секцию в интервале start и сразу после позиции интервала end, а затем пройти через затронутые интервалы и добавить к ним массив type нового интервала:
// merge interval into partition
function merge(partition: Partition, interval: Interval) {
// split partition at interval's start, get index of starting interval in partition
let startIndex = splitAt(partition, interval.start);
// split partition at interval's end, get index of interval after ending interval
let endIndex = splitAt(partition, interval.end + 1, startIndex);
// add types to each interval between start and end
for (let i = startIndex; i < endIndex; i++) {
partition[i].type.push(...interval.type);
}
}
Это пара бинарных поисков плюс обход затронутых интервалов. В худшем случае каждый интервал в разделе необходимо изменить, так что это будет ? (?).
Наконец, все, что нам нужно сделать, чтобы преобразовать произвольный массив интервалов в формат, который вы хотелось бы начать с пустого Partition (который имеет ровно один интервал от -Infinity до Infinity и с пустым массивом type), объединить каждый интервал с ним, а затем вернуть окончательный Partition без интервалов, чей массив type пуст . Это автоматически подавит те, которые касаются Infinity или -Infinity, а также любые отверстия в середине:
// denormalize array into non-overlapping intervals
function denormalize(arr: Array<Interval>) {
// empty partition
const partition: Partition = [{ start: -Infinity, end: Infinity, type: [] }];
arr.forEach(interval => merge(partition, interval));
// turn partition into normal array by removing "empty" intervals
return partition.filter(i => i.type.length !== 0);
}
Так как это работает merge() для каждого интервала, это в конечном итоге будет ? (?²) в худшем случае. Я думаю, что это лучшее, что вы можете сделать для алгоритма; это означает, что вам не нужно три вложенных цикла, но я был бы удивлен, если бы вы могли избежать двух.
Вы можете убедиться, что он выдает тот же вывод, что и ваша версия. Могут быть крайние случаи, но я более уверен в алгоритме, который работает на Partition с, так как мне не нужно постоянно спрашивать «что, если позиция, на которую я смотрю, не имеет интервала, связанного с ней» ?
Примечания:
Возможно, вы захотите, чтобы ваши интервалы были полуоткрыты, как в [start, end). То есть start должно быть наименьшей позицией, содержащейся в интервале, а end должно быть наименьшей позицией больше , чем интервал. Полуоткрытые интервалы гораздо проще составлять и рассуждать. Длина [start, end) составляет end - start. Если вы присоединитесь к интервалам [a, b) и [b, c), вы получите [a, c). Если вы когда-нибудь решите, что вам нужно перейти с целых чисел на дроби, полуоткрытый интервал не потребует никаких изменений кода. И наоборот, закрытые интервалы требуют тщательной математики для сложения или вычитания 1 (или любого другого размера шага) в нужных местах и, следовательно, подвержены ошибкам после ограждения.
Как я уже говорил, производительность часто важна, но не так важна, как правильность. Единственный способ точно узнать, насколько важна производительность в вашем случае, - это проверить ее на предмет нагрузки и посмотреть, как она оценивается. Довольно часто простой алгоритм предпочтительнее сложного, который немного быстрее, особенно если вам придется поддерживать и / или отлаживать код в будущем.
Хорошо, надеюсь, это поможет; удачи!
Детская площадка ссылка на код