Distinct

今回から、ちゃんと reading material を読みます。

## reading material
概要だけ記します。
ソートとは、数字やアルファベットの順にある組を並べることです。
色々なやり方があり、計算量やメモリの使用量に差異があります。
例として、選択ソート、分布数え上げソート、マージソートが挙げられており、Python では組み込みの
sort 関数があることを付記しています。

## [1st][a]
これは PHP の組み込み関数をフル活用しとるから、卑怯かもしれん。
（アイデア勝負ではない点で。アルゴリズムを考えるべき。）

<table>
    <tr><th>Correctness</th><th>Performance</th><th>Task Score</th></tr>
    <tr>
        <td>100%</td>
        <td>100%</td>
        <td>100%</td>
    </tr>
</table>

```php:Distinct-1.php
function solution($A) {
    $unique = array_unique($A);
    $aligned = array_values($unique);
    return count($aligned);
}
```

組み込み関数を使うと、最適化された計算量になることは見込まれるけど、内部の処理に思いを馳せられ
んから、やっぱ自分で実装しよう。

## [2nd][b]

<table>
    <tr><th>Correctness</th><th>Performance</th><th>Task Score</th></tr>
    <tr>
        <td>33%</td>
        <td>0%</td>
        <td>25%</td>
    </tr>
</table>

```php:Distinct-2.php
function solution($A) {
    $count = 0;
    $array = array_fill(0, count($A), 0);

    // 配列の要素に該当する場所に１をセットする
    foreach($A as $value) {
        if(! $array[$value]) {
            $array[$value] = 1;
        }
    }
    // １がセットされている箇所を数える
    foreach($array as $value) {
        if($array[$value]) {
            $count++;
        }
    }

    return $count;

}
```

```php:TestDistinct-2.php
include 'Distinct-2.php';

class DistinctTest extends \PHPUnit\Framework\TestCase {

    public function testDistinct() {
        $array = array(2, 1, 1, 2, 3, 1);
        $ans = solution($array); $this->assertEquals(3, $ans);

        $array = array(1, 1, 5, 2, 3, 4);
        $ans = solution($array); $this->assertEquals(5, $ans);
    }

}
```

所詮実力はこんなもんやった。問題をよく読んでいないことが露呈した。なんせ、前提として、

> each element of array A is an integer within the range [−1,000,000..1,000,000].

やから。つまり、負の数を考慮出来てない。どうやらこのマッピング手法ではダメか？
というわけで、最初の解答で終わりにし、お手本を見るとする。

## [お手本１][c]
なんと、兼ねてよりお世話になっていた jimii さんは、Lesson 6 以上を Github にあげていない！
よって、まずは miina さんをお手本とする。

miina さんの提出した（らしき）コードは、`return count(array_unique($A));` 。
ま、やっぱりこれよな。

ただし、コメントで、その他に３通りの解き方を書いてくれとる。
つまり、以下の４つの解き方が書いてある。

1. `return count(array_unique($A));`
1. `return count(array_count_values($A));`
1. `return count(array_flip($A));`
1. マッピング手法（後述）

`array_count_values` は、要素ごとの出現回数を数えるから、返り値の配列は重複が無くなっている。
`array_flip` は、副作用を利用した解法。この関数は、キーと値の反転時に、重複を消す副作用がある。
そして、マッピング手法は、以下に自分で解いたコードを記すため、これで理解して欲しい。

## [マッピング手法による解答][d]

<table>
    <tr><th>Correctness</th><th>Performance</th><th>Task Score</th></tr>
    <tr>
        <td>100%</td>
        <td>100%</td>
        <td>100%</td>
    </tr>
</table>

```php:Distinct-3.php
function solution($A) {
    $array = array();
    
    foreach($A as $value) {
        if(! isset($array[$value])) {
            $array[$value] = 1;
        }
    }
    
    return count($array);
}
```

`count` を使わず `for` で数え上げてもいいが、与えられた配列の要素をキーとして、キーが存在
しなければ、それをキーとして１を値に持つ要素を配列に追加し、存在すれば何もしない。
ループ終了後は、`$array`の `count` が the number of distinct values になる。

miina さん、参考になりました。ありがとう。

ところで、この問題が **sorting** のジャンルなのは何故だろうか。

<!-- 以下、参考 URL -->
[a]: https://app.codility.com/demo/results/training4F6CER-3F2/
[b]: https://app.codility.com/demo/results/trainingSAFT5X-2AQ/
[c]: https://github.com/miina/codility-php/blob/master/Distinct.php
[d]: https://app.codility.com/demo/results/training8TXXKD-EYR/