Skip to content
This repository has been archived by the owner on Dec 20, 2021. It is now read-only.

Trieっぽい何か #2

Open
wx257osn2 opened this issue Jun 10, 2017 · 6 comments
Open

Trieっぽい何か #2

wx257osn2 opened this issue Jun 10, 2017 · 6 comments

Comments

@wx257osn2
Copy link

現状とりあえず仮組みしただけって感じなので変数名とかがメチャクチャ適当ですが…

class EmojiData
{
private:

	struct trie{
		std::unique_ptr<std::unordered_map<std::uint32_t, trie>> nexts;
		std::size_t t;
	};

	/* データセット (約 2000 種類の絵文字の codePoint 一覧) */
	const trie emojiCodePoints =
		[]{
		trie t = {std::make_unique<std::unordered_map<std::uint32_t, trie>>(), 0};
		const std::vector<std::vector<std::uint32_t>> vec = {
#include "EmojiCodePoints.txt"
		};
		trie* p;
		for(std::vector<std::uint32_t>::size_type j = 0; j != vec.size(); ++j){
			p = &t;
			for(std::vector<std::uint32_t>::size_type i = 0; i != vec[j].size(); ++i){
				if(!p->nexts)
					p->nexts = std::make_unique<std::unordered_map<std::uint32_t, trie>>();
				p = &(*p->nexts)[vec[j][i]];
			}
			p->t = vec[j].size();
		}
		return std::move(t);
	}();

public:

	EmojiData() = default;

	size_t check(std::vector<std::uint32_t>::const_iterator beg, std::vector<std::uint32_t>::const_iterator end)const
	{
		const trie* t = &emojiCodePoints;
		while(true){
			if(!t->nexts || beg == end)
				return std::size_t{t->t};
			auto it = t->nexts->find(*beg++);
			if(it == t->nexts->end())
				return std::size_t{t->t};
			t = &it->second;
		}

		return /**/0;
	}
};
  • メモリ効率はあんまり良くないと思います．サイズもそうですが，unique_ptrとunorderd_mapを組み合わせてるので断片化が激しそう…
    • バケットサイズとか指定すると多少は改善するかもしれないのでちょっといじります
  • 速度は速いです
    • 素直な実装(std::vector<std::vector<std::uint32_t>>を要素数で降順ソートかけたやつを上から総なめする)に比べると20倍ぐらい速い．初期化は3倍ぐらい遅いけど，使い方によっては誤差かなと思います．
@wx257osn2
Copy link
Author

wx257osn2 commented Jun 10, 2017 •
edited 

#include <unordered_map>
#include <memory>
#include <array>
class EmojiData
{
private:

	struct trie{
		std::unique_ptr<std::unordered_map<std::uint32_t, trie>> nexts;
		std::size_t length;
	};

	template<typename T, std::size_t N>
	static constexpr std::size_t size(T (&)[N])noexcept{return N;}
	template<typename T, std::size_t N>
	static constexpr std::size_t length(const std::array<T, N>& t)noexcept{
		auto n = N-1;
		while(n && t[n] == 0)
			--n;
		return n+1;
	}

	trie emojiCodePoints =
	[]{
		trie tri = {std::make_unique<std::unordered_map<std::uint32_t, trie>>(), 0};
		tri.nexts->reserve(1123+1); //激アドホック最適化 データセットが変わったらここは変えないといけない
		constexpr std::array<std::uint32_t, 7> arr[] = {
#include "EmojiCodePoints.txt"
		};
		trie* ptr;
		for(std::vector<std::uint32_t>::size_type j = 0; j != size(arr); ++j){
			ptr = &tri;
			const auto len = length(arr[j]);
			for(std::vector<std::uint32_t>::size_type i = 0; i != len; ++i){
				if(!ptr->nexts)
					ptr->nexts = std::make_unique<std::unordered_map<std::uint32_t, trie>>();
				ptr = &(*ptr->nexts)[arr[j][i]];
			}
			ptr->length = len;
		}
		return std::move(tri);
	}();

public:

	EmojiData() = default;

	size_t check(std::vector<std::uint32_t>::const_iterator beg, std::vector<std::uint32_t>::const_iterator end)const
	{
		const trie* ptr = &emojiCodePoints;
		while(true){
			if(beg == end)
				break;
			auto it = ptr->nexts->find(*beg++);
			if(it == ptr->nexts->end())
				break;
			ptr = &it->second;
			if(!ptr->nexts)
				break;
		}
		return ptr->length;
	}
};
  • 速度を改善しました
    • 素直な実装に比べて初期化が1.1倍遅い程度でチェックの速度が40倍ぐらいいくので速度は十分かなと思います
    • ちなみに中途半端に std::array を使ったりRange-based forを使ってなかったりするのは大体MSVCのオプティマイザのご機嫌取りです
  • メモリ効率はもうこの実装だと諦めるしか無い気がします
    • 普通に書くとどうやっても unordered_map のrehashでメモリを再確保するので…
      • 一応トップレベルの unordered_map については reserve で再確保を抑えてみましたが，子要素までくると中々難しいところがあります

