2022-12-29

優先度付きキューにも使われる二分ヒープ構造をRubyで実装してみる

tech

作者:石田保輝,宮崎修一
翔泳社

アルゴリズム図鑑を眺めていて、二分ヒープ構造は優先度付きキューに使われることを知った。面白いなーと思うと同時に、そういえば二分ヒープ構造の実装をしたことがなく、あまり理解できていないことに気づいた。そこで簡単にRubyで実装をしてみたのでメモ。簡単なテストケースを作ったので多分合ってると思うけど、もしかしたらバグっているかも...

二分ヒープの詳細は二分ヒープ - Wikipediaも参考。

【2023/01/03 14:01追記】要素数が1の時に要素が空にならないバグがあったので修正しました。コメントありがとうございます。https://github.com/shibayu36/algorithms/commit/6c2ce588f7bc7fb890c6a560c7ab062c6f531a9a

実装

class Heap
  attr_reader :nodes

  def initialize(arr)
    @nodes = []
    arr.each { |val| push(val) }
  end

  def size
    @nodes.size
  end

  def push(val)
    @nodes.push(val)

    current_index = size - 1
    parent_index = parent_of(size - 1)

    while current_index > 0 && @nodes[parent_index] > @nodes[current_index]
      swap(parent_index, current_index)
      current_index = parent_index
      parent_index = parent_of(current_index)
    end
  end

  def pop
    return @nodes.pop if size <= 1

    res = @nodes[0]

    @nodes[0] = @nodes.pop

    current_index = 0
    child_index = min_child_of(current_index)

    while child_index && @nodes[child_index] < @nodes[current_index]
      swap(child_index, current_index)
      current_index = child_index
      child_index = min_child_of(current_index)
    end

    res
  end

  private

  def parent_of(index)
    (index - 1) / 2
  end

  def min_child_of(index)
    left_child_index = (2 * index) + 1
    right_child_index = (2 * index) + 2

    left_val = nodes[left_child_index]
    right_val = nodes[right_child_index]

    if left_val && right_val
      left_val <= right_val ? left_child_index : right_child_index
    elsif left_val
      left_child_index
    end
  end

  def swap(i, j)
    @nodes[i], @nodes[j] = @nodes[j], @nodes[i]
  end
end

テスト

require 'heap'

describe Heap do
  describe '#push' do
    it do
      heap = Heap.new([4, 1, 3])
      expect(heap.nodes).to eq([1, 4, 3])

      heap.push(5)
      expect(heap.nodes).to eq([1, 4, 3, 5])

      heap.push(0)
      expect(heap.nodes).to eq([0, 1, 3, 5, 4])
    end
  end

  describe '#pop' do
    it do
      heap = Heap.new([0, 1, 3, 5, 4, 3])

      expect(heap.pop).to eq 0
      expect(heap.nodes).to eq([1, 3, 3, 5, 4])

      expect(heap.pop).to eq 1
      expect(heap.nodes).to eq([3, 4, 3, 5])

      expect(heap.pop).to eq 3
      expect(heap.pop).to eq 3
      expect(heap.pop).to eq 4
      expect(heap.pop).to eq 5

      expect(heap.pop).to eq nil
    end
  end
end

これはminヒープという構造。popすると必ず値が低い順に取得することができる。例えば値に優先度を示す数字を入れておけば、優先度付きキューとして使える。便利。

2022-12-25

Rubyでnewに渡ってきたパラメータ引数のaccessorを自動で作る

tech

GitHub Copilotに補完されて面白いなと思ったのでメモ。たとえばLTSVのログを格納する構造を作るときに、渡ってきたパラメータ引数名を使ってアクセサを作りたいとする。以下のようなコードで実現が可能。

class Log
  # パラメータ引数をハッシュで受け取って
  def initialize(**fields)
    fields.each do |key, value|
      # インスタンス変数を作りつつ
      instance_variable_set("@#{key}", value)
      # attr_readerで動的に定義
      self.class.send(:attr_reader, key)
    end
  end
end

これを使うと、勝手にアクセサが生えてくる。

log = Log.new(
  user: 'frank',
  status: '200',
  size: '2326',
)
p(log.user) # => 'frank'
p(log.status) # => '200'
p(log.size) # => '2326'

2022-12-19

認知行動療法についての自分なりのまとめ

misc

