D言語で使われているデータ構造・アルゴリズム

atof/ftoa相当や正規表現まわりのコードをざっくり読んでて、phobosとかで使われてるアルゴリズムってどんなのがあるっけというのをまとめてみた。主に、というかだいたい標準ライブラリで超雑なまとめです。

std.algorithm

• Boyer-Moore法(std.algorithm.searching.boyerMooreFinder)
• IntroSort(std.algorithm.sorting.sort!unstable)
• TimSort(std.algorithm.sorting.sort!stable)
• レーヴェンシュタイン距離(std.algorithm.comparison.levenshteinDistance)

std.bigint

• Karatsuba法(乗算)

std.container

• 赤黒木(std.container.rbtree)

std.conv

• naive float parsing algorithm (std.conv.parse)

上のアルゴリズムをざっくり解読したもの: https://gist.github.com/kubo39/3aa53f0661dd645f1f0f7d3fef62b5c6

std.format

• naive ftoa algorithm (std.format.internal.floats)

ナイーブな処理とか、他の言語で使われてるアルゴリズムとか:

kubo39.hatenablog.com

std.mathspecial

• ガンマ関数(std.mathspecial.gamma)

std.random

• メルセンヌ・ツイスター法
• XorShift

std.regex

• Shift-Orアルゴリズム(kickstart engine)
• Thompson NFA(Pike VM)
• バックトラック法

後半のほうで少しDのregexの処理を追っている: https://gist.github.com/kubo39/78eb0fbc770aeeba5f7c7126b5a85214

core.bitop

• 分割統治法(core.bitop.popcnt)