LRUキャッシュで頻繁にアクセスするデータの検索時間を短くしたい

はじめに

LRUキャッシュであまり使わないデータにヒットすると、先頭にきてしまうのがちょっと・・・。という場合に、ヒット頻度が高いデータだけが前半に集まるかも？

解説

先頭からヒットした距離の半分だけ優先度をアップさせます。

ソース

main.cpp

//---------------------------------------------------------------------------
#include <list>
#include <iostream>
#include <stdexcept>

//---------------------------------------------------------------------------
// ハーフジャンプキャッシュリストクラス
template<typename Tkey, typename Titem>
class TCacheList : public std::list< std::pair<Tkey, Titem> >
{
public:
	using value_type = std::pair<Tkey, Titem>;
	using self = std::list<value_type>;
	using iterator = typename self::iterator;

public:
	inline iterator find(const Tkey &key)
	{
		for ( iterator i = this->begin(); i != this->end(); ++i )
		{
			if ( i->first == key ) return i;
		}
		return this->end();
	}

	inline iterator erase(const Tkey &key)
	{
		return self::erase( find( key ) );
	}

	inline Titem& Pickup(const Tkey &key)
	{
		int count = 0;
		iterator half_index = this->begin();
		for ( iterator i = this->begin(); i != this->end(); ++i )
		{
			if ( i->first == key )
			{
				// ヒットした所から半分の場所に挿入する
				this->splice( half_index, *this, i );
				return i->second;
			}
			
			if ( count & 1 ) ++half_index;
			++count;
		}
		throw std::runtime_error( "No Item." );
	}
};

using TCashFile = TCacheList< std::string, std::string >;

//---------------------------------------------------------------------------
void print(const TCashFile &list)
{
	for (const auto &i : list)
		std::cout << i.first << " : " << i.second << std::endl;
	std::cout << "--------" << std::endl;
}

//---------------------------------------------------------------------------
int main(int argc, char** argv)
{
	TCashFile cache_file;

	for ( int i = 0; i < 10; ++i )
	{
		// 追加する場合は先頭に
		std::string file_name = "file_" + std::to_string(i) + ".txt";
		cache_file.push_front( TCashFile::value_type( file_name, "data") );
	}
	print( cache_file );

	// 見つけたら半分ずつ上がっていく
	std::string data = cache_file.Pickup("file_1.txt");
	print( cache_file );
	data = cache_file.Pickup("file_1.txt");
	print( cache_file );
	data = cache_file.Pickup("file_1.txt");
	print( cache_file );
	data = cache_file.Pickup("file_1.txt");
	print( cache_file );

	try {
		data = cache_file.Pickup("file_X.txt");
	} catch(...) {
		// ヒットしない場合は好みで先頭か最後尾に追加
		//cache_file.push_front( TCashFile::value_type( "file_X.txt", "data") );
		cache_file.push_back( TCashFile::value_type( "file_X.txt", "data") );
	}

	// キャッシュが大きい場合は消したり
	cache_file.resize( 10 );

	print( cache_file );

	return 0;
}

//---------------------------------------------------------------------------

出力

file_9.txt : data
file_8.txt : data
file_7.txt : data
file_6.txt : data
file_5.txt : data
file_4.txt : data
file_3.txt : data
file_2.txt : data
file_1.txt : data
file_0.txt : data
--------
file_9.txt : data
file_8.txt : data
file_7.txt : data
file_6.txt : data
file_1.txt : data
file_5.txt : data
file_4.txt : data
file_3.txt : data
file_2.txt : data
file_0.txt : data
--------
file_9.txt : data
file_8.txt : data
file_1.txt : data
file_7.txt : data
file_6.txt : data
file_5.txt : data
file_4.txt : data
file_3.txt : data
file_2.txt : data
file_0.txt : data
--------
file_9.txt : data
file_1.txt : data
file_8.txt : data
file_7.txt : data
file_6.txt : data
file_5.txt : data
file_4.txt : data
file_3.txt : data
file_2.txt : data
file_0.txt : data
--------
file_1.txt : data
file_9.txt : data
file_8.txt : data
file_7.txt : data
file_6.txt : data
file_5.txt : data
file_4.txt : data
file_3.txt : data
file_2.txt : data
file_0.txt : data
--------
file_X.txt : data
file_1.txt : data
file_9.txt : data
file_8.txt : data
file_7.txt : data
file_6.txt : data
file_5.txt : data
file_4.txt : data
file_3.txt : data
file_2.txt : data
--------

「file_1.txt」にヒットする度、優先度が半分ずつ上がっています。

参考にしたサイト