DouKaku? 2833 sumim: 念のため時間を計測して bag を介する...(重複する要素を取り除く)

Comment detail

This comment is reply for 2816 sumim: Squeak Smalltalk で。 ...(重複する要素を取り除く). Go to thread root.

念のため時間を計測して bag を介することの有無の影響をみてみました。非力なマシン（PowerPC 1GHz, OS X）なので、1e3 で(^_^;)。

結果の単位はミリ秒で、順に「bag 使用時（bag への変換時間も込み）」「bag 使用時（同、含まず）」「bag 不使用時」です。

| array bag millisecondsWithBag millisecondsWithBag2 millisecondsWioutBag |
array := (1 to: 1e3) asArray.

millisecondsWithBag := [
	bag := array asBag.
	array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

millisecondsWithBag2 := [
	array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

millisecondsWioutBag := [
	array reject: [:each | (array occurrencesOf: each) > 1]] timeToRun.

^{millisecondsWithBag. millisecondsWithBag2. millisecondsWioutBag}   "=> #(19 8 526) "

1e3だけでなく2e3と4e3などの複数のプロファイルデータをとると、
計算量の増加の程度がそれぞれの場合で想像できるのではないでしょうか。

了解です。では、あらためて。

| array bag millisecondsWithBag millisecondsWithBag2 millisecondsWioutBag |
#(1e3 2e3 4e3) collect: [:size |

	array := (1 to: size) asArray.

	millisecondsWithBag := [
		bag := array asBag.
		array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

	millisecondsWithBag2 := [
		array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

	millisecondsWioutBag := [
		array reject: [:each | (array occurrencesOf: each) > 1]] timeToRun.

	size -> {millisecondsWithBag. millisecondsWithBag2. millisecondsWioutBag}]

"=> {1000->#(19 8 548) . 2000->#(43 19 2169) . 4000->#(82 38 8725)} "

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq