DouKaku?beta

challenge 重複する要素を取り除く

与えられたリストxsの中から、 2回以上出現するものを全部取り除いてください。 

サンプル入力
[3, 1, 4, 1, 5, 9, 2, 6, 5]
サンプル出力
[3, 4, 9, 2, 6]

これはアレイのuniqの派生問題です。 リストとかアレイという言葉は言語によってまちまちの意味で使われているので、 「配列のようなもの」という漠然とした意味にとって構いません。

post comment

Posted feedbacks - Smalltalk

Squeak Smalltalk で。

#occurrencesOf: は配列（array）にも適用できますが非効率なので、bag を介在させています。bag は内部的に要素を要素種と数で管理するコレクションです。 
1
2
3
4
| array bag |
array := #(3 1 4 1 5 9 2 6 5).
bag := array asBag.
^array reject: [:each | (bag occurrencesOf: each) > 1]  "=> #(3 4 9 2 6) "

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

結果の単位はミリ秒で、順に「bag  使用時（bag への変換時間も込み）」「bag 使用時（同、含まず）」「bag 不使用時」です。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
| 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) "

了解です。では、あらためて。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
| 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)} "

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]