前提・実現したいこと
次のような配列ar1
, ar2
があるとき、
それぞれのid
をキーとして、rev
の大きさを基準に重複を削除した
配列を出力するような関数を作りたいと思っています。
(id
が重複せず片方のみに存在する場合は、そのまま結果配列に追加)
js
1const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] 2const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] 3 4...処理... 5 6console.log(result) 7// => [{id:'a1', rev:2, val:11}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}, {id:'c1', rev:2, val:30}]
そこでfor
を使った関数を作成しましたが、どうも見辛くスマートさに欠けるため
map
やfilter
などのイテレーター的な関数を使って書き直せないものかと思っています。
皆様のお知恵を拝借させて頂ければ幸いです。
よろしくお願いいたします。
作成したソースコード
js
1function mergeArrayBasedIDByRevision(array1, array2){ 2 //両方の配列を結合 3 let pre = array1.concat(array2); 4 //結果出力用配列を用意 5 let result = []; 6 for (let i of pre) { 7 let tmp = i; 8 //結果を格納する配列に重複がないかチェック 9 let found = false; 10 for (let j of pre) { 11 if (i.id == j.id) { 12 //同じidが見つかった場合、まず結果を格納する配列にすでに存在していないかをチェック 13 for (let k in result) { 14 if (result[k].id == i.id) { 15 found = true; 16 } 17 } 18 //revのidを比較し、高い方を一時変数に格納 19 if (!found) { 20 if (j.rev > tmp.rev) { 21 tmp = j; 22 } 23 } 24 } 25 } 26 //結果を格納する配列にidの重複がなかった場合のみ、一時変数の中身を追加。 27 if (!found) { 28 result.push(tmp); 29 } 30 } 31} 32 33//実行 34let result = mergeArrayBasedIDByRevision(ar1, ar2) 35console.log(result); 36// => [{id:'a1', rev:2, val:11}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}, {id:'c1', rev:2, val:30}] 37
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答8件
0
ベストアンサー
LodashかRamda.jsのGroupByを使いましょう。
質問文のコードをざっと読んでやりたそうな事をLodashで書いてみました。
JavaScript
1const mergeArrayBasedIDByRevision = (array1, array2) => 2 _.chain(array1) 3 .concat(array2) 4 .groupBy(it => it.id) 5 .map(its => _.maxBy(its, it => it.rev)) 6 .value(); 7 8const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] 9const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] 10 11result = mergeArrayBasedIDByRevision(ar1, ar2)
なんということでしょう、匠の手によってわずか6行に関数に大変身!
というわけで、LodashやRamda.jsの扱いに慣れれば、
この程度の処理なら関数化する必要すらありません。
これをLodash Codeに打ち込んだら結果はこうなります。
[ { "id": "a1", "rev": 2, "val": 11 }, { "id": "a2", "rev": 2, "val": 15 }, { "id": "b1", "rev": 1, "val": 20 }, { "id": "c1", "rev": 2, "val": 30 } ]
計算量は2n+α程度なので質問文のn^2に比べれば凄まじく速いでしょう。
まぁ、LodashやRamda.jsは全部眺めて暗記する位の価値があって、
必死に数十行もタイプする無駄な時間が一桁行に収まるのでプログラマとして生きていくつもりならぜひ覚えましょう
この考え方は他の言語にも通用しますしね。
ネイティブJSでやるなら多少Lodashより高速なものが書けると思いますが、
まぁまぁ検討してもそんなに速度は上がらないと思います。
Lodashのコードとアルゴリズム一緒で速度もほぼ同等なものならこんな感じ、
ちょっと読みづらくはなってますが、まぁまぁ平易なレベルに抑えられえているといった感じです。
const mergeArrayBasedIDByRevision = (array1, array2) => { const byId = {}; for (let it of array1.concat(array2)) { if (!byId[it.id]) byId[it.id] = []; byId[it.id].push(it); } return Object.values(byId) .map(its => its.reduce((max, it) => it.rev > max.rev ? it : max) ) } const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] console.log(mergeArrayBasedIDByRevision(ar1, ar2)); // (4) [{…}, {…}, {…}, {…}] // 0: {id: "a1", rev: 2, val: 11} // 1: {id: "a2", rev: 2, val: 15} // 2: {id: "b1", rev: 1, val: 20} // 3: {id: "c1", rev: 2, val: 30}
keiさんのコードをヒントにいじったのがこちら
スマートになりつつの速度確保もそれなりに良い感じに仕上がってると思います。
JavaScript
1// 別に2個の配列の引数に限定せず、3個でも4個でも受け付けるようになったけどいいよね? 2const mergeArrayBasedIDByRevision = (...arrayList) => { 3 const result = {}; 4 // for...ofかforEachかは正直好み 5 for (let array of arrayList) { 6 for (let it of array) { 7 if (it.rev > ((result[it.id] || {}).rev || 0)) { 8 result[it.id] = it; 9 } 10 } 11 } 12 return Object.values(result); 13} 14 15const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] 16const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] 17 18console.log(mergeArrayBasedIDByRevision(ar1, ar2)); 19// (4) [{…}, {…}, {…}, {…}] 20// 0: {id: "a1", rev: 2, val: 11} 21// 1: {id: "a2", rev: 2, val: 15} 22// 2: {id: "b1", rev: 1, val: 20} 23// 3: {id: "c1", rev: 2, val: 30}
投稿2019/01/14 13:48
編集2019/01/14 14:14総合スコア21158
0
js
1const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] 2const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] 3 4const result = Object.values( [ ...ar1, ...ar2 ].reduce( ( pre,curr )=>{ 5 if ( !pre.hasOwnProperty( curr.id ) || pre[ curr.id ].rev < curr.rev ) { 6 pre[ curr.id ] = curr; 7 } 8 return pre; 9}, {} ) ); 10 11console.log(result) 12/* 13(4) […] 140: Object { id: "a1", rev: 2, val: 11 } 151: Object { id: "a2", rev: 2, val: 15 } 162: Object { id: "b1", rev: 1, val: 20 } 173: Object { id: "c1", rev: 2, val: 30 } 18length: 4 19*/ 20```**動くサンプル:**[https://jsfiddle.net/nyrvgpjc/](https://jsfiddle.net/nyrvgpjc/) 21 22--- 23 24【Object.values() | MDN】 25[https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/values](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/values) 26 27【スプレッド構文 | MDN】 28[https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Spread_syntax](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Spread_syntax) 29 30【Array.prototype.reduce() | MDN】 31[https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce) 32 33【Object.prototype.hasOwnProperty() | MDN】 34[https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwnProperty](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwnProperty)
投稿2019/01/14 03:03
総合スコア69364
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
こんにちは
ご質問の趣旨としては、
for
によるループを使うかわりにArray
のメソッドのmap
やfilter
といった、関数を引数として受け取れるもの、すなわち高階関数 を使ったコードにしたい
というものと拝察しました。この回答では、そういった関数の使用事例となるように、コード1から6までの複数のコードを回答します。これらは、短いコードで済ませることを主眼においているので、
- 関数
mergeArrayBasedIDByRevision
本体の最初の行にreturn
を書いて、return
する対象の中にロジックを(あえて)詰め込みました。
- アロー関数
=>
を使う際に、アローの先にある関数本体の記述に、return
を使わないで済ませるようにしました。
上記2点により、コード1から6までのいずれも、セミコロン ;
は return
文の末尾にしか使われていないものになっています。ただしコードが短くなっただけで、効率が悪く処理時間が長くかかってしまうような例も挙げています。
また、以下をあらかじめ補足しておきます。
- 2つの配列の効率的な連結方法についてはご質問の本題ではないと思われたので、ご質問のコードでお使いになっている
concat
をそのまま使っていますが、ご興味あればこの質問と回答が面白いかもしれません。
mergeArrayBasedIDByRevision()
の引数をarray1
とarray2
の2つから、任意の N 個にすることはご質問の主旨から逸脱すると考えたため対応していませんが、mergeArrayBasedIDByRevision(array1, array2)
を使えば、任意の N 個に対応することは簡単にできることを補足3に追記しました。
- 簡単な性能比較を補足4に追記しました。
コード1
reduce, Map, スプレッド構文を使います。
javascript
1function mergeArrayBasedIDByRevision(array1, array2) { 2 return [... 3 array1 4 .concat(array2) 5 .reduce( 6 (map, e) => 7 (map.get(e.id) || {}).rev >= e.rev 8 ? map 9 : map.set(e.id, e) 10 , new Map()) 11 .values() 12 ]; 13}
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/suL7tx3k/12/
コード2
Map を使わず find と filter を使ってみたコードです。
javascript
1function mergeArrayBasedIDByRevision(array1, array2) { 2 return array1.concat(array2).reduce( 3 (ary, e) => 4 (ary.find(e2 => e2.id === e.id) || {}).rev >= e.rev 5 ? ary 6 : [...ary.filter(e3 => e3.id !== e.id), e] 7 , [] 8 ); 9}
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/b9kseywr/10/
ただし、e.id
と同じidの要素が除去された配列を作るのに、ary.filter(e3 => e3.id !== e.id)
としている所が無駄です。なぜかというとary.filter
とすると ary
の全要素を走査してしまいますが、ary
の中には同じid
の要素は最大でも1個しかないからです。
また、ary
の中にある、ある特定idの要素を探すのに find
を使っていますが、find
だと先頭から順に探していくので、これも効率悪いです。
コード3
ar1 と ar2 を結合して、idの昇順+revの降順でソートし、ソート結果から各idのrevが最大のものだけをピックアップします。
javascript
1function mergeArrayBasedIDByRevision(array1, array2) { 2 return array1.concat(array2) 3 .sort((e1, e2) => e1.id.localeCompare(e2.id) || e2.rev - e1.rev) 4 .filter((e, i, ary) => i === ary.findIndex(e3 => e3.id === e.id)); 5}
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/zLodvq7c/3/
ただし、要素すべてについてary.findIndex(e3 => e3.id === e.id)
を毎回やるので無駄が多いです。
コード4,5
array1 と array2を結合した配列を revの昇順でソートし、map で各要素を適切に変形したうえで、Object.assign ないし Mapのコンストラクターに渡します。
コード4
javascript
1function mergeArrayBasedIDByRevision(array1, array2) { 2 return Object.values( 3 Object.assign({}, 4 ...array1.concat(array2) 5 .sort((e1, e2) => e1.rev - e2.rev) 6 .map(e => ({[e.id]: e})) 7 ) 8 ); 9}
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/jf1283mg/13/
コード5
javascript
1function mergeArrayBasedIDByRevision(array1, array2) { 2 return [... 3 new Map( 4 array1.concat(array2) 5 .sort((e1, e2) => e1.rev - e2.rev) 6 .map(e => [e.id, e]) 7 ).values() 8 ]; 9}
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/a4hpgLtn/3/
コード6 (コード3の修正版)
先に挙げたコード3の問題点だった、filter の判定 i === ary.findIndex(e3 => e3.id === e.id)
を修正しました。
javascript
1function mergeArrayBasedIDByRevision(array1, array2) { 2 return array1.concat(array2) 3 .sort((e1, e2) => e1.id.localeCompare(e2.id) || e2.rev - e1.rev) 4 .filter((e, i, ary) => i === 0 || e.id !== ary[i-1].id); 5}
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/h6ob920e/1/
補足1
このご質問の場合、idをキーとする何らかのマップ構造(JavaScriptならプレーンオブジェクトかMapオブジェクト)を経由するのが順当な方法と思われますので、上記の6つの中で選ぶとすれば、コード1, 4, 5 のやり方を参考にされることをお勧めします。配列からいったんマップ構造を経由するのが適切なときに、配列のまま filterやfindで頑張ろうとすると、要件を満たせて見た目上のコードを短くできたとしても、非効率なロジックになってしまっていることが、ままあります。コード2, 3 は、そのような例と思って頂いてかまいません。
補足2
コード3の問題点を修正したコード6を追記しました。この修正によって、idをキーとするMapやプレーンオブジェクトを経由しないで配列のままでどうにかする方法の一案として、そこそこ実用に耐えうるものになったのではと思います。
補足3
任意の N 個の配列 ar1, ar2, ... ar__N__ から result を作る処理について補足しておきます。
ご質問に提示されている、2つの配列 array1
, array2
を引数として受け取り、これらをマージした配列を返す関数
function mergeArrayBasedIDByRevision(array1, array2)
を作っておけば、 N 個の配列 ar1, ar2, ... ar__N__ から result を作る処理は、mergeArrayBasedIDByRevision
を修正しなくても、以下のようにすれば済みます。
javascript
1const result = [ar1, ar2, ... arN].reduce(mergeArrayBasedIDByRevision);
- **動作確認用のサンプル: ** https://jsfiddle.net/jun68ykt/h6ob920e/7/
今回のご質問では、map
や filter
といった高階関数を使ってmergeArrayBasedIDByRevision
を書き直すことがお題ですが、mergeArrayBasedIDByRevision
自体もまた、(上記のreduce
のような)高階関数の引数として渡すことができます。
回答のコード1とコード2でも使いましたが、reduceを使いこなせると色々な場面で重宝します。
補足4
コード1から6までの簡単な性能比較を行いました。方法は
-
2つの配列
ar1
とar2
をともに長さ25万の配列(つまりar1.concat(ar2)
の長さは50万)として用意 -
配列要素の各プロパティは以下のとおり:
id
: /^[a-z][0-9]{2}$/
という形式の文字列(従って2600通り)をランダム生成(例: a00
, h56
)
rev
: 0以上 125000以下の整数をランダム生成
val
: 0
上記のような ar1
と ar2
を用意し、各コードのmergeArrayBasedIDByRevision(ar1, ar2)
を実行して、その所要時間を計測しました。その結果が以下です。
No. | 結果 |
---|---|
コード1 | 0.052 秒 |
コード2 | 10.767 秒 |
コード3 | 5分経過しても終わらず |
コード4 | エラー終了 |
コード5 | 0.63 秒 |
コード6 | 5.14 秒 |
- 使用PC: MacBookPro (CPU:core i7 2.7GHz, メモリ16GB)
- コード4のエラー原因: Maximum call stack size exceeded
結果をみると、コード1の性能が良いです。注目すべき差としては、まず、コード1とコード2の結果の差です。コード1で使っていたMapの働きを、コード2ではfind と filter でやってみたわけですが、これだけの差になってしまいました。それと、コード3が5分経っても終わらなかったのが、コード6に修正したことで5秒程度で正常終了するようになりました。コード4 については、上記の表には書いてませんが ar1
, ar2
ともに 5万件ずつの計10万件だと、約0.2秒かかって正常終了しました。
実用的には、結果から見る限り、コード1がお勧めということになりますが、回答に載せているコードのままだと、若干読みにくいコードかと思われますので、一時的な変数を追加したり、インデントを修正するなど、適宜リファクタリングして頂ければと思います。
投稿2019/01/14 04:24
編集2019/01/21 01:30総合スコア9058
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/02/18 20:07
2019/02/19 16:35
0
スマート
そこでforを使った関数を作成しましたが、どうも見辛くスマートさに欠けるため
mapやfilterなどのイテレーター的な関数を使って書き直せないものかと思っています。
スマートというのは無駄を省く意味があると思いますが、そこから何を無駄で何が必要かの判断基準が人それぞれなので、一口に「スマート」と言い切ってコードを求めるのは無理があると私は思います。
私はパフォーマンス重視なので、concat
の配列走査を無駄に感じてしまう口です(そして、一般に concat は遅いのです)。
JavaScript
1let pre = array1.concat(array2);
また、ループ回数が多ければ速度低下する為、出来るだけ少なくすべきです。
Array.prototype に紐づく、map, filter等は一見、コードを短く見せてくれますが、呼び出す度に全ての要素を走査してる為、無駄にループ回数を増やす原因にもなります。
配列の要素検索は配列全体を検索しますが、オブジェクトのキー参照、Map#get
はそうではありません。
コード
以上の思想で完成したのがこちら。
(可変長引数は要件にありませんが、汎用性は上げた方が美しいと私は思います)
JavaScript
1'use strict'; 2function mergeArrayBasedIDByRevision (array1 /* [...array]*/) { 3 const map = new Map; 4 5 for (let current of array1) { 6 map.set(current.id, current); 7 } 8 9 for (let i = 1, len = arguments.length; i < len; ++i) { 10 const array = arguments[i]; 11 12 for (let current of array) { 13 const id = current.id; 14 if (!map.has(id) || map.get(id).rev < current.rev) { 15 map.set(id, current); 16 } 17 } 18 } 19 20 return Array.from(map.values()); 21} 22 23const array1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}]; 24const array2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}]; 25 26console.log(JSON.stringify(mergeArrayBasedIDByRevision(array1, array2))); // [{"id":"a1","rev":2,"val":11},{"id":"a2","rev":2,"val":15},{"id":"b1","rev":1,"val":20},{"id":"c1","rev":2,"val":30}]
id がユニークであるなら、配列ではなく、初めから Map
でデータを持っておく方がスマートだと思います。
Re: yokatone さん
投稿2019/01/14 06:52
編集2019/01/14 07:13総合スコア18156
0
javascript
1const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] 2const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] 3 4{ 5 const vmax = (...arg) => Math.max.apply (Math, arg); 6 7 class V { 8 constructor ({id, rev, val}) { 9 this.id = id; 10 this.rev = rev; 11 this.val = val; 12 } 13 14 ovw ({rev, val}) { 15 this.rev = vmax (this.rev, rev); 16 this.val = vmax (this.val, val); 17 } 18 } 19 20 this.V = V; 21} 22 23function merge (...arg) { 24 const M = new Map (); 25 26 let ary = [].concat (...arg); 27 ary.forEach (a => M.has (a.id) ? M.get(a.id).ovw (a): M.set (a.id, new V (a))); 28 return [...M.values()]; 29} 30 31console.log (merge (ar1, ar2)); 32
投稿2019/01/15 00:05
退会済みユーザー
総合スコア0
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
連想配列を使ってみました。
javascript
1const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}] 2const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}] 3var dic = {} 4ar1.forEach(function(e){ 5 dic[e.id] = e; 6}); 7ar2.forEach(function(e){ 8 if(!dic[e.id]){ 9 dic[e.id] = e; 10 }else if(dic[e.id].rev < e.rev){ 11 dic[e.id] = e; 12 } 13}); 14let result=[]; 15for(let index in dic){ 16 result.push(dic[index]); 17} 18console.log(result); 19
投稿2019/01/14 03:05
退会済みユーザー
総合スコア0
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
一応
javascript
1const ar1 = [{id:'a1', rev:1, val:10}, {id:'a2', rev:2, val:15}, {id:'b1', rev:1, val:20}]; 2const ar2 = [{id:'a1', rev:2, val:11}, {id:'a2', rev:1, val:12}, {id:'c1', rev:2, val:30}]; 3let ar3 = ar1.concat(ar2); 4ar3=ar3.map(x=>x.id).filter((x,i,self)=>self.indexOf(x)===i).map(x=>ar3.filter(y=>y.id==x)).map(x=>x.sort((y,z)=>y.rev>z.rev?-1:1)[0]); 5console.log(ar3);
投稿2019/01/16 04:58
総合スコア114572
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
ループの無駄を省いたバージョン
of でやるよりループ回数はそれなりに減る。
function mergeArrayBasedIDByRevision(array1, array2){ let pre = array1.concat(array2); let result = []; let ids = []; for (let i = 0; i < pre.length; i++) { let curr = pre[i]; if (ids[curr.id]) continue; ids[curr.id] = i; let check = curr; for (let j = i + 1; j < pre.length; j++) { let tag = pre[j]; if (check.id != tag.id) continue; if (check.rev < tag.rev) check = tag; } result.push(check); } return result; }
結果
[ { id :a1,rev : 2, val : 11} { id :a2,rev : 2, val : 15} { id :b1,rev : 1, val : 20} { id :c1,rev : 2, val : 30} ]
投稿2019/01/14 03:20
退会済みユーザー
総合スコア0
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/02/18 20:07