2022/10/08 16:27

データ量の多い stream や generator で最後の N 個を取得する

カテゴリ:: JavaScript

コメント数:: Comments: 0

タグ：: JavaScript; ベンチマーク

◆ 最後まで取得していくしかない
◆ 配列に入れるときに全部を入れるとデータが多いときにムダも多い
◆ 最後の N 個だけ残す方法
◆ push して shift は普通
◆ unshift して length で N 以降捨てるのは意外と遅い
◆ 使いまわしてインデックスをループさせながら上書きが速いけどちょっと面倒

配列なら

array.slice(-10)

で最後の 10 件のように取得できます

しかし stream や generator ではこのようにはできません
同じようにやる場合は

const arr = []

for await (const value of stream) {
	arr.push(value)
}

arr.slice(-10)

や

const arr = []

for (const value of generateor()) {
	arr.push(value)
}

arr.slice(-10)

みたいなことが必要です
この方法だと全部を配列の中に入れます
最後の一部しかいらないのに全部を保持してもムダです
特に取得するデータが多い場合はメモリ量的にも心配があります

なのでムダなく必要な個数分だけを配列に入れるようにします
もちろんデータが小さいならこんな細かなことは気にせず楽に書けるように配列に全部入れてしまえば良いです
なので対象は大きなデータを扱うときです
となるとパフォーマンス的にも優れる方法にしたいです

思いつくのはこんなのですがどれが一番優れるのでしょうか

// (1)
const arr = Array(10)
for (const value of values) {
	arr.push(value)
	arr.shift()
}

// (2)
const arr = Array(10)
for (const value of values) {
	arr.unshift()
	arr.length = 10
}
arr.reverse()

// (3)
const arr = Array(10)
let ptr = 0
for (const value of values) {
	arr[ptr] = value
	ptr = (ptr + 1) % 10
}
arr.slice(ptr).concat(arr.slice(0, ptr))

(1) はシンプルに最後に push して最初のを shift で捨てます
追加して捨ててなのでパフォーマンス的には優れてそうには見えません

(2) は逆に配列の最初に要素を追加して捨てるのは length の指定にしています
取得するための機能の shift や pop よりは速いかもくらいの気持ちで試しています
最後には逆順に戻す reverse が必要です

(3) は最初に確保した固定の場所を使いまわします
インデックスの数値を変えながら配列の長さでループして一番古いのを上書きしていきます
実装は少し複雑化しますが効率では一番良さそうに思います
最後には古い順になるように一工夫が必要です

(2), (3) は追加の処理が最後に必要ですが最後の一回きりなのでループ回数が多ければ誤差程度でしょう

実際にどれくらい違うのか調べてみました

<!DOCTYPE html>
<meta charset="utf-8" />

<script type="module">
	const main = () => {
		const values = Array.from(Array(100000), (_, index) => index)

		const fn1 = () => {
			const arr = Array(10)
			for (const value of values) {
				arr.push(value)
				arr.shift()
			}
			return arr
		}

		const fn2 = () => {
			const arr = Array(10)
			for (const value of values) {
				arr.unshift(value)
				arr.length = 10
			}
			return arr.reverse()
		}

		const fn3 = () => {
			const arr = Array(10)
			let ptr = 0
			for (const value of values) {
				arr[ptr] = value
				ptr = (ptr + 1) % 10
			}
			return arr.slice(ptr).concat(arr.slice(0, ptr))
		}

		console.log(fn1(), fn2(), fn3())

		const result = measure([fn1, fn2, fn3], 1000, 80)

		document.querySelector("pre").textContent = JSON.stringify(result, null, "  ")
	}

	const measure = (fns, measure_count, effective_rate) => {
		const data = []

		for (let i = 0; i < measure_count; i++) {
			for (const [fn_index, fn] of fns.entries()) {
				if (!data[fn_index]) {
					data[fn_index] = []
				}

				const start = performance.now()
				fn()
				const end = performance.now()
				data[fn_index].push(end - start)
			}
		}

		return data.map((fn_data, fn_index) => {
			return {
				name: fns[fn_index].name,
				...agg(fn_data, effective_rate),
			}
		})
	}

	const agg = (data, effective_rate) => {
		const sorted = data.sort((a, b) => a - b)
		const max = sorted.at(-1)
		const times = getEffective(sorted, effective_rate)
		const num = times.length
		const range = [times[0], times.at(-1)]
		const avg = times.reduce((a, b) => a + b, 0) / num
		const med = num % 2 === 0 ? ((times[num / 2] + times[num / 2 - 1]) / 2) : times[~~(num / 2)]
		return { range, max, avg, med, num }
	}

	const getEffective = (data, rate) => {
		const fixed_rate = Math.max(0, Math.min(100, rate))
		const effective_num = ~~(data.length * fixed_rate / 100)
		const remove_num = data.length - effective_num
		const edge = ~~(remove_num / 2)
		return data.slice(edge, edge + effective_num)
	}

	main()
</script>

<pre></pre>

[
  {
    "name": "fn1",
    "range": [
      0.7999999523162842,
      1
    ],
    "max": 2.3000001907348633,
    "avg": 0.8510000115633011,
    "med": 0.8000001907348633,
    "num": 800
  },
  {
    "name": "fn2",
    "range": [
      9.599999904632568,
      10.799999952316284
    ],
    "max": 15,
    "avg": 9.980625006556512,
    "med": 9.899999856948853,
    "num": 800
  },
  {
    "name": "fn3",
    "range": [
      0.20000004768371582,
      0.39999985694885254
    ],
    "max": 1.7999999523162842,
    "avg": 0.28487500131130217,
    "med": 0.2999999523162842,
    "num": 800
  }
]

10 万の配列を for-of でループして最後の 10 件を残す処理です
比較するのは最後の N 件を残すための方法の違いなので準備が面倒な stream は用意せず単純な配列をデータとして使ってます
fn1, fn2, fn3 が (1), (2), (3) と対応します

上の結果は Chrome105 のものです
結果の単位は ms で performance.now で取得した数値の引き算です
max は一番時間がかかった場合で Chrome だと基本的に最適化される前の最初の 1 回目です
1000 回繰り返して中央の 8 割の 800 回を有効値としています
その中での最小と最大が range で平均値が avg で中央値が med です

fn2 は fn1 より速いかもと思ったのですがかなり遅く 10 倍ほどの差があります
length の変更はパフォーマンス的には良い方法じゃないみたいですね

fn3 は予想どおり速く fn1 の 2～3 倍です
やっぱり使い回すほうがパフォーマンス的には優れていますね

ちなみにそれとは反対の使い回さず新しく配列を毎回作る方法

const fn4 = () => {
	let arr = Array(10)
	for (const value of values) {
		arr = [...arr.slice(1), value]
	}
	return arr
}

速度は遅いだろうと最初はやらなかったのですがあとから試してみると

range: 7.3～8.7 と fn2 よりは速かったです

「JavaScript」カテゴリの最新記事

COMMENT