@wx257osn2
Copy link
Author

メモリについては，EmojiData を生成しない何もしないプログラムが408KB，
ナイーブなソート済みvectorのやつが704KB(+296KB)，2つ目に挙げた実装が812KB(+404KB)でした

以下の実装が間を取ってメモリ使用量を728KB(+320KB)に抑えたものになります
速度は2つ目の実装と比べて初期化が僅かに速く，チェックが1.8倍ぐらい遅いですが1マイクロ秒は切ります
マジックナンバーが増えて汚いですが…

とりあえず速度優先とメモリ優先で2案ということで，どうでしょう．

#include <unordered_map>
#include <memory>
#include <array>
class EmojiData
{
private:

	struct trie{
		std::unique_ptr<std::unordered_map<std::uint32_t, trie>> nexts;
		std::size_t length;
	};

	template<typename T, std::size_t N>
	static constexpr std::size_t size(T (&)[N])noexcept{return N;}
	template<typename T, std::size_t N>
	static constexpr std::size_t length(const std::array<T, N>& t)noexcept{
		auto n = N-1;
		while(n && t[n] == 0)
			--n;
		return n+1;
	}

	trie trieHead;
	std::array<std::uint32_t, 1053> emojiCodePointLength1;

public:

	EmojiData():trieHead{std::make_unique<std::unordered_map<std::uint32_t, trie>>(), 0}{
		trieHead.nexts->reserve(123+1);
		constexpr std::array<std::uint32_t, 7> arr[] = {
#include "EmojiCodePoints.txt"
		};
		auto length1 = emojiCodePointLength1.begin();
		trie* ptr;
		for(std::vector<std::uint32_t>::size_type j = 0; j != size(arr); ++j){
			const auto len = length(arr[j]);
			if(len == 1){
				*length1++ = arr[j][0];
				continue;
			}
			ptr = &trieHead;
			for(std::vector<std::uint32_t>::size_type i = 0; i != len; ++i){
				if(!ptr->nexts)
					ptr->nexts = std::make_unique<std::unordered_map<std::uint32_t, trie>>();
				ptr = &(*ptr->nexts)[arr[j][i]];
			}
			ptr->length = len;
		}
		std::sort(emojiCodePointLength1.begin(), emojiCodePointLength1.end());
		for(auto&& x : emojiCodePointLength1){
			auto it = trieHead.nexts->find(x);
			if(it != trieHead.nexts->end())
				it->second.length = 1;
		}
	}

	size_t check(std::vector<std::uint32_t>::const_iterator beg, std::vector<std::uint32_t>::const_iterator end)const
	{
		const trie* ptr = &trieHead;
		if(beg == end)
			return 0;
		auto it = ptr->nexts->find(*beg);
		if(it == ptr->nexts->end())
			return std::binary_search(emojiCodePointLength1.begin(), emojiCodePointLength1.end(), *beg) ? 1 : 0;
		ptr = &it->second;
		if(!ptr->nexts)
			return ptr->length;
		++beg;
		while(beg != end){
			auto it = ptr->nexts->find(*beg);
			if(it == ptr->nexts->end())
				break;
			ptr = &it->second;
			if(!ptr->nexts)
				break;
			++beg;
		}

		return ptr->length;
	}
};

@Reputeless
Copy link
Member

Reputeless commented Jun 11, 2017 •
edited

複数の手法の検討と実測値の調査をありがとうございます。
標準ライブラリの範囲でコンパクトな実装になっている点が嬉しいです。
マジックナンバーはメンテナンス性の観点から避けたいのが本音です。

やはり #1 のコメントにもあるように、性能を限界まで追求すると std::map や std::unordered_map よりも省メモリでキャッシュ効率の良いデータ構造が必要になるでしょう。
ただ、それでコードが長く複雑になってしまうのは少しオーバースペック感もあり、性能向上とのバランスを見極めたいところです。

@wx257osn2
Copy link
Author

wx257osn2 commented Jun 11, 2017 •
edited

