spica - npm Package Compare versions

Comparing version 0.0.797 to 0.0.798

cache.ts

		@@ -65,3 +65,3 @@ import { max, min } from './alias';
		TinyLFU:
		TinyLFUはキーのポインタのアドレスでブルームフィルタを生成するためJavaScriptでは
		TinyLFUはキーの数値またはポインタのアドレスでブルームフィルタを生成するためJavaScriptでは
		文字列やオブジェクトなどからアドレスを取得または代替値を高速に割り当てる方法がなく汎用的に使用できない。
		@@ -68,0 +68,0 @@ 乱数で代用する方法は強引で低速だがリモートアクセスなど低速な処理では償却可能と思われる。

package.json

		{
		"name": "spica",
		"version": "0.0.797",
		"version": "0.0.798",
		"description": "Supervisor, Coroutine, Channel, select, AtomicPromise, Cancellation, Cache, List, Queue, Stack, and some utils.",
		@@ -5,0 +5,0 @@ "private": false,

tlru.ts

		// TLRU: True LRU
		// TRC: True Recency-based Cache

		export * from './tlru.clock';

		/*
		@@ -19,2 +21,47 @@ 真に最近性に基づく真のLRU。

		export * from './tlru.clock';
		/*
		LRUとClockは偽の最近性に基づく誤ったアルゴリズムにより性能が大幅に低下する。
		真の最近性は偽の最近性よりも非常に優れている。

		エントリ間の最近性関係には使用済みと使用済み、使用済みと未使用、未使用と未使用の3種類がある。
		ただしLRUとClockは一部の最近性に違反する。真のLRUはすべての最近性を維持することにより
		LRUとClockよりも優れた性能を発揮する。

		LRUの根本的誤りは新しいエントリを最近使用されたと見なすことである。実際それがキャッシュ内で
		使用されたことはない。従って新しいエントリは実際に使用されたエントリの後ろに追加する必要がある。

		```
		Sequence: 1, 2, 3, 3, 2, 4

		LRU

		MRU \|4 2 3 1\| LRU
		Hit \|0 1 1 0\|
		^ Violation of the recency between used and unused.

		Clock

		N-1 \|4 3 2 1\| 0
		Hit \|0 1 1 0\|
		^ Violation of the recency between used and used.

		True LRU

		MRU \|2 3 4 1\| LRU
		Hit \|1 1 0 0\|
		^ ^ ^ Ideal recency.
		```

		再利用距離と同様に未使用と使用済みの最近性には無限と有限の差があり差を埋める方法には
		様々な方法が考えられる。

		True LRUにおけるLRUからの大幅な改善はすべてのアルゴリズムの改善の過半が未使用のエントリを
		偶然削除したことによるものを独自の改善として混同および錯覚したものであり各アルゴリズムの
		独自性による改善は小さいか半分に満たないことを示している。True LRUをLRUの代わりに真の
		ベースラインとすると他のアルゴリズムは特に汎用性においてあまり魅力的な性能を達成していない。

		なおClockはLRUの近似アルゴリズムとして知られているがLRUとClockは異なる種類の最近性に基づく
		アルゴリズムであるためClockは実際にはLRUの近似アルゴリズムではなく異なる種類の最近性に基づく
		まったく異なる最近性基準アルゴリズムである。

		*/

spica - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics