ベタな実装
数値配列の部分範囲内の最大値は以下のように検索できます。
function findMax(nums, start, end, minValue = -Infinity) {
let maxValue = minValue;
for (let i = start; i < end; i++) {
maxValue = Math.max(maxValue, nums[i]);
}
return maxValue;
}
ただしこの方法では、一度の検索が線形時間であるため、数万要素数ある配列の場合、何度も範囲を変えながら最大値を求めるような場合には、とても大きな時間がかかってしまいます(繰り返したときの計算量はO(N^2))。
二分木による実装
そこで、これを回避するには、最大値を収めた二分木を一度作成することによって、対数時間で検索できるようになります(繰り返したときの計算量はO(NlogN))。
function createMaxTree(nums, start = 0, end = nums.length) {
const length = end - start;
if (length === 1) return {max: nums[start], start, end};
const mid = start + (length >> 1);
const left = createMaxTree(nums, start, mid);
const right = createMaxTree(nums, mid, end);
// [start, end)範囲での最大値がmax
return {max: Math.max(left.max, right.max), start, end, left, right};
}
function findMax(tree, start, end, minValue = -Infinity) {
if (end <= tree.start || tree.end <= start) return minValue; // ノードの範囲が完全に範囲外
if (start <= tree.start && tree.end <= end) return tree.max; // ノードの範囲が完全に範囲内
// 部分的に範囲内
const left = findMax(tree.left, start, end, minValue);
const right = findMax(tree.right, start, end, minValue);
return Math.max(left, right);
}
// 値の更新
function updateMax(tree, i, value) {
if (i < tree.start || tree.end <= i) return tree.max; // iが完全に範囲外
const length = tree.end - tree.start;
if (length === 1) return tree.max = value;
const left = updateMax(tree.left, i, value);
const right = updateMax(tree.right, i, value);
return tree.max = Math.max(left, right);
}
これは"Segment Tree"の非配列での実装例となるようです。
ほかの例としては、最小値、負値も含む総和、なども可能なよう。
配列上の二分木による実装
function createMaxArray(
nums, start = 0, end = nums.length,
array = new Array((1 << (Math.ceil(Math.log2(nums.length)) + 1)) - 1), i = 0) {
const length = end - start;
if (length === 1) {
array[i] = nums[start];
return array;
}
const mid = start + (length >> 1);
const leftI = i * 2 + 1, rightI = leftI + 1;
createMaxArray(nums, start, mid, array, leftI);
createMaxArray(nums, mid, end, array, rightI);
array[i] = Math.max(array[leftI], array[rightI]);
return array;
}
function findMax(array, nStart, nEnd, start, end, minValue = -Infinity, i = 0) {
if (end <= nStart || nEnd <= start) return minValue; // ノードの範囲が完全に範囲外
if (start <= nStart && nEnd <= end) return array[i]; // ノードの範囲が完全に範囲内
// 部分的に範囲内
const mid = nStart + ((nEnd - nStart) >> 1);
const leftI = i * 2 + 1, rightI = leftI + 1;
const left = findMax(array, nStart, mid, start, end, minValue, leftI);
const right = findMax(array, mid, nEnd, start, end, minValue, rightI);
return Math.max(left, right);
}
function updateMaxArray(array, nStart, nEnd, i, value, j = 0) {
if (i < nStart || nEnd <= i) return array[j]; // iが完全に範囲外
const length = nEnd - nStart;
if (length === 1) return array[j] = value;
const mid = nStart + (length >> 1);
const leftJ = j * 2 + 1, rightJ = leftJ + 1;
const left = updateMaxArray(array, nStart, mid, i, value, leftJ);
const right = updateMaxArray(array, mid, nEnd, i, value, rightJ);
return array[j] = Math.max(left, right);
}
配列の先頭に全範囲の最大値、次に前半分の最大値、その次に後半分の最大値、という配列になります。
要素数によっては、空白のセルも二分木配列の途中に存在し、たとえば要素数3の場合では、[全体の最大値, 要素0の値, 要素1と2の最大値, 空白, 空白, 要素1の値, 要素2の値]
になります。
値配列の要素数3の場合、二分木配列の要素数は7であり、要素数nの値配列に対し、2^(ceil(log2(n))+1)-1要素数の二分木配列ができます。
最悪は、値配列の要素数2^n+1の場合で、最後2つが埋まり、その前に空白が2^ceil(log2(n))-2個続くことになります。
手法は二分木構造体と全く同じですが、配列上に二分木を作る場合、検索時に元の値配列のサイズ(上記コードではnEnd
)を与える必要があります。
ベンチマークとその結果
コード: find-max.js
function findMax0(nums, start, end, minValue = -Infinity) {
let maxValue = minValue;
for (let i = start; i < end; i++) {
maxValue = Math.max(maxValue, nums[i]);
}
return maxValue;
}
function createMaxTree(nums, start = 0, end = nums.length) {
const length = end - start;
if (length === 1) return {max: nums[start], start, end};
const mid = start + (length >> 1);
const left = createMaxTree(nums, start, mid);
const right = createMaxTree(nums, mid, end);
// [start, end)範囲での最大値がmax
return {max: Math.max(left.max, right.max), start, end, left, right};
}
function findMax(tree, start, end, minValue = -Infinity) {
if (end <= tree.start || tree.end <= start) return minValue; // ノードの範囲が完全に範囲外
if (start <= tree.start && tree.end <= end) return tree.max; // ノードの範囲が完全に範囲内
// 部分的に範囲内
const left = findMax(tree.left, start, end, minValue);
const right = findMax(tree.right, start, end, minValue);
return Math.max(left, right);
}
function createMaxArray(
nums, start = 0, end = nums.length,
array = new Array((1 << (Math.ceil(Math.log2(nums.length)) + 1)) - 1), i = 0) {
const length = end - start;
if (length === 1) {
array[i] = nums[start];
return array;
}
const mid = start + (length >> 1);
const leftI = i * 2 + 1, rightI = leftI + 1;
createMaxArray(nums, start, mid, array, leftI);
createMaxArray(nums, mid, end, array, rightI);
array[i] = Math.max(array[leftI], array[rightI]);
return array;
}
function findMaxArray(array, nStart, nEnd, start, end, minValue = -Infinity, i = 0) {
if (end <= nStart || nEnd <= start) return minValue; // ノードの範囲が完全に範囲外
if (start <= nStart && nEnd <= end) return array[i]; // ノードの範囲が完全に範囲内
// 部分的に範囲内
const mid = nStart + ((nEnd - nStart) >> 1);
const leftI = i * 2 + 1, rightI = leftI + 1;
const left = findMaxArray(array, nStart, mid, start, end, minValue, leftI);
const right = findMaxArray(array, mid, nEnd, start, end, minValue, rightI);
return Math.max(left, right);
}
{
const values = [...Array(30000).keys()].map(v => Math.random());
const mid = values.length >> 1;
const maxes0 = [];
performance.mark("linear:start");
for (let i = 0; i < values.length; i++) {
const start = Math.min(i, mid), end = Math.max(i, mid);
maxes0.push(findMax0(values, start, end, 0));
}
performance.mark("linear:end");
const maxes = [];
performance.mark("tree:start");
const tree = createMaxTree(values);
performance.mark("tree:created");
for (let i = 0; i < values.length; i++) {
const start = Math.min(i, mid), end = Math.max(i, mid);
maxes.push(findMax(tree, start, end, 0));
}
performance.mark("tree:end");
const maxesA = [];
performance.mark("array:start");
const array = createMaxArray(values);
performance.mark("array:created");
for (let i = 0; i < values.length; i++) {
const start = Math.min(i, mid), end = Math.max(i, mid);
maxesA.push(findMaxArray(array, 0, values.length, start, end, 0));
}
performance.mark("array:end");
console.log(maxes.every((m, i) => m === maxes0[i]));
console.log(maxes.every((m, i) => m === maxesA[i]));
performance.measure("linear", "linear:start", "linear:end");
performance.measure("tree", "tree:start", "tree:end");
performance.measure("tree:create", "tree:start", "tree:created");
performance.measure("tree:find", "tree:created", "tree:end");
performance.measure("array", "array:start", "array:end");
performance.measure("array:create", "array:start", "array:created");
performance.measure("array:find", "array:created", "array:end");
console.log(performance.getEntriesByName("linear")[0]);
console.log(performance.getEntriesByName("tree")[0]);
console.log(performance.getEntriesByName("tree:create")[0]);
console.log(performance.getEntriesByName("tree:find")[0]);
console.log(performance.getEntriesByName("array")[0]);
console.log(performance.getEntriesByName("array:create")[0]);
console.log(performance.getEntriesByName("array:find")[0]);
}
実行結果
$ deno run --allow-hrtime find-max.js
true
true
PerformanceMeasure {
name: "linear",
entryType: "measure",
startTime: 34.373083,
duration: 188.385333,
detail: null
}
PerformanceMeasure {
name: "tree",
entryType: "measure",
startTime: 223.589083,
duration: 18.106583,
detail: null
}
PerformanceMeasure {
name: "tree:create",
entryType: "measure",
startTime: 223.589083,
duration: 6.16508300000001,
detail: null
}
PerformanceMeasure {
name: "tree:find",
entryType: "measure",
startTime: 229.754166,
duration: 11.94149999999999,
detail: null
}
PerformanceMeasure {
name: "array",
entryType: "measure",
startTime: 241.722958,
duration: 13.832333000000006,
detail: null
}
PerformanceMeasure {
name: "array:create",
entryType: "measure",
startTime: 241.722958,
duration: 2.6689580000000035,
detail: null
}
PerformanceMeasure {
name: "array:find",
entryType: "measure",
startTime: 244.391916,
duration: 11.163375000000002,
detail: null
}
$
3万要素で、線形検索だと188.8かかるのが、二分木だと11.9、二分木配列だと11.2かかるだけになりました。