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

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

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

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

Posted feedbacks - Nested

Flatten Hidden

	
1
2
3
4
5
def only_unique(ary)
  freq = ary.inject(Hash.new(0)){|h,x| h[x]+=1; h }
  ary.select{|x| freq[x]==1 }
end
only_unique([3, 1, 4, 1, 5, 9, 2, 6, 5]) # => [3, 4, 9, 2, 6]
問題文が少しわかりにくいですが、この場合出力は4だけになることが求められています。

	
1
2
3
(defun only-unique (list)
  (remove-if (lambda (x) (>= (count x list) 2)) list))
(only-unique '(3 1 4 1 5 9 2 6 5))      ; => (3 4 9 2 6)
要素がEqクラスのインスタンスなら
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
uniqOnly :: Eq a => [a] -> [a]
uniqOnly = uniq []
  where uniq xs [] = reverse xs
        uniq xs (y:ys) = case break (y ==) xs of
          (_,[])    -> uniq (y:xs) ys
          (ps,_:qs) -> uniq (ps++qs) ys

{-
uniqOnly [3,1,4,1,5,9,2,6,5]
[3,4,9,2,6]
-}
ああやっちゃった。お題を全然満たしてない!
こっちが正解のはず
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
uniqOnly :: Eq a => [a] -> [a]
uniqOnly = uniq [] []
  where uniq xs ys [] = reverse xs
        uniq xs ys (z:zs) = case break (z==) xs of
          (_,[]) | z `notElem` ys -> uniq (z:xs) ys zs
                 | otherwise      -> uniq xs ys zs
          (ps,_:qs)               -> uniq (ps++qs) (z:ys) zs

{-
*Main> uniqOnly [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
[4,2,6,8,7]
-}
要素がOrdクラスのインスタンスなら、こちらの方が効率がいいはず
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import Data.List

binapp :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
binapp o f x y = f x `o` f y
eqapp :: Eq b => (a -> b) -> (a -> a -> Bool)
eqapp = binapp (==) 
cmpapp :: Ord b => (a -> b) -> (a -> a -> Ordering)
cmpapp = binapp compare

mapFilter f p xs = [ f x | x <- xs, p x ]

lenOne [x] = True
lenOne _   = False

uniqOnly :: Ord a => [a] -> [a]
uniqOnly = map snd
         . sortBy (cmpapp fst) 
         . mapFilter head lenOne 
         . groupBy (eqapp snd) 
         . sortBy (cmpapp snd) 
         . zip [0..]
効率について曖昧に書いてしまったので補足です.

#2806のuniqOnlyでは最悪のケースでの計算オーダーではO(n log n)です.
#2805や#2807のuniqOnlyでは最悪のケースでの計算オーダーはO(n^2)です.

入力リストとして[1..10^4]周辺の値を与えて計算時間を比較するとわかります.

他の言語でも,集合やバッグを使う場合,入力リストの要素が順序決定できる
値でないと最悪の場合 O(n^2) の計算になるとだろうと想像しています.

	
1
2
3
4
5
集合+ソートを用いたものでは、Pythonでの僕の投稿 #2818 も、
最悪のケースでの計算量は指数オーダーでした。

ユニークな要素の数が多すぎると sortとcountで効率が落ちる。
効率考えたつもりが返って悪化した悪い例になってしまった(恥
foldl を使う版
1
2
3
4
5
6
uniqOnly :: Eq a => [a] -> [a]
uniqOnly = reverse . fst . foldl uniq ([],[])
  where uniq (xs,ys) z = case break (z==) xs of
           (_,[]) | z `notElem` ys -> (z:xs,ys)
                  | otherwise      -> (xs,ys)
           (ps,_:qs)               -> (ps++qs,z:ys) 
ああっ。寝惚けてる mapAccumL じゃなくて foldlだ!
御免なさい。タグまでうっちゃった。
import Data.List は不要です。
修正しておきました。

	
1
Dim uniq = From x In xs Group By x Into Count() Where Count = 1 Select x
速度的には、defaultdict より
h[i] = h.get(i, 0) + 1
のようなものを使ったほうが速いんでしょうけど・・・
可読性重視で。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import collections

def only_unique(a):
    h = collections.defaultdict(int)
    for i in a:
        h[i] += 1
    return [i for i in a if h[i] == 1]

def main():
    print only_unique([3, 1, 4, 1, 5, 9, 2, 6, 5])

if __name__ == '__main__':
    main()
ちゃんと計測してみたら、要素が多いときは
collections.defaultdict の方が速かったです。
# 一概にどちらが遅いとはいえない
>>> import collections
>>> collections
<module 'collections' (built-in)>

なるほど、collectionsはネイティブで書かれてますね。
「初期化のコストが少し高いけども、
多くのデータを扱うならcollectionsの方がよい」
ということかもしれませんね。
pythonを知らないので想像ですが、
#2827で言及したことと同じことがおこってるのでは?
効率の話題に付いて、
PythonのCookbookのForumでも同じような話題があったので、こっちに返信付けます。

リンク先の内容は、Pythonでのunique関数のレシピで、
今回のお題では、リスト内の要素の型について特に指定はありませんでしたが、
ハッシュや集合を用いる場合に、リストの要素がunhashableの場合等にも言及があります。
# あと、リスト内包内の隠し変数を使うとか裏技っぽいことが・・・
Pythonの辞書(連想配列)は存在しないキーを読み出そうとすると例外を投げるのですが、
defaultdictはキーが存在しない場合にデフォルトの値を返す辞書なんです。
なのでアルゴリズム上はどっちを使ってもオーダーは同じはずです。
h[i] = h.get(i, 0) + 1の場合:

  0 LOAD_GLOBAL              0 (h)
  3 LOAD_ATTR                1 (get)
  6 LOAD_GLOBAL              2 (i)
  9 LOAD_CONST               1 (0)
 12 CALL_FUNCTION            2
 15 LOAD_CONST               2 (1)
 18 BINARY_ADD          
 19 LOAD_GLOBAL              0 (h)
 22 LOAD_GLOBAL              2 (i)
 25 STORE_SUBSCR        

h[i] += 1の場合:

  0 LOAD_GLOBAL              0 (h)
  3 LOAD_GLOBAL              1 (i)
  6 DUP_TOPX                 2
  9 BINARY_SUBSCR       
 10 LOAD_CONST               1 (1)
 13 INPLACE_ADD         
 14 ROT_THREE           
 15 STORE_SUBSCR        

LOAD命令の数がかなり違うので、そこが性能の差につながっているのかな、と思います。
後学のために教えてくださいまし.
Pythonの連想配列と辞書とでキーになれる値の制限は特にないのでしょうか?
それぞれのコレクションのエントリーを追加あるいは更新のときの手間はO(log n)?それともO(n)?

連想配列と辞書の違いはありません、というより「Pythonの『辞書』はPerlの『連想配列』やJavaのHashtableのようなもの」ということです。 実装はハッシュテーブルなのでO(1)のはず。ハッシュ値の計算方法さえ定義してやればどんなオブジェクトでも入ります。組み込み型のリストと辞書は故意にハッシュ値の計算方法が未定義にされているのでそのままでは入りませんが、__hash__メソッドを定義してやれば入るようになります。

{[]: 1} # TypeError: list objects are unhashable

class MyList(list):
    def __hash__(self):
        return id(self)


{MyList(): 1} # {[]: 1}
ありがとうございます。勉強になります。
 uneval の無い環境とプロパティの順番が保証されない可能性に配慮したら,えらく冗長になってしまった。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function doukaku56(a){
  if(typeof uneval != 'function') var uneval = function(o){
    if(o === undefined) return 'undefined';
    if(o === null)      return 'null';
    var s = o.toString();
    switch(o.constructor){
     case Object:
      if(s.indexOf('[object Object')) return s;
      var m = []; for(var p in o) m[m.length] = p +':'+ arguments.callee(o[p]);
      return '({'+ m.join(', ') +'})';
     case Array:
      var a = []; for(var i = o.length; i--;) a[i] = arguments.callee(o[i]);
      return '['+ a.join(', ') +']';
     case String:
      return '"'+ s.replace(/[\"\\]/g,'\\$&').replace(/\r/g,'\\r').replace(/\n/g,'\\n') +'"';
     case Date: return '(new Date('+ +o +'))';
     default:   return s;
    }
  };
  var r = [], h = {}, k, i, l;
  for(i = 0, l = a.length; i < l; i++) h[k = uneval(a[i])] = k in h ? -1 : i;
  for(k in h) if(h[k] >= 0) r[r.length] = h[k];
  for(i = r.sort(function(x, y){ return x - y }).length; i--;) r[i] = a[r[i]];
  return r;
}
 uneval なんか使わずとも === で比較して除けばいいことに気付く。↑ の20倍以上速い…。(--;)

 doukaku56( [ 1, "1", [1], new Number(1), { valueOf: function(){ return 1 } } ] )
  => 1,1,1,1,[object Object]
1
2
3
4
5
6
7
function doukaku56(a){
  for(var r = [], d = {}, i = 0, j, l = a.length; i < l; i++) if(!d[i]){
    for(j = l; --j > i;) if(a[i] === a[j]) d[i] = d[j] = true;
    if(!d[i]) r[r.length] = a[i];
  }
  return r;
}

ふつうに。

1
2
3
4
5
6
7
8
import scala.collection.mutable.HashMap

def uniqOnly[A](a:Seq[A]) = {
  val map = a.foldLeft(new HashMap[A,int]){(r,v)=>r(v)=r.getOrElse(v,0)+1;r}
  a.filter(map(_)==1)
}

println(uniqOnly(Array(3, 1, 4, 1, 5, 9, 2, 6, 5)))
再帰再帰・・・。

pythonで再帰にこだわるのは間違っている気がするが。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def oneces(xs, duplicated=None):
  if duplicated is None:
    duplicated = []
  if len(xs) < 2:
    return xs
  o = oneces(xs[:-1], duplicated)
  if xs[-1] in duplicated:
    return o
  if xs[-1] in o:
    o.remove(xs[-1])
    duplicated.append(xs[-1])
    return o
  return o+xs[-1:]
PHPは配列操作得意ですね。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
<?php
function only_unique($ary) {
	foreach ( $ary as $val ) {
		if ( count(array_keys($ary,$val)) == 1 ) {
			$rtn[] = $val;
		}
	}
	return $rtn;
}

print_r(only_unique(array(3, 1, 4, 1, 5, 9, 2, 6, 5)));
?>
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) "
1e3だけでなく2e3と4e3などの複数のプロファイルデータをとると、
計算量の増加の程度がそれぞれの場合で想像できるのではないでしょうか。
了解です。では、あらためて。
 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)} "

	
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

public class UniqOnly {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5);
		
		Set<Integer> counter = new HashSet<Integer>();
		Set<Integer> dup = new HashSet<Integer>();
		
		for (int i = 0, n = list.size(); i < n; i++) {
			if(!counter.add(list.get(i))) {
				dup.add(list.get(i));
			}
		}
		list = new LinkedList<Integer>(list);
		list.removeAll(dup);
		System.out.println(list);
	}
}
[x for x in xs if xs.count(x) == 1] から、
重複する値が多数あった場合を考えて、ループ回数を減らすために集合を利用。
最後は、 sorted(..., key=xs.index) で元の順番に並べ替え。
1
2
def only_uniq(xs):
    return sorted((x for x in set(xs) if xs.count(x) == 1), key=xs.index)
なら、もしかしてこれでいける?
1
2
def only_uniq(xs):
    return sorted(set(xs), key=xs.index)

それは2回以上出現する要素を取り除いていないですね。前の問題の解答としてならアリですね。

あ、お題を誤読してました。順序を保存したuniqではなく
要素がひとつだけのものを残すんですね。
上のコードにマイナス付けておいてください。
#2818の3.0a1版。3.0a1リリース記念。
1
2
3
>>> L = [3, 1, 4, 1, 5, 9, 2, 6, 5]
>>> sorted({v for v in L if L.count(v) == 1}, key=L.index)
[3, 4, 9, 2, 6]
{v for v