sile · June 26, 2024 12:38
diff --git a/0_succ_bp.md b/0_succ_bp.md
diff --git a/download-wikipedia-titiles.sh b/download-wikipedia-titiles.sh
 #! /bin/bash
 #
 # NOTE:
 # - Wikipedia Language List: https://en.wikipedia.org/wiki/List_of_Wikipedias

 TITLE_FILE=/tmp/wikipedia.titles
 set -e

 rm -f $TITLE_FILE

 for lang in {en,sv,ceb,de,nl,fr,ru,it,es,war}
 do
    echo "# LANG: ${lang}"
    URL=https://dumps.wikimedia.org/${lang}wiki/latest/${lang}wiki-latest-all-titles-in-ns0.gz
    echo $URL
    curl -f $URL | gunzip >> $TITLE_FILE
 done

 LC_ALL=C sort $TITLE_FILE -uo $TITLE_FILE
diff --git a/set_build.sh b/set_build.sh
 # 環境:
 # - OS: Ubuntu-16.4
 # - メモリ: 6GB
 # - CPU: Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz x 2
 # - Rust: 1.11.0
 # - succ: tag=0.0.1 (ソースファイル: https://github.com/sile/succ/blob/master/examples/set_build.rs)


 # 入力データは`/tmp/wikipedia.titles`に配置されているものとする
 $ wc -l /tmp/wikipedia.titles
 29495185 /tmp/wikipedia.titles

 $ du -h /tmp/wikipedia.titles
 672M    /tmp/wikipedia.titles


 # ビルド
 $ git clone [email protected]:sile/succ
 $ cd succ/
 $ cargo build --release --example set_build


 # a) 入力データの走査に要する時間の計測
 $ /usr/bin/time -v cargo run --release --example set_build -- --type null < /tmp/wikipedia.titles
 Running `target/release/examples/set_build --type null`
  Command being timed: "cargo run --release --example set_build -- --type null"
  User time (seconds): 4.90
  System time (seconds): 0.16
  Percent of CPU this job got: 98%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.13  # 所要時間
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 48256  # 使用メモリ
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 0
  Minor (reclaiming a frame) page faults: 7248
  Voluntary context switches: 59
  Involuntary context switches: 302
  Swaps: 0
  File system inputs: 0
  File system outputs: 0
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 0


 # b) ハッシュテーブルの構築コスト計測
 $ /usr/bin/time -v cargo run --release --example set_build -- --type hashset < /tmp/wikipedia.titles
 Running `target/release/examples/set_build --type hashset`
  Command being timed: "cargo run --release --example set_build -- --type hashset"
  User time (seconds): 20.81
  System time (seconds): 4.07
  Percent of CPU this job got: 98%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 0:25.15  # 所要時間
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 2030872  # 使用メモリ
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 124
  Minor (reclaiming a frame) page faults: 649314
  Voluntary context switches: 348
  Involuntary context switches: 1067
  Swaps: 0
  File system inputs: 502536
  File system outputs: 0
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 0


 # c) ソート配列の構築コスト計測
 $ /usr/bin/time -v cargo run --release --example set_build -- --type sortarray < /tmp/wikipedia.titles
 Running `target/release/examples/set_build --type sortarray`
  Command being timed: "cargo run --release --example set_build -- --type sortarray"
  User time (seconds): 2.65
  System time (seconds): 0.64
  Percent of CPU this job got: 98%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.34  # 所要時間
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 1054300  # 使用メモリ
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 0
  Minor (reclaiming a frame) page faults: 10504
  Voluntary context switches: 63
  Involuntary context switches: 203
  Swaps: 0
  File system inputs: 0
  File system outputs: 0
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 0


 # d) Balanced Parenthesesによるトライ木の構築コスト計測
 $ /usr/bin/time -v cargo run --release --example set_build -- --type parentheses < /tmp/wikipedia.titles
 Running `target/release/examples/set_build --type parentheses`
 NODES: 283832153  # トライ木のノード数
 BYTES: 422445483  # 構築後に必要なバイト数
  Command being timed: "cargo run --release --example set_build -- --type parentheses"
  User time (seconds): 9.40
  System time (seconds): 0.30
  Percent of CPU this job got: 99%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 0:09.80  # 所要時間
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 628716  # 使用メモリ
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 0
  Minor (reclaiming a frame) page faults: 9066
  Voluntary context switches: 61
  Involuntary context switches: 374
  Swaps: 0
  File system inputs: 0
  File system outputs: 0
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 0


 # 要素検索
 $ cargo run --release --example set_find < /tmp/wikipedia.titles 
 Running `target/release/examples/set_find`
  HashSet: Duration { secs: 0, nanos: 437 } (avg)
  BinSearch: Duration { secs: 0, nanos: 419 } (avg)
  Parentheses: Duration { secs: 0, nanos: 65059 } (avg)
diff --git a/sortarray.png b/sortarray.png
	所要時間	使用メモリ	備考