マジックナンバーは基本的に unordered_map のrehash回避と vector を array で代用して動的メモリ確保を減らすことを目的に使っていて，
これは EmojiCodePoints.txt を実際に読んで unorderd_map とか vector に突っ込んだときの要素数をぺちぺち打ち込んでるだけなので，

  • rehash/reallocateによるメモリの断片化が許容できる程度なら特に必要ない
    (若干初期化時の速度が鈍るでしょうが，おそらく許容範囲内だと思います)
  • 個人的には(EmojiCodePoints.txtの更新頻度にもよりますが)そこまでコストが増えるほどでもないかなぁという印象
    • どこまでが「データセット」(前処理の範疇)なのか，という話になりそう
    • あれ？コンパイル時に導出できればよいのでは…？(コードは複雑化しますが)

という感じです．
EmojiCodePoints.txt の生成タイミングでEmojiDataのコンストラクタ相当の処理をしてsize()の値を吐き出しておけばほぼ自動化も可能だと思います．

@wx257osn2
Copy link
Author

wx257osn2 commented Jun 11, 2017 •
edited

というわけでコンパイル時にほぼすべてのマジックナンバーになってた部分を導出してみました
やはり実装がゴタゴタしてしまいますが…

どちらのコードも残るマジックナンバーは「EmojiDataHelper::LongestCodePointLength」ですが，これもコンパイルが通る程度に大きい値にすれば良いというだけで，足りなければコンパイルエラーが出るのでその都度最小の数に設定し直すだけですし，最悪将来を見越して10とか20とかにしてしまえば実質メンテフリーです(その場合バイナリサイズと初期化時のスタックが若干多目に消費されるようになると思いますが，EmojiDataオブジェクト生成後のメモリ消費は変わらないはずです)

#include <unordered_map>
#include <memory>
#include <array>

class EmojiDataHelper{
	friend class EmojiData;

	static constexpr std::size_t LongestCodePointLength = 7;

	template<typename T, std::size_t N>
	static constexpr std::size_t size(T (&)[N])noexcept{return N;}
	template<typename T, std::size_t N>
	static constexpr std::size_t length(const std::array<T, N>& t)noexcept{
		auto n = N-1;
		while(n && t[n] == 0)
			--n;
		return n+1;
	}
	static constexpr std::size_t codePointsNum()noexcept{
		constexpr std::array<std::uint32_t, LongestCodePointLength> arr[] = {
//#include "EmojiCodePoints.txt"
#include "EmojiCodePoints_sortedByValue.txt"
		};
		return size(arr);
	}
	template<std::size_t N = codePointsNum()>
	static constexpr std::array<std::array<std::uint32_t, LongestCodePointLength>, N> emojiCodePoints(){
		return{{
//#include "EmojiCodePoints.txt"
#include "EmojiCodePoints_sortedByValue.txt"
		}};
	}
	static constexpr std::size_t trieHeadSize(){
		constexpr auto arr = emojiCodePoints();
		std::uint32_t prev = 0;
		std::uint32_t count = 1;
		for(std::size_t i = 0; i != arr.size()-1/*for last comma*/; ++i){
			const auto len = length(arr[i]);
			if(prev == 0){
				prev = arr[i][0];
				continue;
			}
			if(prev != arr[i][0]){
				prev = arr[i][0];
				++count;
			}
		}
		return count;
	}
};

class EmojiData
{
private:

	struct trie{
		std::unique_ptr<std::unordered_map<std::uint32_t, trie>> nexts;
		std::size_t length;
	};

	template<typename T, std::size_t N>
	static constexpr std::size_t size(T (&)[N])noexcept{return N;}
	template<typename T, std::size_t N>
	static constexpr std::size_t length(const std::array<T, N>& t)noexcept{
		auto n = N-1;
		while(n && t[n] == 0)
			--n;
		return n+1;
	}

	trie emojiCodePoints =
	[]{
		trie tri = {std::make_unique<std::unordered_map<std::uint32_t, trie>>(), 0};
		tri.nexts->reserve(EmojiDataHelper::trieHeadSize()+1/*workaround*/);
		constexpr auto arr = EmojiDataHelper::emojiCodePoints();
		trie* ptr;
		for(std::size_t j = 0; j != arr.size()-1/*for last comma*/; ++j){
			ptr = &tri;
			const auto len = length(arr[j]);
			for(std::size_t i = 0; i != len; ++i){
				if(!ptr->nexts)
					ptr->nexts = std::make_unique<std::unordered_map<std::uint32_t, trie>>();
				ptr = &(*ptr->nexts)[arr[j][i]];
			}
			ptr->length = len;
		}
		return std::move(tri);
	}();

public:

	EmojiData() = default;

	size_t check(std::vector<std::uint32_t>::const_iterator beg, std::vector<std::uint32_t>::const_iterator end)const
	{
		const trie* ptr = &emojiCodePoints;
		while(beg != end){
			auto it = ptr->nexts->find(*beg);
			if(it == ptr->nexts->end())
				break;
			ptr = &it->second;
			if(!ptr->nexts)
				break;
			++beg;
		}
		return ptr->length;
	}
};
class EmojiDataHelper{
	friend class EmojiData;

