NimのHashSet, OrderedSet(setsモジュール)とset(system), PackedSet(packedsets)の違いと速度比較

はじめに

最近気になっている言語Nim。触ってから、集合を扱える標準ライブラリの型がsystemにあるsetとsetsのHashSetとOrderedSetの3種類あることを知った。これらの違いは何となく分かっても、実際の速度差については調べたことが無かったので今回メモしていこうと思う。
追記：packedsetsモジュールにPackedSetがあったのでこれの実行速度も計測した。

set

(型の説明はNim TutorialのSetsを大いに参考にしている。)
setは数学的概念における集合をモデル化したものらしく、setに使える型は以下の序数型とそれと同等のものに限定されている。

• int8 - int16
• uint8 / byte - uint16
• char
• enum

setの最大要素数であるMaxSetElementsが2^16となっていることから16bitより大きいint32などの序数型が許可されない。また，符号付き整数も許可されているが0以上である必要がある。
setの使用例は以下の通りである（Wandbox）。なお、チュートリアルで示された関数以外にlen, setを指定するincl, setを指定するexcl等が定義されていた。

import std/typetraits          # 型の確認のため，syetemモジュールはimportする必要なし

let a1 = {2'i8, 3, 9, 4, 5}    # コンストラクタは{}
var a2 = {0'i8, 4, 3..7}       # 3以上7以下の要素を一気に入れることができる
echo typetraits.name(type(a1)) # set[int8]
let b = {2'u16..4, 9, 13..19}
echo typetraits.name(type(b))  # set[uint16]
let c = {1, 1, 9, 3}           # 0..65535内でのint
echo typetraits.name(type(c))  # set[range 0..65535(int)]
echo ""

echo "a1=", a1
echo "a2=", a2
echo ""

# echo a1 + b 要素の型が違うと演算不可
echo "a1 + a2=", a1 + a2 # 和集合
echo "a1 * a2=", a1 * a2 # 積集合
echo "a1 - a2=", a1 - a2 # 差集合
echo ""

echo "a1.card=", a1.card # 要素数
echo "a1.len=", a1.len # 要素数(cardと同じ)
echo "2 in a1=", 2 in a1 # 含むかどうか
echo "a1.contains(2)=", a1.contains(2) # 含むかどうか(inと同じ)
echo "0 notin a1=", 0 notin a1 # 含まないかどうか
echo ""

a2.incl(1) # 1を包含させる
a2.incl({6'i8..10}) # setで複数包含させられる
echo "a2=", a2
a2.excl(3) # 3を除外する
a2.excl({3'i8..6})  # setで複数除外させられる
echo "a2=", a2

また、AとBの集合があった時に、どちらも同じ要素を含んでいる集合であればA == B、AがBの部分集合(Bの一部を取り出したもの)であればA <= B、AがBの真部分集合(Bの全部を取り出すことは認めない)であればA < Bでチェックできる。

HashSet, OrderedSet

要素にできる制限が「ハッシュ可能な値」に大きく緩んだ集合がsetsで提供されている。Nimで "集合" を扱う setsに詳しく内容が記してあるため、ここではsetの関数から更に追加された主な関数について実行例を示す（Wandbox）。

import std/sets

var a1 = [2,5,3,5,6].toHashSet
let a2 = [1,3,4,5,7,8].toHashSet

echo "a1=", a1
echo "a2=", a2
echo ""

echo "a1 -+- a2=", a1 -+- a2                       # 対称差(a1またはa2の要素であるが同時に両方の要素ではない)
echo "a1.disjoint(a2)=", a1.disjoint(a2)           # 素集合(共通部分を持たない)であるか
echo "a1.disjoint(a2-a1)=", a1.disjoint(a2-a1)     # 素集合(共通部分を持たない)であるか
echo "a1.pop=", a1.pop                             # 任意の要素を取得しa1から削除
echo "a1=", a1
echo ""

echo "a1.missingOrExcl(5)=", a1.missingOrExcl(5)   # 存在する場合falseを返し要素を削除、存在しない場合true
echo "a1.missingOrExcl(5)=", a1.missingOrExcl(5) 
echo "a1=", a1
echo "a1.containsOrIncl(5)=", a1.containsOrIncl(5) # 存在しない場合falseを返し要素を追加、存在する場合true
echo "a1.containsOrIncl(5)=", a1.containsOrIncl(5)
echo "a1=", a1
echo "a1.hash=", a1.hash     # ハッシュ化
echo "a1.map(proc (x: int): int = x * x)=", a1.map(proc (x: int): int = x * x)  # map
a1.clear                     # 要素を全消去
echo "a1=", a1
echo ""

追記：PackedSet

標準ライブラリを調べているとPackedSet（及びIntSet）を発見した。PackedSetは、疎な（スパース）ビット集合により効率的な序数型集合を実装している(std/packedsets)。任意の序数型を指定できるので、制限はsetより緩く、HashSetよりは厳しい。
「効率的な」と表現する理由は、setにおいては内部でビットフィールドを用いて定義されているためだろう。もし、set[range[0..15]]と定義するなら[0が存在するかのビット、1が存在するかのビット....15が存在するかのビット]の合計16bit=2byteが必要となる。これだけならまだしもset[range[0..65535]]と定義すれば65,536bit=8,192byteを必要としてしまう（[Nim]Nimの文法を勉強 04 (データ型(前編))）。
対してPackedSetは、以下のように定義されている。

PackedSet[A] = object
  elems: int
  counter, max: int
  head: Trunk
  data: TrunkSeq
  a: array[0 .. 33, int]

このため、恐らく存在する値だけメモリを確保しており、効率的なのだと思われる。なお、定義されていた関数はHashSetとほとんど同じであった。

速度比較

set, HashSet, OrderedSetに対して、0以上2^16=65536未満の範囲から10, 100, 1000, 10000, 100000万個の数字を取り出し挿入と検索をそれぞれ行ってその実行時間を比較する。
まず、挿入プログラムとその実行時間は以下の通りである（Wandbox）。

import std/[sets, random, times, sequtils, math, sugar]
import std/typetraits

randomize()

proc chunked[S](s: openArray[S]; size: Positive): seq[seq[S]] = # Positive = range[1..high(int)] (system)
  collect(for i in 0..<ceilDiv(s.len, size): s[(i*size)..<min((i+1)*size, s.len)])

type Set = set[range[0..65535]] | HashSet[range[0..65535]] | OrderedSet[range[0..65535]] # 先に型をまとめないとvarを認識しない
proc measure(targets: (seq[int], seq[int]); set: var Set): array[0..1, int64] =
  var start = now(); 
  for i in targets[0]:
    set.incl(i)
  result[0] = (now() - start).inNanoseconds

  var flag = true;
  start = now();
  for i in targets[1]:
    flag = i in set
  result[1] = (now() - start).inNanoseconds

proc f(size, repeatTimes=10, findTimes: int=10) = # repeatTimes回行い平均を取る。検索処理はfindTimes回行う
  var 
    mySet    :        set[range[0..65535]]
    myHash   :    HashSet[range[0..65535]]
    myOrdered: OrderedSet[range[0..65535]]
  let 
    genTargets  = toSeq(1..repeatTimes*size).mapIt(rand(65535)).chunked(size)
    findTargets = toSeq(1..repeatTimes*findTimes).mapIt(rand(65535)).chunked(findTimes)
  # echo typetraits.name(type(items))
  # echo genTargets # 生成乱数列表示

  
  echo "set平均実行時間=", 
    zip(genTargets, findTargets).map(proc (targets: (seq[int], seq[int])): array[0..1, int64] = 
      mySet = {}
      measure(targets, myset)
    ).foldl([a[0]+b[0], a[1]+b[1]]).mapIt(cast[int](it)/repeatTimes) , "[ns]"

  echo "Hash平均実行時間=", 
    zip(genTargets, findTargets).map(proc (targets: (seq[int], seq[int])): array[0..1, int64] = 
      myHash = initHashSet[range[0..65535]]()
      measure(targets, myHash)
    ).foldl([a[0]+b[0], a[1]+b[1]]).mapIt(cast[int](it)/repeatTimes) , "[ns]"

  echo "OrderedSet平均実行時間=", 
    zip(genTargets, findTargets).map(proc (targets: (seq[int], seq[int])): array[0..1, int64] = 
      myOrdered = initOrderedSet[range[0..65535]]()
      measure(targets, myOrdered)
    ).foldl([a[0]+b[0], a[1]+b[1]]).mapIt(cast[int](it)/repeatTimes) , "[ns]\n"


for x in [10, 100, 1_000, 10_000, 100_000, 1_000_000]:
  f(x) # xの数分だけ要素を追加する

また、このプログラムから生成した実行時間をグラフ化したものを以下に示す。

集合への要素追加とそれに対する実行時間
setが圧倒的に早い。使用できる値に制限がある分高速化が可能なのだろう（縦軸を対数グラフにした方がいい気がしたが、やり方がわからなかった...）。

要素が追加済のsetに対する10個の要素の検索処理
集合なので検索速度は要素数に依存していないことを改めて確認できた。検索に関してはsetが異常に速いわけでもないようである。

追記：PackedSetも含めて実行したグラフを以下に示す。

各集合への要素追加とそれに対する実行処理
PackedSetも序数型のみという制限があるためか、HashSetらと比較して半分以下の実行時間で行うことができるようである。

要素が追加済のsetに対する10個の要素の検索処理
検索処理はどの集合であってもそこまでの影響しないことがわかった。

まとめ

setはsetsモジュールの集合と比べ処理速度が大きいことが確認できた（速度比較を行う範囲を0以上2^16未満としたため、そもそも土俵がset寄りだった気もする）。これからは、集合の要素が上記範囲内になることがわかっているのならばsetを積極的に使おうと思う。
追記：小さい範囲であれば良いが、0以上2^16未満などの大きな範囲であった場合は、メモリ消費と速度を比較してPackedSetとsetのどちらを使うかを吟味したいと思う。