最近、「マンガでやさしくわかる認知行動療法」読んだ - $shibayu36->blog;や「認知行動療法による対人援助スキルアップ・マニュアル」を読んだ - $shibayu36->blog;で紹介したとおり、認知行動療法について学んでいた。自分の中で認知行動療法のイメージが湧いてきたので、自分なりにまとめておく。

自分は専門家ではないので、実際にやるときは専門家に相談したり、自分で本を読んだりしましょう。

基本となるモデル

事実の受け止め方は、認知によって変化する(ABCモデル)
- 状況 -> 自動思考 -> 反応（気分、行動）
- 状況からそのまま気分や行動が決まるのではなく、状況から自分の解釈が挟まりその解釈によって気分や行動が生まれるという考え方が大事
自分がどのように事実を受け止めているかを判断するために、状況確認シートを使うとよい
- 状況 -> 認知・感情・行動・身体反応で整理
自分がストレスを感じやすい状態になっている時、認知がバランスの取れていない極端な状態になっていることが多い
認知・感情・行動・身体反応の中で、認知と行動は変化をさせやすい。感情と身体反応は変化をさせにくい。変化をさせやすい認知と行動を対象として改善を進める
認知に働きかけることで、状況からストレスを感じにくいバランスの取れた考え方ができるような自分を作っていく
行動に働きかけていくことで、ネガティブな気持ちになっている時に、ネガティブな気持ちのループになることを防ぎやすくする

認知行動療法の進め方

状況整理 -> 状況観察 -> 考え方のクセを掴む -> 考え方を変化させる・行動を変化させる

状況整理や状況観察に使えるワーク

セルフモニタリング法
- 就寝・起床時間、行動したこと、体調や気分を点数化したものなどで、それを一定期間（1週間・1か月など）続けて振り返ることで、客観的に自分の体調や気分の変化をの傾向を知る
状況確認シート
- 例: https://www.cocoro-quest.net/entry/anxiety-basic

考え方のクセを掴む

自分の考え方のクセを捉えることで、同様の思考になった時に、もう少しバランスの取れた考え方にしやすい。クセにはパターンがあるので、そのパターンを使うと整理しやすい。

白黒思考: 状況を極端な2つのカテゴリーで考えてしまう
過度の一般化: たったひとつの嫌な出来事があると、実際を遥かに超えて世の中全て同様と考える
心のフィルター(選択的抽出): 全体を見ることなくたったひとつの嫌なことにこだわることによって、現実を実際より暗くみてしまう
マイナス化思考(トンネル視): 状況に対して、良い出来事を無視してしまうことによって、否定的な側面しか見ない
結論の飛躍・心の読みすぎ: 現実な可能性を考慮せず、相手が自分に対して悪く考えていると早合点する
結論の飛躍・先読みの誤り: 事態が悪くなると決めつける
拡大視・縮小視: 自分の失敗を課題に考え、成功を過小評価する。逆に他人に対しては反対のことを行う
感情的理由づけ: 例えば「こう感じるのだから、それは本当のことだ」と自分の憂鬱な感情を自分の現実認識が正しいという理由とすること
「べき」思考: 自分や他人の振る舞いや考えに対して固定された思考を要求し、それが実現しないことを「最悪」だと考える
レッテル貼り: 極端な形の「過度の一般化」であり、ミスした自分や他人に対して、固定的で包括的なレッテルを貼ってしまう
自己関連づけ: 何か嫌な事柄が起こった時、自分に責任がないような出来事に対しても自分のせいにしてしまう

考え方を変化させるのに使えるワーク

コラム法。3コラム、5コラム、7コラムなど
- https://works.litalico.jp/column/system/018/
- 認知に対して、矛盾点を洗い出して妥当性を検討する、メリットとデメリットを比べてみるなどのやり方もある
暴露反応妨害法
- 苦手なことに対して、別の選択肢を準備した上で、あえて苦手なことにチャレンジする。それによってスモールステップで、その苦手なことに慣れるようにする

行動を変化させるのに使えるワーク

行動活性化法
- https://www.goto-c.com/blog/%E8%A1%8C%E5%8B%95%E6%B4%BB%E6%80%A7%E5%8C%96/
- 分が変わりそうな活動を探し、気分が晴れない時にひとまずその活動をしてみる
- コーピングレパートリーの話に近い
リラクセーション法
- リラクセーション法（呼吸法）の紹介 | 日下部記念病院
- マインドフルネス的な観点に近い