PowerAutomateで、ReservoirSamplingを実装してみた。

こんにちは、 @tariki-code ことコバッチです。
前回の記事の続編で、PowerAutomateでReservoirSamplingを実装してみる事をやってみました。

きっかけ

2023 PowerAutomate AdventCalenderを投稿させていただきました。

18日目の記事です。背景となるフローの詳細もこちらに記載してますので、もしよろしければご参照ください。

やりたいことは、Teams上のとあるチームに参加しているメンバー（200名程度）から、アイスブレイクな質問を送るべくランダムに抽出したい・・・というもので、そのPowerAutomteでの実装方法について記事を書かせていただきました。

この時に、以下のようなコメントをいただいたので、少し調べてやってみようと思ったのがきっかけです！！（@igrep様、ありがとうございます。）

ReservoirSamplingとは？

• 大容量のデータストリームや配列からランダムに要素を取得するためのアルゴリズム。
• 要素の数が不明でも、大量の領域を使ったり、1件づつ舐めるような事をせずとも、均一な確率でランダムにデータを取得したい時に使われる。

きちんとした参考文献を見ていただければとは思いますが、一旦GPT君に相談した時に受けた説明が以下です。

JavaScriptでアルゴリズムを書いてみる

書いてみると言いますか、面倒なのでGPT君に頼んで書いてもらいました。笑
コードは以下です、一応Githubにも挙げてみました。

index.js

function reservoirSampling(stream, k) {
    // Initialize the reservoir with the first k elements
    let reservoir = [];
    for (let i = 0; i < k; i++) {
        reservoir[i] = stream[i];
    }

    // Process the remaining elements in the stream
    for (let i = k; i < stream.length; i++) {
        // Randomly decide whether to replace an element in the reservoir
        let j = Math.floor(Math.random() * (i + 1));
        if (j < k) {
            reservoir[j] = stream[i];
        }
    }

    return reservoir;
}

// Example usage
const dataStream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50];
const k = 5; // Number of samples to select
const sampledData = reservoirSampling(dataStream, k);
console.log("Sampled Data:", sampledData);

dataStreamが対象となる配列で、サンプルでは1から50までの数字が入っています。
kがサンプリングしたい数です。
これら２つのパラメータを渡してreservoirSamplingの関数を実行します。

結果はこんな感じです。

terminal

bash-3.2$ node index.js
Sampled Data: [ 20, 2, 18, 4, 13 ]

bash-3.2$ node index.js
Sampled Data: [ 11, 45, 3, 16, 27 ]

・・・と毎回違う結果が返ってきます。

関数内のlet j = Math.floor(Math.random() * (i + 1));が処理の中核部分でこちらは、２つのステップの処理を行っています。

ランダムな数の生成：

• Math.random() は、0以上1未満のランダムな浮動小数点数を生成します。
• このランダムな数に (i + 1) を掛けることで、0以上 i 以下の範囲のランダムな浮動小数点数が得られます。ここでのiは現在処理しているデータセット内の要素のインデックスです。

整数への丸め：

• Math.floor()関数は、与えられた数を下方向へ最も近い整数に丸めます。
• 結果として、0からiの範囲内でランダムな整数jが生成されます。

この生成されたランダムな整数jは、reservoir内の要素のどれかを現在の要素（i番目の要素）と置き換えるかどうかを決定するために使われます。もしjがreservoirのサイズk未満の場合、reservoir内のj番目の要素が現在の要素で置き換えられます。これにより、データセットの各要素が最終的なサンプルに含まれる確率が等しくなるように設計されています。

PowerAutomateでどう実装する？

PowerAutomateで実装するなら、Excel Onlineを使って、OfficeScriptを実行させるのが一番楽かなと思いました。

想定しているフローのイメージは以下の通りです。
こう見ると、rand関数をちょっと豪華にした処理に過ぎないようにも見えます。。笑
まぁでもやってみたいと思います。

Excelでコード書いてみる

Office365からExcelOnlineで任意のファイルを立ち上げ、「Automate」のメニューから「NewScript」をクリックすると、エディターが起動します。

OfficeScriptはTypeScriptがベースになっているようです。先ほどのGPT君に作ってもらったサンプルソースコードの型指定の部分など若干修正します。ちなみに数値配列の変数を指定するのであればfoo: number[]と書きます。