a) 深さ優先探索のみ	5.13秒	48MB
b) ハッシュテーブル	25.15秒	2,030MB
c) 入力データ+先頭位置の配列	3.34秒	1,054MB	使用メモリ(おおよそ): `入力文字列 + 32bit * キー数`
d) Balanced Parentheses	9.80秒	628MB	構築完了後に必要な領域は`402MB`
	平均検索時間	備考
b) ハッシュテーブル	437ナノ秒
c) 入力データ+先頭位置の配列	419ナノ秒	要するに二分探索の性能
d) Balanced Parentheses	65,059ナノ秒	未最適化 (ちゃんと実装すれば一桁くらいは速くなりそう?)
	ノード数	ラベル部分のサイズ	全体サイズ
トライ(BP)	283,832,153	270MB	402MB
パトリシア(BP)	50,579,914	77MB	252MB
	#! /bin/bash
	#
	# NOTE:
	# - Wikipedia Language List: https://en.wikipedia.org/wiki/List_of_Wikipedias

	TITLE_FILE=/tmp/wikipedia.titles
	set -e

	rm -f $TITLE_FILE

	for lang in {en,sv,ceb,de,nl,fr,ru,it,es,war}
	do
	echo "# LANG: ${lang}"
	URL=https://dumps.wikimedia.org/${lang}wiki/latest/${lang}wiki-latest-all-titles-in-ns0.gz
	echo $URL
	curl -f $URL \| gunzip >> $TITLE_FILE
	done

	LC_ALL=C sort $TITLE_FILE -uo $TITLE_FILE
	# 環境:
	# - OS: Ubuntu-16.4
	# - メモリ: 6GB
	# - CPU: Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz x 2
	# - Rust: 1.11.0
	# - succ: tag=0.0.1 (ソースファイル: https://github.com/sile/succ/blob/master/examples/set_build.rs)


	# 入力データは`/tmp/wikipedia.titles`に配置されているものとする
	$ wc -l /tmp/wikipedia.titles
	29495185 /tmp/wikipedia.titles

	$ du -h /tmp/wikipedia.titles
	672M /tmp/wikipedia.titles


	# ビルド
	$ git clone [email protected]:sile/succ
	$ cd succ/
	$ cargo build --release --example set_build


	# a) 入力データの走査に要する時間の計測
	$ /usr/bin/time -v cargo run --release --example set_build -- --type null < /tmp/wikipedia.titles
	Running `target/release/examples/set_build --type null`
	Command being timed: "cargo run --release --example set_build -- --type null"
	User time (seconds): 4.90
	System time (seconds): 0.16
	Percent of CPU this job got: 98%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.13 # 所要時間
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 48256 # 使用メモリ
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 7248
	Voluntary context switches: 59
	Involuntary context switches: 302
	Swaps: 0
	File system inputs: 0
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0


	# b) ハッシュテーブルの構築コスト計測
	$ /usr/bin/time -v cargo run --release --example set_build -- --type hashset < /tmp/wikipedia.titles
	Running `target/release/examples/set_build --type hashset`
	Command being timed: "cargo run --release --example set_build -- --type hashset"
	User time (seconds): 20.81
	System time (seconds): 4.07
	Percent of CPU this job got: 98%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:25.15 # 所要時間
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 2030872 # 使用メモリ
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 124
	Minor (reclaiming a frame) page faults: 649314
	Voluntary context switches: 348
	Involuntary context switches: 1067
	Swaps: 0
	File system inputs: 502536
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0


	# c) ソート配列の構築コスト計測
	$ /usr/bin/time -v cargo run --release --example set_build -- --type sortarray < /tmp/wikipedia.titles
	Running `target/release/examples/set_build --type sortarray`
	Command being timed: "cargo run --release --example set_build -- --type sortarray"
	User time (seconds): 2.65
	System time (seconds): 0.64
	Percent of CPU this job got: 98%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.34 # 所要時間
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 1054300 # 使用メモリ
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 10504
	Voluntary context switches: 63
	Involuntary context switches: 203
	Swaps: 0
	File system inputs: 0
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0


	# d) Balanced Parenthesesによるトライ木の構築コスト計測
	$ /usr/bin/time -v cargo run --release --example set_build -- --type parentheses < /tmp/wikipedia.titles
	Running `target/release/examples/set_build --type parentheses`
	NODES: 283832153 # トライ木のノード数
	BYTES: 422445483 # 構築後に必要なバイト数
	Command being timed: "cargo run --release --example set_build -- --type parentheses"
	User time (seconds): 9.40
	System time (seconds): 0.30
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:09.80 # 所要時間
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 628716 # 使用メモリ
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 9066
	Voluntary context switches: 61
	Involuntary context switches: 374
	Swaps: 0
	File system inputs: 0
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0


	# 要素検索
	$ cargo run --release --example set_find < /tmp/wikipedia.titles
	Running `target/release/examples/set_find`
	HashSet: Duration { secs: 0, nanos: 437 } (avg)
	BinSearch: Duration { secs: 0, nanos: 419 } (avg)
	Parentheses: Duration { secs: 0, nanos: 65059 } (avg)