javascriptによるアルゴリズムの実装

jsに関する質問です。

[
{chose: "javascript",
  questionId: {
   options: [ "javascript","python","c","R"],
   _id: 123,
  }
 },
{chose: "ramen",
  questionId: {
   options: [ "ramen", "sushi","teriyaki","duck"],
   _id: 456,
  }
 },
{chose: "python",
  questionId: {
   options: [ "javascript","python","c","R"],
   _id: 123,
  }
 },
{chose: "javascript",
  questionId: {
   options: [ "javascript","python","c","R"],
   _id: 123,
  }
 },
]

仮に上のようなinputがあったとして最終的に、下のような配列を返すfunctionを作りたいです。

[
 {
  questionId: 123,
  javascript: 2,
  python: 1,
  c: 0,
  R: 0,
  },
 {
   questionId: 456
   ramen: 1,
   sushi: 0,
   teriyaki : 0,
   duck: 0
 }
]

私は以下のように書きました。しかし、結果空の配列が出力されてしまいます。

const getStats = (answers) => {
  let stats = [];
  answers.forEach((answer) => {
    let empty = {};
    empty.questionId = answer.questionId._id;
    answer.questionId.options.forEach((option) => {
      empty[option] = 0;
    });
    for (let i = 0; i < stats.length; i++) {
      if (stats[i].questionId === empty.questionId) {
        stats[i][answer.chose]++;
      } else {
        empty[answer.chose]++;
        stats.push(empty);
      }
    }
  });
  return stats;
};

解ける方いますか？？もし計算量の少ない記述ができるのであればなお嬉しいです。

退会済みユーザー

2021/06/29 20:41

まずは仕様を日本語で適切に説明できるようになると良いですよ。今の説明だと、「下のような配列」をそのまま返すだけの関数が最も計算量が少なくなります。

退会済みユーザー

2021/06/30 09:00

01110000 01101001 01101110 01100011 01101000 01100101 00100000 01100100 01100101 00100000 01110100 01110101 00100000 01110000 01110101 01110100 01100001 00100000 01101110 01100101 01110100 01101001 01111010 01100101 01101110

退会済みユーザー

2021/06/30 09:18

ただのアルゴリズム実装法のアドバイスなんだけどね＾＾；一応、暴言コメントは通報しときますが。

行動規範の内容に同意します

回答1件

ベストアンサー

計算量はともかく
そもそも動かないのはお話にならないので
Lodashを使う等工夫しましょう。

online lodash testerで動作検証します。

js
1const start = [
2{chose: "javascript",
3  questionId: {
4   options: [ "javascript","python","c","R"],
5   _id: 123,
6  }
7 },
8{chose: "ramen",
9  questionId: {
10   options: [ "ramen", "sushi","teriyaki","duck"],
11   _id: 456,
12  }
13 },
14{chose: "python",
15  questionId: {
16   options: [ "javascript","python","c","R"],
17   _id: 123,
18  }
19 },
20{chose: "javascript",
21  questionId: {
22   options: [ "javascript","python","c","R"],
23   _id: 123,
24  }
25 },
26];
27
28result = _.chain(start)
29  .groupBy(it => it.questionId._id)
30  .values()
31  .map(questions => {
32    const options = questions[0]
33      .questionId
34      .options
35      .reduce((obj, it) => ({...obj, [it]: 0}), {});
36    questions.forEach(({chose}) => options[chose]++);
37    return {
38      questionId: questions[0].questionId._id,
39      ...options
40    }
41  })
42  .value();

結果

JSON
1[
2   {
3      "questionId": 123,
4      "javascript": 2,
5      "python": 1,
6      "c": 0,
7      "R": 0
8   },
9   {
10      "questionId": 456,
11      "ramen": 1,
12      "sushi": 0,
13      "teriyaki": 0,
14      "duck": 0
15   }
16]

さて、ではネイティブのJSで何とかする方法を考えていきます。
groupByからのvaluesのコンボでスマートに解決する問題は非常に多いです。
なのでLodashに限らず、多くの関数型プログラミング言語に存在する概念だったりします。

Lodash等の関数型プログラミング用ライブラリを使えばすぐですが、
その気になればJSのreduceメソッドを使って置き換える事が出来ます。

js
1const start = [
2{chose: "javascript",
3  questionId: {
4   options: [ "javascript","python","c","R"],
5   _id: 123,
6  }
7 },
8{chose: "ramen",
9  questionId: {
10   options: [ "ramen", "sushi","teriyaki","duck"],
11   _id: 456,
12  }
13 },
14{chose: "python",
15  questionId: {
16   options: [ "javascript","python","c","R"],
17   _id: 123,
18  }
19 },
20{chose: "javascript",
21  questionId: {
22   options: [ "javascript","python","c","R"],
23   _id: 123,
24  }
25 },
26];

js
1start.reduce((obj, it) => {
2  const id = it.questionId._id;
3  if (!obj[id]) return {...obj, [id]: [it]};
4  obj[id].push(it);
5  return obj;
6}, {});
7// {123: Array(3), 456: Array(1)}

これをオブジェクトから配列に戻すのはObject.valuesとして
JSに用意されています。
メソッドじゃないのでちょっと変な事になりますが。

js
1Object.values(start.reduce((obj, it) => {
2  const id = it.questionId._id;
3  if (!obj[id]) return {...obj, [id]: [it]};
4  obj[id].push(it);
5  return obj;
6}, {}));
7// [Array(3), Array(1)]

後はLodashのmapと同じモノをくっつけて完成

js
1Object.values(start.reduce((obj, it) => {
2  const id = it.questionId._id;
3  if (!obj[id]) return {...obj, [id]: [it]};
4  obj[id].push(it);
5  return obj;
6}, {})).map(questions => {
7  const options = questions[0]
8    .questionId
9    .options
10    .reduce((obj, it) => ({...obj, [it]: 0}), {});
11  questions.forEach(({chose}) => options[chose]++);
12  return {
13    questionId: questions[0].questionId._id,
14    ...options
15  }
16})

JSON
1[
2   {
3      "questionId": 123,
4      "javascript": 2,
5      "python": 1,
6      "c": 0,
7      "R": 0
8   },
9   {
10      "questionId": 456,
11      "ramen": 1,
12      "sushi": 0,
13      "teriyaki": 0,
14      "duck": 0
15   }
16]

こんな感じでLodashで使える関数と同じ挙動を
自前で書けるようになるとこういうでかい計算への対策になります。

因みに多少メモリは汚しますが
計算量は同じ配列を2回舐めるだけで実質2n程度です。
まぁまぁな速さはあるのでgroupByで一気に仕分けるやり方を気に入ってます。

質問文のやり方は毎回配列をサーチすることになるので、
問題数/2*nの計算量になる事が想像でき、私がやった回答と比べて遅くなると思います。
計算量を減らすなら一旦オブジェクトを介してObject.values叩いて結果を取り出す方法にするのが良いでしょうね。
そうなると私が一旦やったreduceを使ったなんちゃってgroupByを経由せずにダイレクトにやっつける方法になるでしょう。

私はそこまでする意味があまり感じられませんが、
チャレンジとして試してみても良いかもしれませんね。

投稿2021/06/29 14:03