アルゴリズム & データ構造勉強会

こんにちは、技術チームの孫です。猛暑が続いていますが、趙さん主催の「データ構造＆アルゴリズム」勉強会を開催しました！例を挙げながら、データ構造とアルゴリズムについて説明します。内容を抜粋して技術ブログに載せさせていただきます。

データ構造とは?
データの集まりの形式化された構成です。
アルゴリズムとは?
「手順や計算方法」のことです。

理解を容易にするために、「料理」を例とすると、
データ構造は具材で、アルゴリズムはレシピです。

まず、データ構造に対して、次の課題を一緒に見てみましょう。
リアルタイムに単価が高い順で10%のデータ抽出するのは、どうすれば良いでしょうか？
SQLのorder byはIOPSが高くなります。一方、PHPのsortも遅いです。

heap(ヒープ)を使うと、このような悩みが簡単に解決できます。

データ構造を改善することの良さが実感できます。

そして、アルゴリズムに対して、DFAの例を挙げて説明しました。

DFAを使ってNGワードを高速に発見する


<?php
$waitForCheck = '13asa碳df充电宝ガニjhui你是谁高麗人参你好吗美味しい猪自販機，啊时间地方是就会230998uasdfauems款了。';
$tree = [];

$ngWords = check($waitForCheck, $ngWordList);
var_dump($ngWords);


function genNgWordComponentTree(array $ngWordList): array  {
    foreach($ngWordList as $words) {
        $hashMap = &$tree;
        $len = mb_strlen($words);

        for ($i = 0; $i < $len; $i++) {
            $word = mb_substr($words, $i, 1);
            if ($i + 1 == $len) {
                $hashMap[$word]['end'] = true;
            }

            $hashMap = &$hashMap[$word] ?? $hashMap = false;
        }
    }

    return $tree;
}

function check(string $string, array $ngWordList): array {
    $txtLength = mb_strlen($string);
    $wordList = [];
    $ngWordsTree = genNgWordComponentTree($ngWordList);

    for ($i = 0; $i < $txtLength; $i++) { $lenList = checkFromTree($string, $i, $txtLength, $ngWordsTree); foreach ($lenList as $key => $len) {
            if ($len > 0) {
                $wordList[] = mb_substr($string, $i, $len);
            }
        }
    }
    return array_flip(array_flip($wordList));
}

function checkFromTree(string $txt, int $index, int $txtLength, array $ngWordsTree): array {
    $wordLength = 0;
    $flag = false;
    $wordLengthArray = [];

    for ($i = $index; $i < $txtLength; $i++) {
        $txtWord = mb_substr($txt, $i, 1);

        if (!isset($ngWordsTree[$txtWord])) {
            break;
        }
        $wordLength++;

        if (isset($ngWordsTree[$txtWord]['end'])) {
            $flag = true;
            $wordLengthArray[] = $wordLength;
        }
        $ngWordsTree = &$ngWordsTree[$txtWord];
    }

    $flag ?: $wordLength = 0;
    return $wordLengthArray;
}

上記のアルゴリズムロジック、早い速度で「你是谁」と「你好吗」を見つけることができます。

所感

アルゴリズムって、すこく難しいイメージがありますね。アルゴリズムは何かの問題を解決するための手順や計算方法を意味します。決まった手順をコンピューターに理解させるように記述したものです。色んな方法の中でも、もっとも効率よく処理を行うためにはアルゴリズムが必要です。プログラミングスキルを向上させるためにも、アルゴリズムを学ぶ意義もあるのですね。