	static constexpr std::size_t LongestCodePointLength = 7;

	template<typename T, std::size_t N>
	static constexpr std::size_t size(T (&)[N])noexcept{return N;}
	template<typename T, std::size_t N>
	static constexpr std::size_t length(const std::array<T, N>& t)noexcept{
		auto n = N-1;
		while(n && t[n] == 0)
			--n;
		return n+1;
	}
	static constexpr std::size_t codePointsNum()noexcept{
		constexpr std::array<std::uint32_t, LongestCodePointLength> arr[] = {
//#include "EmojiCodePoints.txt"
#include "EmojiCodePoints_sortedByValue.txt"
		};
		return size(arr);
	}
	template<std::size_t N = codePointsNum()>
	static constexpr std::array<std::array<std::uint32_t, LongestCodePointLength>, N> emojiCodePoints(){
		return{{
//#include "EmojiCodePoints.txt"
#include "EmojiCodePoints_sortedByValue.txt"
		}};
	}
	static constexpr std::size_t trieHeadSize(){
		constexpr auto arr = emojiCodePoints();
		std::uint32_t prev = 0;
		std::uint32_t count = 1;
		for(std::size_t i = 0; i != arr.size()-1/*for last comma*/; ++i){
			const auto len = length(arr[i]);
			if(len == 1)
				continue;
			if(prev == 0){
				prev = arr[i][0];
				continue;
			}
			if(prev != arr[i][0]){
				prev = arr[i][0];
				++count;
			}
		}
		return count;
	}
	static constexpr std::size_t length1Size(){
		constexpr auto arr = emojiCodePoints();
		std::uint32_t count = 0;
		for(std::size_t i = 0; i != arr.size()-1/*for last comma*/; ++i)
			if(length(arr[i]) == 1)
				++count;
		return count;
	}
};

class EmojiData
{
private:

	struct trie{
		std::unique_ptr<std::unordered_map<std::uint32_t, trie>> nexts;
		std::size_t length;
	};

	trie trieHead;
	std::array<std::uint32_t, EmojiDataHelper::length1Size()> emojiCodePointLength1;

public:

	EmojiData():trieHead{std::make_unique<std::unordered_map<std::uint32_t, trie>>(), 0}{
		static constexpr auto trieHeadSize = EmojiDataHelper::trieHeadSize();
		trieHead.nexts->reserve(trieHeadSize+1/*workaround*/);
		constexpr auto arr = EmojiDataHelper::emojiCodePoints();
		auto length1 = emojiCodePointLength1.begin();
		trie* ptr;
		for(std::size_t j = 0; j != arr.size()-1/*for last comma*/; ++j){
			const auto len = EmojiDataHelper::length(arr[j]);
			if(len == 1){
				*length1++ = arr[j][0];
				continue;
			}
			ptr = &trieHead;
			for(std::size_t i = 0; i != len; ++i){
				if(!ptr->nexts)
					ptr->nexts = std::make_unique<std::unordered_map<std::uint32_t, trie>>();
				ptr = &(*ptr->nexts)[arr[j][i]];
			}
			ptr->length = len;
		}
		//std::sort(emojiCodePointLength1.begin(), emojiCodePointLength1.end());
		for(auto&& x : emojiCodePointLength1){
			auto it = trieHead.nexts->find(x);
			if(it != trieHead.nexts->end())
				it->second.length = 1;
		}
	}

	size_t check(std::vector<std::uint32_t>::const_iterator beg, std::vector<std::uint32_t>::const_iterator end)const
	{
		const trie* ptr = &trieHead;
		if(beg == end)
			return 0;
		auto it = ptr->nexts->find(*beg);
		if(it == ptr->nexts->end())
			return std::binary_search(emojiCodePointLength1.begin(), emojiCodePointLength1.end(), *beg) ? 1 : 0;
		ptr = &it->second;
		if(!ptr->nexts)
			return ptr->length;
		++beg;
		while(beg != end){
			auto it = ptr->nexts->find(*beg);
			if(it == ptr->nexts->end())
				break;
			ptr = &it->second;
			if(!ptr->nexts)
				break;
			++beg;
		}

		return ptr->length;
	}
};

@Reputeless Reputeless mentioned this issue Jun 27, 2017
Open
@Reputeless
Copy link
Member

ご提案いただいた #2 と #1 を検証のため OpenSiv3D v0.1.6 以降に実装します。
最終的にどちらを使用するかは今後判断させていただきます。
追って経過を報告するため、Close せず残しておきます。

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@wx257osn2 @Reputeless