また、処理をシンプルにするために、要素数とサンプリングをしたい数を指定したら、その条件でその要素を取得する際アドレスとなる数字配列を返すという処理にしました。

実装したソースコードは以下となります。

Reservoir Sampling.xlsx

function main(workbook: ExcelScript.Workbook, length: number, k: number){
    
  // Initialize Stream
  let stream: number[] = [];
  for (let i = 0; i < length; i++) {
    stream[i] = i
  }

  // Initialize the reservoir with the first k elements
  let reservoir: number[] = [];
  for (let i = 0; i < k; i++) {
    reservoir[i] = stream[i];
  }

  // Process the remaining elements in the stream
  for (let i = k; i < stream.length; i++) {
    // Randomly decide whether to replace an element in the reservoir
    let j = Math.floor(Math.random() * (i + 1));
    if (j < k) {
      reservoir[j] = stream[i];
    }
  }
  console.log("reservoir:", reservoir);
  return reservoir;
}

lengthで要素数を受け取ります。受け取った要素数のある数値配列をstreamとして作成します。
kはサンプリングしたい数です。

実行確認をしてみる

「Run」をクリックすると実行確認ができます。

パラメータが設定されている場合は、入力が求められます。
この例だと、100要素の中から、10個のサンプルを取ってきてくださいという意味になります。

実行結果はこうなります。

PowerAutomateから呼び出してみる

ちょっと雑かもしれませんが。。w、とりあえず作ってみました、
全体のフローです。

前半

後半

グループメンバー一覧表示

単純にチームのメンバー一覧を取得してきます。

変数を初期化する１（lengthの設定）

取得してきたグループメンバーのlengthを取ります。これも簡単ですね。

変数を処理化する１

length(outputs('グループ_メンバーの一覧表示')?['body/value'])

変数を初期化する２（kの設定）

常に10%のサンプリング率になるようにkの計算を行います。
単純にlengthに10%を乗算した結果を整数に切り上げるという処理です。

変数を初期化する２

int(formatNumber(mul(variables('length'), 0.1), 'F0'))

少ないチームでも最低でも5名選出はしようということで、条件を追加してみました。
kの計算結果が、5未満でかつlengthが10より大きい場合だけ、強制的にk=5としてみました。

スクリプトの実行

ExcelOnlineで「スクリプトの実行」アクションを選択すると、実行するスクリプトファイルが保存されているファイルの選択ができます。

また、そのスクリプトのパラメータの入力が求められるので指定をします。今回はlengthとkが必要なので、それぞれフローの中で設定した変数を指定します。

変数を初期化する（スクリプト実行結果の取得）

実行したスクリプトの結果の配列を受け取ります。
そのまま配列変数に突っ込んでいるだけです。

Apply to Each

配列の数分だけループを回します。
グループメンバー一覧で取得してきた要素数の範囲でランダムな数字を持っているので、そのアドレスを指定する形で値を取得します。

今回はUPNだけで良いので、要素を指定して取得します。

配列を変数に追加

outputs('グループ_メンバーの一覧表示')?['body/value'][items('Apply_to_each')]?['userPrincipalName']

実行結果

スクリプト実行によって、うまくランダムな数字を取得できました。

また、取得したランダム数字を使って、そのアドレスを持つユーザーのUPNも問題なく取得できています。

これによって、前記事の処理ではグループメンバー一覧の要素数だけApply to Eachする必要が無くなったので処理速度としては改善できることが期待できます。

感想

• 毎回思うことですが、もっといいやり方を知っている人は是非コメントなどで教えてくださいー
• 今回はとりあえずサンプル的にフロート作ってみましたが、実際のフローに適用してみて、処理速度の面についてはもう少し検証してみたい。
  OfficeScriptはプログラミングをやってきた人にとっては他のケースでもうまく活用できるかも、TypeScriptがベースになっているのでかなり個人的にはとっつきやすいし、フローとコード部分の棲み分けもキレイな疎結合で管理できそうな気がしました。
• 2024/01/20開催、「気ままに勉強会#75」でLTさせていただきますー。

ReservoirSamplingに関する参考URL

参考にさせていただきました、ありがとうございます。