アレイのuniq
Posted feedbacks - Nested
Flatten Hidden
「Rubyからの挑戦状」ということで。
1 | xs.uniq
|
うーん。プリミティブ値だけの配列だったらこれでいける。 でも、オブジェクトとかが入ってくると toString() の結果によっては正しい結果にならないなあ。 alert([1, 2, 3, 3, 2, 1].uniq()); // [1, 2, 3]
1 2 3 4 5 6 7 | Array.prototype.uniq = function () {
for (var i = 0, r = [], s = {}; i < this.length; i++) {
if (!s[this[i]]) r.push(this[i]);
s[this[i]] = true;
}
return r;
};
|
Object Type にも対応した書き方。
効率悪いとか言わない><
alert([1, 2, {}, {}, 2, 1].uniq()); // [1, 2, {}, {}]
var a = {};
alert([1, 2, a, a].uniq()); // [1, 2, {}]
1 2 3 4 5 6 7 8 9 10 11 | Array.prototype.uniq = function () {
for (var i = 0, r = [], s = []; i < this.length; i++) {
for (var j = 0; j < s.length; j ++)
if (s[j] === this[i]) break;
if (j == s.length) {
r.push(this[i]);
s.push(this[i]);
}
}
return r;
};
|
いっそ両方とも実装してみるとか。ダメ?
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | Array.prototype.uniq = function(usedObjKey) {
if (typeof(usedObjKey) == 'undefined')
usedObjKey = (typeof(this[0]) == 'object');
var ret = [];
if (usedObjKey) {
for (var i=0, len=this.length, s=[]; i<len; i++) {
if (s.indexOf(this[i]) < 0) {
ret.push(this[i]);
s.push(this[i]);
}
}
}
else
{
for (var i=0, len=this.length, s={}; i<len; i++) {
if (!s[this[i]])
ret.push(this[i]);
s[this[i]] = true;
}
}
return ret;
}
/**
* @site http://developer.mozilla.org/ja/docs/
* Core_JavaScript_1.5_Reference:Global_Objects:Array:indexOf
*/
if (!Array.prototype.indexOf) {
Array.prototype.indexOf = function(elt /*, from*/) {
var len = this.length;
var from = Number(arguments[1]) || 0;
from = (from < 0) ? Math.ceil(from) : Math.floor(from);
if (from < 0)
from += len;
for (; from<len; from++)
if (from in this && this[from] === elt)
return from;
return -1;
};
}
|
ObjectやFunctionにも対応してみた。firefox2.0.0.4+Firebugで確認。 なんというかtoJSONString()の手抜き実装みたいだ。
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 26 27 28 29 30 31 32 33 34 35 36 | Array.prototype.uniq=function(){
var h={};
var tostr=function(obj){
if(typeof obj == "object"){
var str="";
for(var p in obj){
str+=p+":"+arguments.callee(obj[p]);
}
return "{"+str+"}";
}
return obj;
}
for(var i=0,h={},l=this.length,r=[]; chk=tostr(this[i]),i<l; i++){
if(!h[chk]===true)r.push(this[i]);
h[chk]=true;
}
return r;
}
// -------------------
var a=[1,2,[3,4],6,2,3,{},{},[4,3]
,function(){},function(a){},function(){},function(){return this;}
,{"a":"test1"}
,{"a":"nest","b":{"c":"nest2"}}
,{"a":"nest2","b":{"c":"nest3"}}
,{"a":"nest","b":{"c":"nest2"}}
,{"a":"test1"}
,{"a":"test3"}
,[5,12,4],[4,3],[5]
];
a.uniq();
//[1, 2, [3, 4], 6, 3, Object, [4, 3], function(), function(), function()
//, Object a=test1, Object a=nest b=Object, Object a=nest2 b=Object, Object a=test3
//, [5, 12, 4], [5]]
|
1 2 3 4 5 6 7 8 9 10 11 | require 'pseudohash' # http://www.notwork.org/~gotoken/ruby/p/pseudohash/
xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
h = PseudoHash.new
xs.each{|i|
h[i, true] = nil
}
xs_out = h.map{|k, v| k}
p xs_out
|
効率はともかく
1 2 | >>> [ xs[i] for i in xrange(0, len(xs)) if xs[i] not in xs[:i] ]
[3, 1, 4, 5, 9, 2, 6, 8, 7]
|
1 2 3 4 5 6 7 8 9 10 | xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
h = {}
xs_out = []
xs.each {|i|
xs_out << i unless h.key?(i)
h[i] = nil
}
p xs_out
|
# uniq [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 8; 9; 7; 9];; - : int list = [3; 1; 4; 5; 9; 2; 6; 8; 7]
1 2 3 4 5 6 7 | let uniq xs =
let rec uniq' acc = function
| [] -> acc
| y::ys when (List.mem y acc) -> uniq' acc ys
| y::ys -> uniq' (y::acc) ys
in
List.rev (uniq' [] xs)
|
#456 は「配列状」を緩く解釈してリストを使いましたが、文字通り配列(だけ)を使うとこうなるのかなあと。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | let rec appears_between p q m a =
if p = q then false
else
if a.(p) = m then true
else appears_between (succ p) q m a
let uniq2 xs =
let ys = Array.copy xs in
let rec move x y =
if (Array.length xs) = x then
Array.sub ys 0 y
else
if appears_between 0 y xs.(x) ys then
move (succ x) y
else
(ys.(y) <- xs.(x); move (succ x) (succ y))
in
move 0 0
|
関数型ということにこだわらなければこういう手も。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | open System;;
open Array;;
let uniq xs =
let ars = create (length xs) xs.(0) in
let i = ref 1 in
for idx = 1 to (length xs)-1
do
if not (exists (fun elem -> xs.(idx) = elem) ars)
then
begin
ars.(!i) <- xs.(idx);
i := !i+1
end
else ()
done;
sub ars 0 !i;;
|
(vector-uniq xs) =>#(3 1 4 5 9 2 6 8 7)
1 2 3 4 5 6 7 | (define xs #(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9))
(define (vector-uniq vec)
(let ((ls (vector->list vec)))
(do ((ls ls (cdr ls))
(acc '() (if (memv (car ls) acc) acc (cons (car ls) acc))))
((null? ls) (list->vector (reverse! acc))))))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | import java.util.ArrayList;
import java.util.List;
public class Unique {
public static Object[] toUniqueArray(Object[] array) {
List unique = new ArrayList();
for (Object o : array) {
if (!unique.contains(o)) {
unique.add(o);
}
}
return unique.toArray();
}
}
|
Squeak Smalltalk の #addIfNotPresent: を使って。
1 2 3 4 5 6 7 | | xs uniq |
xs := #(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9).
uniq := OrderedCollection new.
xs do: [:each | uniq addIfNotPresent: each].
^uniq asArray
"=> #(3 1 4 5 9 2 6 8 7) "
|
普通に。
1 2 3 4 5 6 7 8 9 10 11 | def iter_uniq(it):
s = set()
for x in it:
if x not in s:
yield x
s.add(x)
def uniq(a):
return list(iter_uniq(a))
print uniq([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9])
|
「hashを使」います。
vectorでもlistでもsequenceなら効きます。
1 2 3 4 5 6 | (use gauche.sequence)
(define (uniq a)
(let1 h (make-hash-table 'equal?)
(define (p x) (or (hash-table-exists? h x)
(begin (hash-table-put! h x #t) #f)))
(remove-to (class-of a) p a)))
|
そのものズバリ array_unique を利用。
何のヒネリも有りませんね。
1 2 3 4 | <?php
$xs = array(3,1,4,1,5,9,2,6,5,3,5,8,9,7,9);
var_dump(array_unique($xs));
?>
|
#457や#462を思いつけるようになりたい。
1 2 3 4 5 6 7 8 | (define (uniq lst)
(fold
(lambda (e l)
(cond ((null? l) (cons e l))
((member e l) l)
(else (append l (list e)))))
'()
lst))
|
こちらこそ。foldを使うなんて思い付きませんorz
リストの処理で、foldを使うのならこういうのも。最後にreverseするのが残念な感じですが。!無しで。
1 2 3 4 5 6 | (define (uniq a)
(reverse
(fold (lambda (e knil)
(if (member e knil)
knil
(cons e knil))) () a)))
|
毎回 (null? l) する無駄や (append l (list e)) あたりの汚さが 消えてすっきりキレイに! なるほど納得。ありがとうございます。
こんなのでいいのか。
(import Data.List が必要)
1 | nub xs
|
nub だと最悪のケースでO(n^2) になる。以下のuniqなら要素がOrd(順序)クラス という条件のもとで最悪ケースでO(n log n)にできる。 最悪ケースのベンチマークは以下のとおり *Main> length $ uniq [1..10000] 10000 (0.13 secs, 11539780 bytes) *Main> length $ uniq [1..100000] 100000 (1.00 secs, 121637004 bytes) *Main> length $ nub [1..10000] 10000 (0.98 secs, 1045976 bytes) *Main> length $ nub [1..100000] 100000 (95.85 secs, 8910200 bytes)
1 2 3 4 5 6 7 8 9 10 11 | import Data.List
app o f x y = f x `o` f y
cmpapp = app compare
eqapp = app eq
uniq :: Ord a => [a] -> [a]
uniq = map snd . sort . map head . groupBy (eqapp snd) . sortBy (cmpapp snd) . zip [1..]
uniq' :: Eq a => [a] -> [a]
uniq' = nub
|
あれあれコードを写しそこねてる。ごめんなさい。 eq なんて関数ないし、型宣言を文脈をつけて書くのが正しい。
1 2 3 4 5 6 7 8 9 10 11 12 13 | import Data.List
app :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
app o f x y = f x `o` f y
cmpapp :: Ord b => (a -> b) -> (a -> a -> Ordering)
cmpapp = app compare
eqapp :: Eq b => (a -> b) -> (a -> a -> Bool)
eqapp = app (==)
uniq :: Ord a => [a] -> [a]
uniq = map snd . sort . map head . groupBy (eqapp snd) . sortBy (cmpapp snd) . zip [1..]
|
隙があったのでinject
1 2 | xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
xs.inject([]){|a, e| a.member?(e) ? a : a << e }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[] xs ={ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 };
foreach(int i in Uniq(xs))
Console.WriteLine(i);
}
static List<T> Uniq<T>(T[] xs)
{
List<T> lst = new List<T>();
Dictionary<T, object> dic = new Dictionary<T, object>();
foreach (T t in xs) if (!dic.ContainsKey(t))
{ lst.Add(t); dic.Add(t, null); }
return lst;
}
}
|
元の配列をそのまま変更しています。
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 26 27 28 29 30 | #include <stdio.h>
int main()
{
int xs[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
int array_size;
int i, j, k;
int save;
array_size = (sizeof(xs) / sizeof(xs[0]));
for (i = 0; i < array_size; i++) {
save = xs[i];
for (j = i+1; j < array_size; j++) {
if (save == xs[j]) {
/* 配列を詰める作業 */
for (k = j; k < array_size-1; k++) {
xs[k] = xs[k+1];
}
array_size--;
}
}
}
for (i = 0; i < array_size; i++) {
printf("%d ", xs[i]);
}
printf("\n");
return 0;
}
|
重複を取り除いた配列ということで教科書通りにArrayList.Contains()です。 VS2005なのでムダにジェネリックで。 Javaとほぼ同じロジックなのはナイショだ。つーかC#出てた orz
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 26 27 28 29 30 31 32 | using System;
using System.Collections.Generic;
using System.Text;
namespace ArrayUniq
{
class Program
{
static void Main(string[] args)
{
object[] source = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 };
object[] results = Uniq(source);
foreach (object value in results)
{
System.Console.WriteLine(value);
}
}
static object[] Uniq(object[] array)
{
List<object> uniqList = new List<object>();
foreach (object value in array)
{
if (! uniqList.Contains(value))
{
uniqList.Add(value);
}
}
return uniqList.ToArray();
}
}
}
|
C#からRubyへ感覚を移行する練習です。 1.foreach, Containsのまま移植 2.injectを使いローカル変数を使用せずオブジェクトを返す(#467) 3.uniqメソッドを使用(#448) 全て同じ結果になります。 Hackety Hackにて作成/実行 http://hacketyhack.net/ http://www.radiumsoftware.com/0705.html#070515
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | xs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
# C#の例(#470)をそのままRubyに変換
us = []
xs.each do |x|
unless us.member?(x)
us << x
end
end
p us
# moroさん(#467) injectを使いローカル変数を使用せずオブジェクトを返す
p xs.inject([]){|a, e| a.member?(e) ? a : a << e }
# 匿名さん(#448) uniqメソッドを使用
p xs.uniq
|
適当
1 2 | (let ((xs (list 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9)))
(delete-duplicates xs :from-end t))
|





にしお
#3372()
Rating1/1=1.00
Rubyで表現すると下のようになります。
間違えないように:よくある「ハッシュを使う」「集合オブジェクトを使う」などの方法は順番が乱れてしまうので使えません。出現順序を守りつつ、2回目以降の出現だけを取り除いてください。
この投稿は匿名での挑戦状の投稿を元に作成しています。ご投稿ありがとうございます。
[ reply ]