ある連続値が区間集合のどの位置に含まれるか

JavaScript アルゴリズム
  • 問題: 区間の上界と下界の属性を元に、何かを計算する
    • 例えば、区間集合{ 3: {3の属性}, 5: {5の属性}, 8: {8の属性}, ... }
    • 4を与えると、4は3と5の区間に含まれるから、3の属性と5の属性から、4の属性を新たに計算したい
  • 解決1: 素朴に indexOf
    • 4が区間(3, 5)に含まれることを検索するのに線形探索?
    • 区間が少ないならあるいは。 それでも、10個の区間で、80の点で同じ処理をするなら?　うーん。比較数n x m
  • 解決2: 切断点集合を与えて、まとめて処理
    • {10, 11, 29, 30, ...}求めたい切断点はたくさんあるなら、まとめて処理した方が比較数が減る
    • 多分比較数log(n) x m 
var sections = [{"距離": 0, "高さ": 10}, {"距離": 2, "高さ", 12}, {"距離": 8, "高さ": 14},,,];
var dists = [4, 9, 10]; // 切断点集合

sections.inject([], function(list, section, i, self){
   for (var dist = dists[0]; dist != null && (section["距離"] <= dist); dist = dists[0]){
      if (i+1<self.length ? (dist < self[i+1]["距離"]) : true){
　　　　var grad = (self[i+1]["高さ"]-section["高さ"])/(self[i+1]["距離"]-section["距離"];     　　　
        list.push({"距離": dist, "高さ": section["高さ"] + grad * (dist - section["距離"])})
      }else
        break;
      dist = dists.shift();
    }
  return list;
});

これでOK。

dist =　dists.shift()とdist = dists[0]を分けてあるのがミソ。