回答編集履歴
3
findIndexAll 型
answer
CHANGED
|
@@ -44,7 +44,7 @@
|
|
|
44
44
|
console.log(JSON.stringify(removeOverlapB1(array))); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]
|
|
45
45
|
```
|
|
46
46
|
|
|
47
|
-
###
|
|
47
|
+
### findIndexAll 型
|
|
48
48
|
|
|
49
49
|
`Array.prototype.findIndex` を発展させ、配列全体からHITした index 値のリストを返す `findIndexAll` を定義し、返り値となる配列の `length` 値が `0` なら重複なしと見なします。
|
|
50
50
|
一度、重複ありと見なしたインデックスをキャッシュし、再検索しないことで検索コストを抑えます。
|
2
3パターンのコードを紹介
answer
CHANGED
|
@@ -1,3 +1,178 @@
|
|
|
1
|
-
|
|
1
|
+
### findIndex + findLastIndex 型
|
|
2
2
|
|
|
3
|
+
配列を前方/後方検索し、`index` が一致したら重複なしと見なします。
|
|
4
|
+
アルゴリズムは単純ですが、重複が全くないと配列全体を要素数だけ検索するのでコストがかかります。
|
|
5
|
+
また、`Array.prototype.findLastIndex` が存在しないので自前定義する必要があります。
|
|
6
|
+
|
|
7
|
+
```JavaScript
|
|
8
|
+
/**
|
|
9
|
+
* findIndex + findLastIndex 型
|
|
10
|
+
*/
|
|
11
|
+
var removeOverlapB1 = (function () {
|
|
12
|
+
function findLastIndex (array, callbackfn, thisArg) {
|
|
13
|
+
var i = array.length, hasThisArg = arguments.length > 2;
|
|
14
|
+
|
|
15
|
+
while (i--) {
|
|
16
|
+
if (hasThisArg) {
|
|
17
|
+
if (callbackfn.call(thisArg, array[i], i, array)) {
|
|
18
|
+
return i;
|
|
19
|
+
}
|
|
20
|
+
} else if (callbackfn(array[i], i, array)) {
|
|
21
|
+
return i;
|
|
22
|
+
}
|
|
23
|
+
}
|
|
24
|
+
|
|
25
|
+
return -1;
|
|
26
|
+
}
|
|
27
|
+
|
|
28
|
+
function findIndexfn (object) {
|
|
29
|
+
return object.b === this;
|
|
30
|
+
}
|
|
31
|
+
|
|
32
|
+
function filterfn (object, i, array) {
|
|
33
|
+
var b = object.b;
|
|
34
|
+
|
|
35
|
+
return array.findIndex(findIndexfn, b) === findLastIndex(array, findIndexfn, b);
|
|
36
|
+
}
|
|
37
|
+
|
|
38
|
+
return function removeOverlapB (array) {
|
|
39
|
+
return array.filter(filterfn);
|
|
40
|
+
};
|
|
41
|
+
}());
|
|
42
|
+
|
|
43
|
+
var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
|
|
44
|
+
console.log(JSON.stringify(removeOverlapB1(array))); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]
|
|
45
|
+
```
|
|
46
|
+
|
|
47
|
+
### findIndex + findLastIndex 型
|
|
48
|
+
|
|
49
|
+
`Array.prototype.findIndex` を発展させ、配列全体からHITした index 値のリストを返す `findIndexAll` を定義し、返り値となる配列の `length` 値が `0` なら重複なしと見なします。
|
|
50
|
+
一度、重複ありと見なしたインデックスをキャッシュし、再検索しないことで検索コストを抑えます。
|
|
51
|
+
ただし、配列全体が検索対象であることは変わりない為、重複が少ないと検索コストが高くなる問題は依然としてあります。
|
|
52
|
+
|
|
53
|
+
```JavaScript
|
|
54
|
+
/**
|
|
55
|
+
* findIndexAll 型
|
|
56
|
+
*/
|
|
57
|
+
var removeOverlapB2 = (function (push) {
|
|
58
|
+
function findIndexAll (array, callbackfn, thisArg) {
|
|
59
|
+
var indexes = [], hasThisArg = arguments.length > 2;
|
|
60
|
+
|
|
61
|
+
for (var i = 0, l = array.length; i < l; ++i) {
|
|
62
|
+
if (hasThisArg) {
|
|
63
|
+
if (callbackfn.call(thisArg, array[i], i, array)) {
|
|
64
|
+
indexes.push(i);
|
|
65
|
+
}
|
|
66
|
+
} else if (callbackfn(array[i], i, array)) {
|
|
67
|
+
indexes.push(i);
|
|
68
|
+
}
|
|
69
|
+
}
|
|
70
|
+
|
|
71
|
+
return indexes;
|
|
72
|
+
}
|
|
73
|
+
|
|
74
|
+
function findIndexAllfn (object) {
|
|
75
|
+
return object.b === this;
|
|
76
|
+
}
|
|
77
|
+
|
|
78
|
+
function filterfn (object, i, array) {
|
|
79
|
+
if (this.indexOf(i) !== -1) {
|
|
80
|
+
return false;
|
|
81
|
+
}
|
|
82
|
+
|
|
83
|
+
var indexes = findIndexAll(array, findIndexAllfn, object.b);
|
|
84
|
+
|
|
85
|
+
if (indexes.length === 1) {
|
|
86
|
+
return true;
|
|
87
|
+
}
|
|
88
|
+
|
|
89
|
+
push.apply(this, indexes);
|
|
90
|
+
return false;
|
|
91
|
+
}
|
|
92
|
+
|
|
93
|
+
return function removeOverlapB (array) {
|
|
94
|
+
return array.filter(filterfn, []);
|
|
95
|
+
};
|
|
96
|
+
}(Array.prototype.push));
|
|
97
|
+
|
|
98
|
+
var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
|
|
99
|
+
console.log(JSON.stringify(removeOverlapB2(array))); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]
|
|
100
|
+
```
|
|
101
|
+
|
|
102
|
+
### while 文 + 後方検索キャッシュ型
|
|
103
|
+
|
|
104
|
+
`while` 文で前方検索/後方検索し、`index` が同値なら重複なしと見なします。
|
|
105
|
+
検索時に重複値をキャッシュする為、一度重複なしと見なされればキャッシュから重複判定出来ます。
|
|
106
|
+
コードが複雑化していますが、私が考えうる限りでは「検索コストが最も低い(無駄が少ない)コード」です。
|
|
107
|
+
|
|
108
|
+
```JavaScript
|
|
109
|
+
/**
|
|
110
|
+
* while 文 + 後方検索キャッシュ型
|
|
111
|
+
*/
|
|
112
|
+
function removeOverlapB3 (array) {
|
|
113
|
+
var i = -1,
|
|
114
|
+
l = array.length,
|
|
115
|
+
j = l,
|
|
116
|
+
conflicts = [],
|
|
117
|
+
values = [],
|
|
118
|
+
results = [];
|
|
119
|
+
|
|
120
|
+
if (l < 2) {
|
|
121
|
+
return array;
|
|
122
|
+
}
|
|
123
|
+
|
|
124
|
+
while (++i < l) {
|
|
125
|
+
var current = array[i],
|
|
126
|
+
b = current.b,
|
|
127
|
+
cindex = values.indexOf(b);
|
|
128
|
+
|
|
129
|
+
if (cindex === -1) {
|
|
130
|
+
values.push(b);
|
|
131
|
+
cindex = conflicts.push(false) - 1;
|
|
132
|
+
|
|
133
|
+
while (i < --j) {
|
|
134
|
+
var target = array[j],
|
|
135
|
+
tb = target.b;
|
|
136
|
+
|
|
137
|
+
if (b === tb) {
|
|
138
|
+
conflicts[cindex] = true;
|
|
139
|
+
break;
|
|
140
|
+
} else {
|
|
141
|
+
var tindex = values.indexOf(tb);
|
|
142
|
+
|
|
143
|
+
if (values.indexOf(tb) === -1) {
|
|
144
|
+
values.push(tb);
|
|
145
|
+
conflicts.push(false);
|
|
146
|
+
} else {
|
|
147
|
+
conflicts[tindex] = true;
|
|
148
|
+
}
|
|
149
|
+
}
|
|
150
|
+
}
|
|
151
|
+
|
|
152
|
+
if (i === j) {
|
|
153
|
+
results.push(current);
|
|
154
|
+
|
|
155
|
+
while (++i < l) {
|
|
156
|
+
var current = array[i],
|
|
157
|
+
b = current.b;
|
|
158
|
+
|
|
159
|
+
if (!conflicts[values.indexOf(b)]) {
|
|
160
|
+
results.push(current);
|
|
161
|
+
}
|
|
162
|
+
}
|
|
163
|
+
|
|
164
|
+
break;
|
|
165
|
+
}
|
|
166
|
+
} else {
|
|
167
|
+
conflicts[cindex] = true;
|
|
168
|
+
}
|
|
169
|
+
}
|
|
170
|
+
|
|
171
|
+
return results;
|
|
172
|
+
}
|
|
173
|
+
|
|
174
|
+
var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
|
|
175
|
+
console.log(JSON.stringify(removeOverlapB3(array))); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]
|
|
176
|
+
```
|
|
177
|
+
|
|
3
178
|
Re: leila さん
|
1
要件を勘違いしていたので再考
answer
CHANGED
|
@@ -1,72 +1,3 @@
|
|
|
1
|
-
|
|
1
|
+
要件を勘違いしていたので再考します。
|
|
2
|
-
質問文にある「一応これでできたけど」のコードにそれ程無駄はないと思います。
|
|
3
|
-
細かいことを指摘するならいくつかありますが、パフォーマンスUPが切実な問題でなければ問題といえるほどでもないかと…。
|
|
4
2
|
|
|
5
|
-
- `arr.length` を毎回評価するのが無駄
|
|
6
|
-
- `arr[i]["b"]` を毎回評価するのが無駄
|
|
7
|
-
- フラグ変数 `flg` が不要
|
|
8
|
-
|
|
9
|
-
```JavaScript
|
|
10
|
-
'use strict';
|
|
11
|
-
/**
|
|
12
|
-
* for 文
|
|
13
|
-
*/
|
|
14
|
-
function removeOverlapB1 (array) {
|
|
15
|
-
var results = [];
|
|
16
|
-
|
|
17
|
-
for (var i = 0, l = array.length; i < l; ++i) {
|
|
18
|
-
var object = array[i],
|
|
19
|
-
b = object.b;
|
|
20
|
-
|
|
21
|
-
for (var j = 0, m = results.length; j < m; ++j) {
|
|
22
|
-
if (results[j].b === b) {
|
|
23
|
-
break;
|
|
24
|
-
}
|
|
25
|
-
}
|
|
26
|
-
|
|
27
|
-
if (j === m) {
|
|
28
|
-
results.push(object);
|
|
29
|
-
}
|
|
30
|
-
}
|
|
31
|
-
|
|
32
|
-
return results;
|
|
33
|
-
}
|
|
34
|
-
|
|
35
|
-
/**
|
|
36
|
-
* reduce + findeIndex
|
|
37
|
-
*/
|
|
38
|
-
var removeOverlapB2 = (function () {
|
|
39
|
-
function findIndexfn (object) {
|
|
40
|
-
return object.b === this.b;
|
|
41
|
-
}
|
|
42
|
-
|
|
43
|
-
function reducefn (before, current) {
|
|
44
|
-
if (before.findIndex(findIndexfn, current) === -1) {
|
|
45
|
-
before.push(current);
|
|
46
|
-
}
|
|
47
|
-
|
|
48
|
-
return before;
|
|
49
|
-
}
|
|
50
|
-
|
|
51
|
-
return function removeOverlapB (array) {
|
|
52
|
-
return array.reduce(reducefn, []);
|
|
53
|
-
};
|
|
54
|
-
}());
|
|
55
|
-
|
|
56
|
-
var array = [{a:1,b:"h"},{a:1,b:"e"},{a:2,b:"l"},{a:3,b:"l"},{a:1,b:"o"}]
|
|
57
|
-
console.log(JSON.stringify(removeOverlapB1(array))); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]
|
|
58
|
-
console.log(JSON.stringify(removeOverlapB2(array))); // [{"a":1,"b":"h"},{"a":1,"b":"e"},{"a":2,"b":"l"},{"a":1,"b":"o"}]
|
|
59
|
-
```
|
|
60
|
-
|
|
61
|
-
`reduce`, `findIndex` で処理を小分けにすると見通しが良くなりますが、「**パフォーマンスが上なのは For 文版**」です。
|
|
62
|
-
ですので、要件によっては leila さんが目指した方向も有りだと私は思います。
|
|
63
|
-
それと、「何を無駄と思うのか」の観点は人それぞれだと思いますので自分の制作ポリシーを見つめなおしてみることも重要だと思います。
|
|
64
|
-
例えば、私がここに挙げたコードで比較するなら
|
|
65
|
-
|
|
66
|
-
- 関数はコストが高いので `reduce`, `findeIndex` を使うのが無駄
|
|
67
|
-
- `for` 文の入れ子は変数が増えて見通しが悪くなるので制作効率が低下して無駄に時間がかかる
|
|
68
|
-
|
|
69
|
-
考え方によっては評価が180度変わります。
|
|
70
|
-
ただ、「可読性」については経験によるところが大きいので苦手意識を持たずにいろんな書き方を習得してみると使える武器が増えて良いと思います。
|
|
71
|
-
|
|
72
3
|
Re: leila さん
|