並列文字頻度

説明

並列計算を使って、テキストに含まれる文字の出現頻度を数えましょう。

並列処理とは、順番に実行することもできる物事を、並行して行うことです。よくある例が、文字の出現頻度を数えることです。並列処理を活用して、テキストの配列に含まれる各文字の出現頻度の合計を計算しましょう。

非同期タスク

タスクは、Leanで非同期コードを書くための主要な抽象化です。軽量で、別のスレッドで並列に実行されることも、同じスレッド上で並行に実行されることもあります。

タスクには、純粋なものと不純なものがあります。純粋なタスクはTask.spawnで作成します。Task.spawnは純粋な計算を受け取ります。不純なタスクは、IOの計算から作成します。たとえばIO.asTaskを使うと、IO αをIOモナドの中のTask αに持ち上げることができます。

この演習では、関数calculateFrequenciesはモナド的で、IO (Std.TreeMap Char Nat)を返します。これにより、IO.asTaskを使った不純なタスクを利用できるだけでなく、最終的な値を返す前の中間計算のために純粋なタスクを生成することもできます。

データ競合を防ぐ

関数型言語であるLeanでは、ほとんどの値は永続的、つまり不変です。値を変更しているように見える操作も、実際には変更を加えた新しい値を作り出します。そのため、データ競合を起こさずに、メモリをタスク間で安全に共有できることがよくあります。

ただし、すべてのデータ構造が永続的な使い方に同じように向いているわけではありません。たとえば、Arrayの1つの要素を更新するには、通常は配列全体をコピーする必要があります。Std.HashSetやStd.HashMapも同じです。

こうしたデータ構造を効率的に扱うために、Leanは参照カウントを使っています。値への参照が1つだけである限り、更新を破壊的に行えるので、不要なコピーを避けられます。

一方、ListやStd.TreeSet、Std.TreeMapのようなデータ構造は、内部的に構造を共有するように設計されています。更新するときには変わらないノードを再利用するので、複数の値がそれらのノードへの参照を共有できます。その結果、構造の一部を変更するときも、通常は値全体をコピーする必要がありません。こうしたデータ構造は、タスク間での共有に特に向いています。

実行速度を測る

各テストの実行時間は、IO.monoNanosNowを使ってナノ秒単位で測定され、結果と一緒に表示されます。いろいろな方法を試して、実行時のパフォーマンスにどんな影響があるか確かめてみましょう。