回答編集履歴
27
テキスト修正
answer
CHANGED
|
@@ -132,7 +132,7 @@
|
|
|
132
132
|
|
|
133
133
|
### 追記 - getUnique13
|
|
134
134
|
|
|
135
|
-
アルゴリズムとしては、`getUnique8` を拝借し、比較対象として、0以上の整数として設定される id(
|
|
135
|
+
アルゴリズムとしては、`getUnique8` を拝借し、比較対象として、0以上の整数として設定される id(=`1000 * x + y`) を使うコードです。
|
|
136
136
|
|
|
137
137
|
```javascript
|
|
138
138
|
function getUnique13(a, b) {
|
26
テキスト修正
answer
CHANGED
|
@@ -177,6 +177,6 @@
|
|
|
177
177
|
```
|
|
178
178
|
のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。
|
|
179
179
|
|
|
180
|
-
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。その結果、
|
|
180
|
+
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。その結果、うまく大小関係を定義できれば、`getUnique8`をベースとした速いコードを書くことができます。
|
|
181
181
|
|
|
182
182
|
（※参考：このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。）
|
25
テキスト修正
answer
CHANGED
|
@@ -177,6 +177,6 @@
|
|
|
177
177
|
```
|
|
178
178
|
のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。
|
|
179
179
|
|
|
180
|
-
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。
|
|
180
|
+
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。その結果、もし（運良く）大小関係を定義できれば、`getUnique8`をベースとした速いコードを書くことができます。
|
|
181
181
|
|
|
182
182
|
（※参考：このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。）
|
24
テキスト修正
answer
CHANGED
|
@@ -179,4 +179,4 @@
|
|
|
179
179
|
|
|
180
180
|
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。
|
|
181
181
|
|
|
182
|
-
※このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。
|
|
182
|
+
（※参考：このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。）
|
23
テキスト修正
answer
CHANGED
|
@@ -177,6 +177,6 @@
|
|
|
177
177
|
```
|
|
178
178
|
のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。
|
|
179
179
|
|
|
180
|
-
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id` のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。
|
|
180
|
+
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id`プロパティ のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。
|
|
181
181
|
|
|
182
182
|
※このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。
|
22
テキスト修正
answer
CHANGED
|
@@ -169,7 +169,7 @@
|
|
|
169
169
|
```typescript
|
|
170
170
|
{ x: number; y: number }
|
|
171
171
|
```
|
|
172
|
-
という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係
|
|
172
|
+
という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係（つまり、ソート結果が一意になる比較関数）を定義できるかどうか検討することができて、もし（運良く）大小関係を定義できれば、Set や Map を使わない `getUnique13`やその元となっている `getUnique8`のようなコードを書けますが、もし、`a` や `b` の要素として入ってくるオブジェクトの型が不明という状況、すなわち、ご質問のタイトルにある
|
|
173
173
|
「二つの配列、それぞれに含まれるユニークな値をできるだけ高速に抽出する方法」
|
|
174
174
|
の一般解を求めようとすると、この回答の冒頭に挙げた
|
|
175
175
|
```javascript
|
21
テキスト修正
answer
CHANGED
|
@@ -169,10 +169,14 @@
|
|
|
169
169
|
```typescript
|
|
170
170
|
{ x: number; y: number }
|
|
171
171
|
```
|
|
172
|
-
という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係を定義できて（つまり、ソート結果が一意な
|
|
172
|
+
という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係を定義できて（つまり、ソート結果が一意な大小関係を定義できて）、Set や Map を使わない `getUnique13`やその元となっている `getUnique8`のようなコードを書けますが、もし、`a` や `b` の要素として入ってくるオブジェクトの型が不明という状況、すなわち、ご質問のタイトルにある
|
|
173
|
+
「二つの配列、それぞれに含まれるユニークな値をできるだけ高速に抽出する方法」
|
|
174
|
+
の一般解を求めようとすると、この回答の冒頭に挙げた
|
|
173
175
|
```javascript
|
|
174
176
|
const getUnique = (a,b) => _.differenceWith(a, b, _.isEqual);
|
|
175
177
|
```
|
|
176
178
|
のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。
|
|
177
179
|
|
|
178
|
-
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの比較関数、あるいは比較可能な（今回の `id` のような）そのオブジェクトのプリミティブ値を導入でき
|
|
180
|
+
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの大小比較関数、あるいは大小の比較が可能な（今回の `id` のような）そのオブジェクトのプリミティブ値(※)を導入できるかどうか検討することが、ある型を要素とする配列の差分抽出には優先順位の高いタスクかなと思われました。
|
|
181
|
+
|
|
182
|
+
※このような「そのオブジェクトの値を表すプリミティブ値を返す」ために、対象とするオブジェクト群専用の [valueOf()](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/valueOf) メソッドが定義される場合があります。
|
20
テキスト修正
answer
CHANGED
|
@@ -160,4 +160,19 @@
|
|
|
160
160
|
```
|
|
161
161
|
- ** getUnique13:** [https://jsfiddle.net/jun68ykt/h2ydp9sj/11/](https://jsfiddle.net/jun68ykt/h2ydp9sj/11/)
|
|
162
162
|
|
|
163
|
-
参考になれば幸いです。
|
|
163
|
+
参考になれば幸いです。
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
### 所感
|
|
167
|
+
|
|
168
|
+
ご質問のサンプルにあるように、配列`a` 配列 `b` ともにその要素はすべて
|
|
169
|
+
```typescript
|
|
170
|
+
{ x: number; y: number }
|
|
171
|
+
```
|
|
172
|
+
という型を満たしているという前提が明らかになっていれば、これを元に、問題の対象範囲に出現するオブジェクトの集合が全順序集合になるような、何らかの大小関係を定義できて（つまり、ソート結果が一意な比較関数を定義できて）、Set や Map を使わない `getUnique13`やその元となっている `getUnique8`のようなコードを書けますが、もし、`a` や `b` の要素として入ってくるオブジェクトの型が不明という状況だと、この回答の冒頭に挙げた
|
|
173
|
+
```javascript
|
|
174
|
+
const getUnique = (a,b) => _.differenceWith(a, b, _.isEqual);
|
|
175
|
+
```
|
|
176
|
+
のような時間のかかるコードに頼らざるを得なくなるのかなという気はいたします。
|
|
177
|
+
|
|
178
|
+
とはいえ、実際の何らかの問題領域においては、配列要素となるオブジェクトの型は何らか特定できるものなので、その型情報から、問題領域に出現し得るオブジェクト群が全順序を満たすような何らかの比較関数、あるいは比較可能な（今回の `id` のような）そのオブジェクトのプリミティブ値を導入できないかどうか検討することが、（ある型を要素とする）配列の差分抽出には優先順位の高いタスクかなと思われました。
|
19
テキスト修正
answer
CHANGED
|
@@ -145,9 +145,9 @@
|
|
|
145
145
|
b.sort((e1, e2) => e1.id - e2.id);
|
|
146
146
|
|
|
147
147
|
for (let iA=0, iB=0; iA < lenA || iB < lenB; ) {
|
|
148
|
-
if (iB
|
|
148
|
+
if (iB === lenB || iA < lenA && a[iA].id < b[iB].id) {
|
|
149
149
|
onlyA.push(a[iA ++]);
|
|
150
|
-
} else if (iA
|
|
150
|
+
} else if (iA === lenA || iB < lenB && b[iB].id < a[iA].id) {
|
|
151
151
|
onlyB.push(b[iB ++]);
|
|
152
152
|
} else {
|
|
153
153
|
iA ++;
|
|
@@ -158,6 +158,6 @@
|
|
|
158
158
|
return [onlyA, onlyB];
|
|
159
159
|
}
|
|
160
160
|
```
|
|
161
|
-
- ** getUnique13:** [https://jsfiddle.net/jun68ykt/h2ydp9sj/
|
|
161
|
+
- ** getUnique13:** [https://jsfiddle.net/jun68ykt/h2ydp9sj/11/](https://jsfiddle.net/jun68ykt/h2ydp9sj/11/)
|
|
162
162
|
|
|
163
163
|
参考になれば幸いです。
|
18
テキスト修正
answer
CHANGED
|
@@ -130,4 +130,34 @@
|
|
|
130
130
|
|
|
131
131
|
|
|
132
132
|
|
|
133
|
+
### 追記 - getUnique13
|
|
134
|
+
|
|
135
|
+
アルゴリズムとしては、`getUnique8` を拝借し、比較対象として、0以上の整数として設定される id(`const id = 1000 * x + y;`) を使うコードです。
|
|
136
|
+
|
|
137
|
+
```javascript
|
|
138
|
+
function getUnique13(a, b) {
|
|
139
|
+
const lenA = a.length,
|
|
140
|
+
lenB = b.length,
|
|
141
|
+
onlyA = [],
|
|
142
|
+
onlyB = [];
|
|
143
|
+
|
|
144
|
+
a.sort((e1, e2) => e1.id - e2.id);
|
|
145
|
+
b.sort((e1, e2) => e1.id - e2.id);
|
|
146
|
+
|
|
147
|
+
for (let iA=0, iB=0; iA < lenA || iB < lenB; ) {
|
|
148
|
+
if (iB >= lenB || iA < lenA && a[iA].id < b[iB].id) {
|
|
149
|
+
onlyA.push(a[iA ++]);
|
|
150
|
+
} else if (iA >= lenA || iB < lenB && b[iB].id < a[iA].id) {
|
|
151
|
+
onlyB.push(b[iB ++]);
|
|
152
|
+
} else {
|
|
153
|
+
iA ++;
|
|
154
|
+
iB ++;
|
|
155
|
+
}
|
|
156
|
+
}
|
|
157
|
+
|
|
158
|
+
return [onlyA, onlyB];
|
|
159
|
+
}
|
|
160
|
+
```
|
|
161
|
+
- ** getUnique13:** [https://jsfiddle.net/jun68ykt/h2ydp9sj/10/](https://jsfiddle.net/jun68ykt/h2ydp9sj/10/)
|
|
162
|
+
|
|
133
|
-
|
|
163
|
+
参考になれば幸いです。
|
17
テキスト修正
answer
CHANGED
|
@@ -17,7 +17,7 @@
|
|
|
17
17
|
|
|
18
18
|
### 追記 - getUnique10
|
|
19
19
|
|
|
20
|
-
上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きましたjsFiddleのテストコードによって生成されるオブジェクトの配列を処理することに特化し
|
|
20
|
+
上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きましたjsFiddleのテストコードによって生成されるオブジェクトの配列を処理することに特化したコードも考えてみました。以下の `getUnique10` になります。
|
|
21
21
|
|
|
22
22
|
```javascript
|
|
23
23
|
function getUnique10(a, b) {
|
16
テキスト修正
answer
CHANGED
|
@@ -128,4 +128,6 @@
|
|
|
128
128
|
|
|
129
129
|
当方の環境では、`getUnique12` のほうが数ミリ〜10ミリ秒程度、短くなる結果を確認しています。
|
|
130
130
|
|
|
131
|
+
|
|
132
|
+
|
|
131
133
|
以上、参考になれば幸いです。
|
15
テキスト修正
answer
CHANGED
|
@@ -90,8 +90,40 @@
|
|
|
90
90
|
|
|
91
91
|
### 追記 - getUnique12
|
|
92
92
|
|
|
93
|
-
先述の `getUnique11` のループで使っている、 `for ･･･ of` および `filter` を、 (ofなしの）`for`文に変更した、 `getUnique12` を作成しました。
|
|
93
|
+
先述の `getUnique11` のループで使っている、 `for ･･･ of` および `filter` を、 (ofなしの）`for`文に変更した、 `getUnique12` を作成しました。
|
|
94
94
|
|
|
95
|
+
```javascript
|
|
96
|
+
function getUnique12(a, b) {
|
|
97
|
+
const set = new Set();
|
|
98
|
+
|
|
99
|
+
const lenA = a.length;
|
|
100
|
+
const lenB = b.length;
|
|
101
|
+
|
|
102
|
+
for (let i=0; i < lenA; ++ i)
|
|
103
|
+
set.add(a[i].id);
|
|
104
|
+
|
|
105
|
+
for (let i=0; i < lenB; ++ i)
|
|
106
|
+
set.add(~b[i].id);
|
|
107
|
+
|
|
108
|
+
const onlyA = [];
|
|
109
|
+
for (let i=0; i < lenA; ++ i) {
|
|
110
|
+
if(!set.has(~a[i].id))
|
|
111
|
+
onlyA.push(a[i]);
|
|
112
|
+
}
|
|
113
|
+
|
|
114
|
+
const onlyB = [];
|
|
115
|
+
for (let i=0; i < lenB; ++ i) {
|
|
116
|
+
if(!set.has(b[i].id))
|
|
117
|
+
onlyB.push(b[i]);
|
|
118
|
+
}
|
|
119
|
+
|
|
120
|
+
return [onlyA, onlyB];
|
|
121
|
+
}
|
|
122
|
+
|
|
123
|
+
```
|
|
124
|
+
|
|
125
|
+
`getUnique11`との比較をするための jsFiddleが下記です。
|
|
126
|
+
|
|
95
127
|
- **getUnique11 vs getUnique12：** [https://jsfiddle.net/jun68ykt/ajtnd5wm/13/](https://jsfiddle.net/jun68ykt/ajtnd5wm/13/)
|
|
96
128
|
|
|
97
129
|
当方の環境では、`getUnique12` のほうが数ミリ〜10ミリ秒程度、短くなる結果を確認しています。
|
14
テキスト修正
answer
CHANGED
|
@@ -45,7 +45,7 @@
|
|
|
45
45
|
|
|
46
46
|
### 追記 - getUnique11
|
|
47
47
|
|
|
48
|
-
前掲の `getUnique10` の改良案を挙げます。この改良案は、(コメントに
|
|
48
|
+
前掲の `getUnique10` の改良案を挙げます。この改良案は、(2019/11/14 21:10のコメントに書いたとおり、） 下記
|
|
49
49
|
|
|
50
50
|
```javascript
|
|
51
51
|
const num = 1000;
|
13
テキスト修正
answer
CHANGED
|
@@ -74,7 +74,7 @@
|
|
|
74
74
|
return [onlyA, onlyB];
|
|
75
75
|
}
|
|
76
76
|
```
|
|
77
|
-
`getUnique10` では 2個の Set を使っていましたが、上記の `getUnique11` では、１個で済ませるようにして、Set 1個分のコンストラクタ `new Set()` の時間を減らすことを狙っています。Setを１個にした替わりに、b の要素の id をSet にaddするときに、
|
|
77
|
+
`getUnique10` では 2個の Set を使っていましたが、上記の `getUnique11` では、１個で済ませるようにして、Set 1個分のコンストラクタ `new Set()` の時間を減らすことを狙っています。Setを１個にした替わりに、b の要素の id をSet にaddするときに、a の要素のidと被らない値に変換する必要がありますが、その変換のために、（整数に対する演算として速いことが期待できる）ビット反転 `~` を使っています。
|
|
78
78
|
|
|
79
79
|
以下にて、 `getUnique10` と `getUnique11` とを比較できます。
|
|
80
80
|
|
12
テキスト修正
answer
CHANGED
|
@@ -45,7 +45,7 @@
|
|
|
45
45
|
|
|
46
46
|
### 追記 - getUnique11
|
|
47
47
|
|
|
48
|
-
前掲の `getUnique10` の改良案を挙げます。この改良案は、コメントには既に書きました、下記
|
|
48
|
+
前掲の `getUnique10` の改良案を挙げます。この改良案は、(コメントには既に書きましたが、） 下記
|
|
49
49
|
|
|
50
50
|
```javascript
|
|
51
51
|
const num = 1000;
|
11
テキスト修正
answer
CHANGED
|
@@ -38,7 +38,7 @@
|
|
|
38
38
|
|
|
39
39
|
この `getUnique10` を試すコードを以下の jsFiddle に作成しました。
|
|
40
40
|
|
|
41
|
-
- **
|
|
41
|
+
- **getUnique7 vs getUnique10：** [https://jsfiddle.net/jun68ykt/b501gqpj/1/](https://jsfiddle.net/jun68ykt/b501gqpj/1/)
|
|
42
42
|
|
|
43
43
|
上記は、コメントからご教示いただきました、 [https://jsfiddle.net/e9a5kvw2/](https://jsfiddle.net/e9a5kvw2/) を Forkして、テスト対象として`getUnique10` を追加したものです。
|
|
44
44
|
|
10
テキスト修正
answer
CHANGED
|
@@ -56,7 +56,7 @@
|
|
|
56
56
|
const id = 1000 * x + y;
|
|
57
57
|
･･･
|
|
58
58
|
```
|
|
59
|
-
のようなコードによって、 `id` に整数の値を設定することが前提になります。`getUnique11` は以下です。
|
|
59
|
+
のようなコードによって、 `id` に０以上の整数の値を設定することが前提になります。`getUnique11` は以下です。
|
|
60
60
|
|
|
61
61
|
```javascript
|
|
62
62
|
function getUnique11(a, b) {
|
9
テキスト修正
answer
CHANGED
|
@@ -56,7 +56,7 @@
|
|
|
56
56
|
const id = 1000 * x + y;
|
|
57
57
|
･･･
|
|
58
58
|
```
|
|
59
|
-
のようなコードによって、 `id` に数値を設定することが前提になります。`getUnique11` は以下です。
|
|
59
|
+
のようなコードによって、 `id` に整数の値を設定することが前提になります。`getUnique11` は以下です。
|
|
60
60
|
|
|
61
61
|
```javascript
|
|
62
62
|
function getUnique11(a, b) {
|
8
テキスト修正
answer
CHANGED
|
@@ -17,7 +17,7 @@
|
|
|
17
17
|
|
|
18
18
|
### 追記 - getUnique10
|
|
19
19
|
|
|
20
|
-
上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きました
|
|
20
|
+
上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きましたjsFiddleのテストコードによって生成されるオブジェクトの配列を処理することに特化して、なるべく高速に処理するコードも考えてみました。以下の `getUnique10` になります。
|
|
21
21
|
|
|
22
22
|
```javascript
|
|
23
23
|
function getUnique10(a, b) {
|
7
テキスト修正
answer
CHANGED
|
@@ -17,7 +17,7 @@
|
|
|
17
17
|
|
|
18
18
|
### 追記 - getUnique10
|
|
19
19
|
|
|
20
|
-
lodashを使
|
|
20
|
+
上記ではlodashを使った汎用的なコードを挙げましたが、コメントから頂きました、jsFiddleのテストコードによって生成させるオブジェクトの配列を処理することに特化して、なるべく高速に処理するコードも考えてみました。以下の `getUnique10` になります。
|
|
21
21
|
|
|
22
22
|
```javascript
|
|
23
23
|
function getUnique10(a, b) {
|
|
@@ -36,11 +36,11 @@
|
|
|
36
36
|
}
|
|
37
37
|
```
|
|
38
38
|
|
|
39
|
-
|
|
39
|
+
この `getUnique10` を試すコードを以下の jsFiddle に作成しました。
|
|
40
40
|
|
|
41
|
-
- **
|
|
41
|
+
- **getUnique10 vs getUnique7：** [https://jsfiddle.net/jun68ykt/b501gqpj/1/](https://jsfiddle.net/jun68ykt/b501gqpj/1/)
|
|
42
42
|
|
|
43
|
-
|
|
43
|
+
上記は、コメントからご教示いただきました、 [https://jsfiddle.net/e9a5kvw2/](https://jsfiddle.net/e9a5kvw2/) を Forkして、テスト対象として`getUnique10` を追加したものです。
|
|
44
44
|
|
|
45
45
|
|
|
46
46
|
### 追記 - getUnique11
|
6
テキスト修正
answer
CHANGED
|
@@ -88,4 +88,12 @@
|
|
|
88
88
|
のように、`getUnique11`の所要時間のほうが、`getUnique10` の所要時間よりも短くなる結果を得ています。
|
|
89
89
|
|
|
90
90
|
|
|
91
|
+
### 追記 - getUnique12
|
|
92
|
+
|
|
93
|
+
先述の `getUnique11` のループで使っている、 `for ･･･ of` および `filter` を、 (ofなしの）`for`文に変更した、 `getUnique12` を作成しました。`getUnique11`との比較をするための jsFiddleが下記です。
|
|
94
|
+
|
|
95
|
+
- **getUnique11 vs getUnique12：** [https://jsfiddle.net/jun68ykt/ajtnd5wm/13/](https://jsfiddle.net/jun68ykt/ajtnd5wm/13/)
|
|
96
|
+
|
|
97
|
+
当方の環境では、`getUnique12` のほうが数ミリ〜10ミリ秒程度、短くなる結果を確認しています。
|
|
98
|
+
|
|
91
99
|
以上、参考になれば幸いです。
|
5
テキスト修正
answer
CHANGED
|
@@ -45,7 +45,7 @@
|
|
|
45
45
|
|
|
46
46
|
### 追記 - getUnique11
|
|
47
47
|
|
|
48
|
-
|
|
48
|
+
前掲の `getUnique10` の改良案を挙げます。この改良案は、コメントには既に書きました、下記
|
|
49
49
|
|
|
50
50
|
```javascript
|
|
51
51
|
const num = 1000;
|
4
テキスト修正
answer
CHANGED
|
@@ -45,7 +45,7 @@
|
|
|
45
45
|
|
|
46
46
|
### 追記 - getUnique11
|
|
47
47
|
|
|
48
|
-
上記の `getUnique10` の改良案を挙げます。
|
|
48
|
+
上記の `getUnique10` の改良案を挙げます。この改良案は、コメントには既に書きました、下記
|
|
49
49
|
|
|
50
50
|
```javascript
|
|
51
51
|
const num = 1000;
|
|
@@ -56,7 +56,7 @@
|
|
|
56
56
|
const id = 1000 * x + y;
|
|
57
57
|
･･･
|
|
58
58
|
```
|
|
59
|
-
にて、 `id`
|
|
59
|
+
のようなコードによって、 `id` に数値を設定することが前提になります。`getUnique11` は以下です。
|
|
60
60
|
|
|
61
61
|
```javascript
|
|
62
62
|
function getUnique11(a, b) {
|
3
テキスト修正
answer
CHANGED
|
@@ -74,7 +74,7 @@
|
|
|
74
74
|
return [onlyA, onlyB];
|
|
75
75
|
}
|
|
76
76
|
```
|
|
77
|
-
`getUnique10` では 2個の Set を使っていましたが、上記の `getUnique11` では、１個で済ませるようにして、Set 1個分のコンストラクタの時間を減らすことを狙っています。Setを１個にした替わりに、b の要素の id をSet にaddするときに、それが b の要素のid であることが分かるように、ビット反転した値を add しています。
|
|
77
|
+
`getUnique10` では 2個の Set を使っていましたが、上記の `getUnique11` では、１個で済ませるようにして、Set 1個分のコンストラクタ `new Set()` の時間を減らすことを狙っています。Setを１個にした替わりに、b の要素の id をSet にaddするときに、それが b の要素のid であることが分かるように、ビット反転した値を add しています。
|
|
78
78
|
|
|
79
79
|
以下にて、 `getUnique10` と `getUnique11` とを比較できます。
|
|
80
80
|
|
2
テキスト修正
answer
CHANGED
|
@@ -43,4 +43,49 @@
|
|
|
43
43
|
これは、コメントからご教示いただきました、 [https://jsfiddle.net/e9a5kvw2/](https://jsfiddle.net/e9a5kvw2/) を Forkして、テスト対象として`getUnique10` を追加したものです。
|
|
44
44
|
|
|
45
45
|
|
|
46
|
+
### 追記 - getUnique11
|
|
47
|
+
|
|
48
|
+
上記の `getUnique10` の改良案を挙げます。ただしこの改良案は、コメントに書いたように、下記
|
|
49
|
+
|
|
50
|
+
```javascript
|
|
51
|
+
const num = 1000;
|
|
52
|
+
for (let i = 0; i < num; i++) {
|
|
53
|
+
const x = i;
|
|
54
|
+
const y = Math.floor(Math.random() * num);
|
|
55
|
+
// const id = `${x}:${y}`
|
|
56
|
+
const id = 1000 * x + y;
|
|
57
|
+
･･･
|
|
58
|
+
```
|
|
59
|
+
にて、 `id` を数値として設定することが前提になります。`getUnique11` は以下です。
|
|
60
|
+
|
|
61
|
+
```javascript
|
|
62
|
+
function getUnique11(a, b) {
|
|
63
|
+
const set = new Set();
|
|
64
|
+
|
|
65
|
+
for (let e of a)
|
|
66
|
+
set.add(e.id);
|
|
67
|
+
|
|
68
|
+
for (let e of b)
|
|
69
|
+
set.add(~e.id);
|
|
70
|
+
|
|
71
|
+
const onlyA = a.filter(e => !set.has(~e.id));
|
|
72
|
+
const onlyB = b.filter(e => !set.has(e.id));
|
|
73
|
+
|
|
74
|
+
return [onlyA, onlyB];
|
|
75
|
+
}
|
|
76
|
+
```
|
|
77
|
+
`getUnique10` では 2個の Set を使っていましたが、上記の `getUnique11` では、１個で済ませるようにして、Set 1個分のコンストラクタの時間を減らすことを狙っています。Setを１個にした替わりに、b の要素の id をSet にaddするときに、それが b の要素のid であることが分かるように、ビット反転した値を add しています。
|
|
78
|
+
|
|
79
|
+
以下にて、 `getUnique10` と `getUnique11` とを比較できます。
|
|
80
|
+
|
|
81
|
+
- **getUnique10 vs getUnique11：** [https://jsfiddle.net/jun68ykt/ajtnd5wm/5/](https://jsfiddle.net/jun68ykt/ajtnd5wm/5/)
|
|
82
|
+
|
|
83
|
+
当方の環境（PC: Macbook Pro(Core i7 2.8GHz), ブラウザ： Chrome バージョン: 78.0.3904.97)では、以下
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
|
|
88
|
+
のように、`getUnique11`の所要時間のほうが、`getUnique10` の所要時間よりも短くなる結果を得ています。
|
|
89
|
+
|
|
90
|
+
|
|
46
91
|
以上、参考になれば幸いです。
|
1
テキスト修正
answer
CHANGED
|
@@ -12,4 +12,35 @@
|
|
|
12
12
|
|
|
13
13
|
- **例2:** [https://codepen.io/jun68ykt/pen/GRRBEYj?editors=0012](https://codepen.io/jun68ykt/pen/GRRBEYj?editors=0012)
|
|
14
14
|
|
|
15
|
+
|
|
16
|
+
|
|
17
|
+
|
|
18
|
+
### 追記 - getUnique10
|
|
19
|
+
|
|
20
|
+
lodashを使わずに、なるべく高速に処理するコードも考えてみました。以下の `getUnique10` になります。
|
|
21
|
+
|
|
22
|
+
```javascript
|
|
23
|
+
function getUnique10(a, b) {
|
|
24
|
+
const [setA, setB] = [new Set(), new Set()];
|
|
25
|
+
|
|
26
|
+
for (let e of a)
|
|
27
|
+
setA.add(e.id);
|
|
28
|
+
|
|
29
|
+
for (let e of b)
|
|
30
|
+
setB.add(e.id);
|
|
31
|
+
|
|
32
|
+
const onlyA = a.filter(e => !setB.has(e.id));
|
|
33
|
+
const onlyB = b.filter(e => !setA.has(e.id));
|
|
34
|
+
|
|
35
|
+
return [onlyA, onlyB]
|
|
36
|
+
}
|
|
37
|
+
```
|
|
38
|
+
|
|
39
|
+
上記の `getUnique10` を試すコードを以下の jsFiddle に作成しました。
|
|
40
|
+
|
|
41
|
+
- **動作確認用 jsFiddle :** [https://jsfiddle.net/jun68ykt/b501gqpj/1/](https://jsfiddle.net/jun68ykt/b501gqpj/1/)
|
|
42
|
+
|
|
43
|
+
これは、コメントからご教示いただきました、 [https://jsfiddle.net/e9a5kvw2/](https://jsfiddle.net/e9a5kvw2/) を Forkして、テスト対象として`getUnique10` を追加したものです。
|
|
44
|
+
|
|
45
|
+
|
|
15
46
|
以上、参考になれば幸いです。
|