Ruby
アルゴリズム

group_by のような処理で、要素数を保ったまま戻り値を得るメソッド(名称募集)

More than 1 year has passed since last update.

値はどの区間に含まれるか

任意の距離での高さを求めたいです。各区間は一定勾配で変化しています。

  • 区間集合
sections = [
  {"距離" =>   0,     "高さ" => 80.650},
  {"距離" =>  40,     "高さ" => 78.650},
  {"距離" => 126.153, "高さ" => 76.065}
]
  • 各点
distances = [0, 20, 40, 60, 80, 100, 120, 126.153]`
  • distances.group_by{|distance| ...}として、group_by だと次のように仕分けされる(イメージ)
sections = [                                                                                                                         
  {"距離" =>   0,     "高さ" => 80.650}, # 0, 20                                                                                     
  {"距離" =>  40,     "高さ" => 78.650}, # 40, 60, 80, 100, 120                                                                      
  {"距離" => 126.153, "高さ" => 76.065}  # 126.153                                                                                   
]

そうではなくて、期待する戻り値はこう

  • SQLでいう、LEFT JOINのような
=begin
return_values = [                                                                                                                    
  {"距離": 0       , under: {"距離": 0, "高さ": 80.650},  over: {"距離": 40, "高さ": 78.650} }                                       
  ,{"距離": 20     , under: {"距離": 0, "高さ": 80.650},  over: {"距離": 40, "高さ": 78.650} }                                       
  ,{"距離": 40     , under: {"距離": 40, "高さ": 78.650}, over: {"距離": 126.153, "高さ": 76.065} }                                  
  ,{"距離": 60     , under: {"距離": 40, "高さ": 78.650}, over: {"距離": 126.153, "高さ": 76.065} }                                  
  ,{"距離": 80     , under: {"距離": 40, "高さ": 78.650}, over: {"距離": 126.153, "高さ": 76.065} }                                  
  ,{"距離": 100    , under: {"距離": 40, "高さ": 78.650}, over: {"距離": 126.153, "高さ": 76.065} }                                  
  ,{"距離": 120    , under: {"距離": 40, "高さ": 78.650}, over: {"距離": 126.153, "高さ": 76.065} }                                  
  ,{"距離": 126.153, under: {"距離": 126.153, "高さ": 76.065}  over: nil}                                                            
]
=end

でけた。

sectionlist = sections.dup

puts distances.map{|distance|
  while sectionlist.length > 0 do
    under = sectionlist.first();
    over  = sectionlist.length < 2 ? nil : sectionlist[1];
    if (over.nil? || distance < over["距離"])
      break {"距離" => distance, :under => under, :over => over}
    end
    sectionlist.shift();
  end
}
  • 実行結果
{"距離"=>0, :under=>{"距離"=>0, "高さ"=>80.65}, :over=>{"距離"=>40, "高さ"=>78.65}}
{"距離"=>20, :under=>{"距離"=>0, "高さ"=>80.65}, :over=>{"距離"=>40, "高さ"=>78.65}}
{"距離"=>40, :under=>{"距離"=>40, "高さ"=>78.65}, :over=>{"距離"=>126.153, "高さ"=>76.065}}
{"距離"=>60, :under=>{"距離"=>40, "高さ"=>78.65}, :over=>{"距離"=>126.153, "高さ"=>76.065}}
{"距離"=>80, :under=>{"距離"=>40, "高さ"=>78.65}, :over=>{"距離"=>126.153, "高さ"=>76.065}}
{"距離"=>100, :under=>{"距離"=>40, "高さ"=>78.65}, :over=>{"距離"=>126.153, "高さ"=>76.065}}
{"距離"=>120, :under=>{"距離"=>40, "高さ"=>78.65}, :over=>{"距離"=>126.153, "高さ"=>76.065}}
{"距離"=>126.153, :under=>{"距離"=>126.153, "高さ"=>76.065}, :over=>nil}

この処理は使い出がありそうなので、仕分けメソッドとして定義。

class Array
  def account(sectionlist, key, &block)
    return self.map{ |distance|
      while sectionlist.length > 0 do
        under = sectionlist.first()
        over  = sectionlist.length < 2 ? nil : sectionlist[1];
        if (over.nil? || distance < over[key])
          break block_given? ? block.call(distance, under, over) :
                  {key => distance, :under => under, :over => over}
        end
        sectionlist.shift();
      end
      # sectionlistがnilか空の場合は例外にすべき?                                                                                    
    }
  end
end

ひとまず、各点の高さを計算。

  • これが求めるべきものであった。
puts
puts distances.account(sections.dup, "距離")

puts
puts distances.account(sections.dup, "距離"){|distance, under, over|
  if over.nil?
    {"距離" => distance, "高さ" => under["高さ"]}
  else
    grad   = (over["高さ"] - under["高さ"])/(over["距離"] - under["距離"])
    height = under["高さ"] + grad * (distance - under["距離"]);

    {"距離" => distance, "高さ" => height};
  end
}
  • 実行結果
{"距離"=>0, "高さ"=>80.65}
{"距離"=>20, "高さ"=>79.65}
{"距離"=>40, "高さ"=>78.65}
{"距離"=>60, "高さ"=>78.04990482049378}
{"距離"=>80, "高さ"=>77.44980964098755}
{"距離"=>100, "高さ"=>76.84971446148131}
{"距離"=>120, "高さ"=>76.24961928197509}
{"距離"=>126.153, "高さ"=>76.065}

仕分けが念頭にあったのでaccountと、命名。

RubyのArrayクラスは便利なメソッドが洗練されてありますが、一見してこの処理は見受けられませんでした。(Ruby 2.4.0 で調べた)

節穴かも。