概要

この記事は2本立てです。

Qiita:Team上でのコード実行速度の最適化バトルの実例
Qiita:Teamを盛り上げるためのごく小規模な傾向分析

Qiita:Team上でのコード実行速度の最適化バトルの実例

すごく単純ですが、こんな問題があります。

A zero-indexed array A consisting of N different integers is given. 
The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

function solution(A);
that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

要するに1以上の整数が連続している配列Aの中で、欠如している要素を答えなさいっていう問題です（この例では4が正解になります）。下記を読み進める前に、自分ならどう実装するかを考えてみる事をお勧めします。下記の一番最適な方法やそれ以上の方法を思いつかれた方は、こちらへどうぞ。

力任せの方法

function solution(A) {
    const num = A.length;
    if(num === 0) {
        return 1;
    }
    for(let i = 0; i < num; i++) {
        if(A.indexOf(i + 1) < 0) {
            return i + 1;
        }
    }
    return A[num - 1];
}

この方法だと、概ね配列長の２乗に比例する計算時間がかかりますので、大規模だと実用的ではないです。

ソートで高速化する手法

function solution(A) {
    const num = A.length;
    if(num === 0) {
        return 1;
    }
    A.sort((prev, next) => {
        if(prev < next) return -1;
        else if(prev > next) return 1;
        return 0;
    });
    for(let i = 0; i < num; i++) {
        if(A[i] !== i + 1) {
            return i + 1;
        }    
    }
    return A[num - 1] + 1;
}

だいぶ早くなりますが、ソートの時点で配列長をNとするとNlogNに比例する
時間が掛かります。ここまでを投稿者が社内Qiita:Team記事にしたところ、次々と高速化のネタが上がりました。

フラグ配列による高速化

同じ長さのboolean配列を用意して１パスで存否チェック、２パス目で最小の欠けている数の取得で、配列長に比例する計算時間。

合計値による高速化

配列の合計と欠けのない合計であるN(N+1)/2の差を返す事で、前の手法の半分の計算時間かつ追加の配列記憶も不要。

ビット演算による黒魔術

(1) 配列全体のXORを取る
(2) n = 配列要素数+1
(3) nを4で割った余り(下位3bit)が
　0のとき：　解は(1)にnをXORしたもの
　1のとき：　解は(1)に1をXORしたもの
　2のとき：　解は(1)に1をXORし、さらにnをXORしたもの
　3のとき：　解は(1)

例 (n=7; 余りが3のとき)
漏れのない[1,2,3,4,5,6,7]はXORすると「0」ですので、
設問のように１つの要素が抜けていれば、XOR結果は解になります。

この方法だと、加算によるオーバーフローの心配が無く、かつXORが加算より早い処理系もあるので速度面でも有利な場合があります。

Qiita:Teamを盛り上げるためのごく小規模な傾向分析

前章の様に、コメントで気軽に議論やグループハックができるのがQiita:Teamのいいところです。どの様な要因で、この様な盛り上がりにつながるのか、ごく小規模に分析してみました。社内のある１週間を切り取っただけで、もう少し事例を増やさないと明確な事は言えないですが、参考程度にどうぞ。

まずは、コメント数のヒストグラムから

ランダムにコメントが付くなら、単峰性のポアソン分布になるはずですが、そうはなっていません。ものすごく強引に見ると、コメント0件を除けば、２～４あたりのコメント数をピークとするポアソン分布に見えなくも無いので、

最初のコメントが付くかどうかで壁がある
その後はコメントが付きやすくなり、ランダムにコメントされる

という傾向が示唆されます。この最初のコメントの壁は、記事自体なのか、コメントが付くという社会的評価によるものなのか不明ですが、もし後者ならサクラコメントが効く可能性があります。

次に、投稿が非常に多い日（飽和日）と投稿が少ない日（非飽和日）と社会的評価の比較を行います。

飽和日だと、閲覧が追いつかず、社会的評価も低くなるかと思われたのですが、これを見る限り、関係なさそうです。むしろ、いいね数に限ってはやや多いかもしれません。この原因としては、

投稿が集中すると、自分の投稿への反応を見るついでに反応するというコミュニティ活性化効果がある
みんな閲覧効率がよく、一日数十件程度の記事は読みこなせる
みんな仕事が嫌で、Qiita:Team記事を心待ちにしている

などの可能性があり、今後の分析が待たれます。