更有效地分割重叠间隔,然后合并重复项 [英] More Efficient method to split overlapped intervals, then merge duplicates
问题描述
所以我正在尝试找出最有效的方法来拆分重叠的间隔,然后合并重复项。特定于我的情况的两个条件是,如果合并间隔的开始是原始间隔的结束,则加1。如果合并间隔的结束是原始间隔的开始,则减1。以下是一些样本数据和预期结果:
interface Interval {
start: number;
end: number;
type: Array<number>;
}
// starting data
const arr: Array<Interval> = [
{ start: 0, end: 16, type: [42] },
{ start: 6, end: 30, type: [95] },
{ start: 11, end: 24, type: [126] },
{ start: 32, end: 47, type: [42] }
].sort((a, b) => a.start - b.start);
// magic splitting code here
// what we expect to end up with
const end_arr: Array<Interval> = [
{ start: 0, end: 5, type: [42] },
{ start: 6, end: 10, type: [42, 95] },
{ start: 11, end: 16, type: [42, 95, 126] },
{ start: 17, end: 24, type: [95, 126] },
{ start: 25, end: 30, type: [95] },
{ start: 32, end: 47, type: [42] },
];
从技术上讲,我已经得到了这个问题的答案,但它的效率不是很高--涉及3个嵌套的for/forEach循环。当然还有更有效的办法吗?这是它的代码:
let startIndexArray: Array<number> = [];
let endIndexArray: Array<number> = [];
for (let i = 0; i < arr.length; i++) {
startIndexArray.push(arr[i].start);
endIndexArray.push(arr[i].end);
}
startIndexArray = startIndexArray.sort((a, b) => a - b);
endIndexArray = endIndexArray.sort((a, b) => a - b);
const indexArray = [...startIndexArray, ...endIndexArray].sort((a, b) => a - b);
const result: Array<Interval> = [];
arr.forEach((currentInterval) => {
for (let i = currentInterval.start; i < currentInterval.end; i++) {
if (indexArray.includes(i)) {
const position = indexArray.indexOf(i);
if (position !== indexArray.length - 1) {
let start = i;
let next = indexArray[position + 1];
if (endIndexArray.includes(start)) {
start = start + 1;
}
if (startIndexArray.includes(next)) {
next = next - 1;
}
let in_result = false;
result.forEach((mergedInterval) => {
if (mergedInterval.start === start && mergedInterval.end === next) {
mergedInterval.type = [...mergedInterval.type, ...currentInterval.type];
in_result = true;
}
});
if (!in_result) {
result.push({ start: start, end: next, type: [...currentInterval.type]});
}
}
}
}
});
// output is my expected, correct outcome
console.log(result);
推荐答案
以下算法是我所能想到的最干净的算法,具有合理的性能。我预计,对于您给出的特定示例数组,此代码和您上面给出的代码将具有相似的性能水平,但如果您开始使用更大的数组,您将在这里看到与您的相比的性能提升。如果没有一套测试用例,就很难确定。
不管怎样,大意是这样的。让我们调用一个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;
}
}
}
此算法是二进制搜索,如果您碰巧已经知道正确的间隔可能在分区中的什么位置,则它允许您向它提供有关开始和结束索引的提示。如果分区的长度为𝑛,则此算法应为𝖮(𝗅𝗈𝗀𝑛)。
另一个有用的操作是在特定的
position
处拆分partition
。如果分区已经包含从该位置开始的间隔,则无需执行任何操作。否则,您需要找到跨越该位置的间隔,并将其一分为二:
// 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
(或不管步长是多少),因此很容易出现栅栏柱错误。正如我前面所说,性能通常很重要,但它可能不如正确性那么重要。要确切知道性能对您的情况有多重要,唯一的方法是针对负载进行测试,并看看它的表现如何。通常,简单的算法比速度更快的复杂算法更可取,特别是如果您必须在将来维护和/或调试代码。
好的,希望这会有帮助;祝你好运!
这篇关于更有效地分割重叠间隔,然后合并重复项的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!