LoginSignup
0

More than 1 year has passed since last update.

二分木を用いた数値配列の部分範囲内の最大値取得

Last updated at Posted at 2022-04-10

ベタな実装

数値配列の部分範囲内の最大値は以下のように検索できます。

線形最大値検索
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
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かかるだけになりました。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0