engineering.otobank.co.jp Open in urlscan Pro
13.230.115.161  Public Scan

Form analysis
1 forms found in the DOM

GET https://engineering.otobank.co.jp/search

<form class="search-form" role="search" action="https://engineering.otobank.co.jp/search" method="get">
  <input type="text" name="q" class="search-module-input" value="" placeholder="記事を検索" required="">
  <input type="submit" value="検索" class="search-module-button">
</form>

Text Content

OTOBANK ENGINEERING BLOG


オトバンクはコンテンツが大好きなエンジニアを募集しています！

2021-08-02


UNIQUEBYから始める低計算量アルゴリズムのすゝめ

ReactNative

こんにちは、アプリ開発担当のエモトです。先日、弊社アプリが大型アップデートされました。我々アプリチーム含め社内メンバーと取り組んで、ダークモードなど新しい機能を追加してリリースすることができました。是非、新しくなったアプリをご利用くださいませ。

さて話は変わり、ある配列に対して、その配列の要素が重複しない配列に気軽に変換にしたい。

const array1 = [1, 1, 2, 2, 3, 3]
const array2 = uniqueBy(array1) // [1, 2, 3]


この問題、何も考えずに実装すると計算量 O(N2)
となり、非常に大きい計算負荷になってしまいます。安易に実装するぐらいなら、サードライブラリを利用するのが良いと思います。

弊アプリは React Native を採用しているので、Swift などのネイティブ実装と比べると計算量はより気になる要因の1つです。アプリでは lodash
の uniqBy を使用していました。ふと気になって、そのソースコード を確認すると while
ループが2つ重なるパターンがあり、良い計算量の設計ではないと気づきました。また lodash の代替候補とも言われる just の just-unique
は計算量は考慮されているが、重複確認は単純比較のみなので、必ずしも代わりになるわけではないとわかりました。これは何かしないといけない。


SET を利用した手法

重複なしを実現したいなら Set を利用するのが簡単ですが、要素の順番が保証されないケースがほとんどです。しかし、TypeScript (JaveScript)
では Set は順序が保証されているとのことで、Set を利用するしかありません。

export const unique = <T>(args: T[]): T[] => [...new Set(args)]


上記だと、要素が Object 型の場合、比較が困難になります。そのため、特定要素を比較する場合も作成しました。

const uniqueBy = <T>(args: T[], key: keyof T): T[] => {
  const valueSet = new Set()
  return args.filter((arg) => {
    const value = arg[key]
    if (valueSet.has(value)) {
      return false
    }
    valueSet.add(value)
    return true
  })
}


検証として 0 から 4 までの数字で構成された 100 万個の要素を持つ配列を用意して、計測しました。

unique uniqueBy 対象配列 [0, 1, 2, ...] [{x: 0}, {x: 1}, {x: 2}, ... ] 計算時間 (msec)
333 21

純粋な Set を利用した unique の方が早いと想像しましたが、予想外にもその unique の方が 10 倍以上の計算時間でした。ソースコードは短いが
Set に変換した後に Array に変換するという処理だから？かもしれませんが、詳しくは分かりませんでした。


自作した UNIQUEBY

検証結果から以下のようなコードを作成しました。

/**
 * 配列から、ユニークな（重複しない）配列を生成する
 *
 * @description
 * keyが未指定の場合、[...new Set(args)] の方が早そうだが、実際は遅かった。
 * なお、jsのSetは順番が保証されている
 */
const _uniqueBy = <T>(args: T[], key?: keyof T): T[] => {
  const valueSet = new Set()
  return args.filter((arg) => {
    const value = key ? arg[key] : arg
    if (valueSet.has(value)) {
      return false
    }
    valueSet.add(value)
    return true
  })
}

/**
 * 単純な配列から、ユニークな（重複しない）配列を生成する
 * - 単純比較できる string[] や number[] など
 */
export const unique = <T>(args: T[]): T[] => _uniqueBy(args)

/**
 * 配列から、その配列内要素の特定keyを基準に、ユニークな（重複しない）配列を生成する
 *
 * @example
 * const uniqueArray = uniqueBy([{x:1}, {x:1}, {x:2}], 'x')
 */
export const uniqueBy = <T>(args: T[], key: keyof T): T[] =>
  _uniqueBy(args, key)



既存ライブラリとの比較

lodash の uniqBy と比較しました。対象データは先ほどと同様な100万個要素の配列を用意しました。

自作/uniqueBy lodash/uniqBy 平均 (msec) 68.9 111.7 標準偏差 (msec) 38.2 13.4 最小 (msec)
24 87 最大 (msec) 141 132

10回ほど検証したところ、多くの場合で、自作の方が早かったです（うれしい）。


まとめ

uniqueBy（重複なし配列への変換）を含め、安易なアルゴリズムでコーディングすると計算量が高くなる処理があります。これらは自作せずに、サードパーティを利用した方が良いと思っています。しかし、それぞれの設計思想や目的があり、自分が使いたいシーンで必ず良い結果や計算量が与えられるとは限らない問題もあります。

今回は対象データや、Set
でうまく処理できたことが重なって、自作の採用にメリットがあり挑戦できました。最適なアルゴリズムを考える時間は、とても楽しい開発でした。

最後に、オトバンクではエンジニアを募集中です。日々高速で低計算量なアルゴリズムを考えるのが好きな方、オーディオブック・React Native 開発（Swift
や Kotlinのネイティブコードも書いてます）にご興味があれば、是非どうぞ。

 * 株式会社オトバンク の採用・求人

お待ちしております。

mitsuharu_e 39日前


uniqueByから始める低計算量アルゴリズムのすゝめ


 * もっと読む

コメントを書く
2021-05-17


図でよくわかる DOCTRINE ORM の基本のキ

Doctrine2 PHP Symfony2 社内LT

こんにちは @kalibora です。

図でよくわかる Doctrine ORM の基本のキ というタイトルで社内LTをしたので、せっかくなので資料を公開しておきます。

EntityManager でよく使うメソッドである persist, flush, clear の挙動を簡単に図解しています。

内容はめっちゃ基本的なものですが、Doctrine 初心者の方には役立つかもしれないのでよろしければどうぞ。

kalibora (id:kalibora) 116日前


図でよくわかる Doctrine ORM の基本のキ


 * もっと読む

コメントを書く
2021-03-26


レイヤー間の依存関係の静的解析 - PHP DEPTRAC ~ 実践編

前回の記事 レイヤー間の依存関係の静的解析 - PHP deptrac ~ 導入編 からの続きです。

「ユニットテストとは事情が違うし、そうそう違反は起きないよ」と思った方がいらっしゃるかも知れません。いえ、レイヤーの依存関係違反は割と発生します。


起こりうる違反例

前回のコードを少し変更して、Userエンティテイにおいて getType() メソッドで属性を取得できるようにしてみましょう。

<?php
namespace Foo\Entity;

class User
{
    public function getType() : string
    {
        // 何かしらのロジック

        return \Foo\Repository\UserRepository::TYPE_ADMIN;
    }
}


<?php
namespace Foo\Repository;
use Foo\Entity\User;

class UserRepository
{
    public const TYPE_ADMIN = 'admin';

    public function findOneById(int $id) : User
    {}
}


Entityまでのレイヤールールを行うと・・・・

paths:
  - ./src
exclude_files:
layers:
  - name: Action
    collectors:
      - type: implements
        implements: Psr\Http\Server\RequestHandlerInterface
  - name: Repository
    collectors:
      - type: className
        regex: Foo\\Repository\\.*Repository
  - name: Entity
    collectors:
      - type: className
        regex: Foo\\Entity\\.*

ruleset:
  Action:
    - Repository
    - Entity
  Repository:
    - Entity


$ deptrac analyse action-repository-entity.yaml
 8/8 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%

 ----------- -------------------------------------------------------------------------------
  Reason      Entity
 ----------- -------------------------------------------------------------------------------
  Violation   Foo\Entity\User must not depend on Foo\Repository\UserRepository (Repository)
              /mnt/d/dev/sandbox-deptrac/src/Entity/User.php:10
 ----------- -------------------------------------------------------------------------------


 -------------------- -----
  Report
 -------------------- -----
  Violations           1
  Skipped violations   0
  Uncovered            6
  Allowed              5
  Warnings             0
  Errors               0
 -------------------- -----

と、Entityは他に参照するレイヤーはあるべきでないのに、UserRepositoryの定数を利用していたことが判明します。
実際のプロジェクトでも数は少なくはありながらも、「サービスクラスの定数を Entityクラス内で用いてしまっていた。」などがありました。


ほかの違反例

さきほどの例では、レイヤー外の定数を挙げましたが、ほかには以下のような違反を発見しました。

 * Entityでのメソッドで、サービスレイヤーとして定義した層の例外クラスの使用
   * これは、定数の例と同様にサービスクラス側に設けた、サービスの例外をエンティテイの例外に利用してしまったというミスです。


現行のエラーをひとまずレポートしないようにする。~ BASELINEの利用

実際に、既存のプロジェクトに対してレイヤールールをある程度行い、analyseを実行してみると上記で述べたような違反が検出されてくることになります。その場合、deptrac
を導入したくても既存の違反分の修正を行わなくては、と思われるかも知れません。ご安心ください。deptracには、phpstanやpsalmのものと同様に既存の違反分を許容するベースラインサポートがあります。


BASELINEの作成

--formatter=baseline でbaselineを作成します。

$ deptrac analyse --formatter=baseline --baseline-dump=baseline.yaml action-repository-entity.yaml
 8/8 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%

Baseline dumped to /mnt/d/dev/sandbox-deptrac/baseline.yaml

以下のような既存の違反に対して skip_violationsが作成されます。

$ cat baseline.yaml
skip_violations:
  Foo\Entity\User:
    - Foo\Repository\UserRepository


BASELINEのインクルード

baseline: 行を追加します。

paths:
  - ./src
exclude_files:

baseline: baseline.yaml


BASELINEを含んだ上での再実行

baselineを含ませて改めて実行してみます。

$ deptrac analyse action-repository-entity.yaml
 8/8 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%


 -------------------- -----
  Report
 -------------------- -----
  Violations           0
  Skipped violations   1
  Uncovered            6
  Allowed              5
  Warnings             0
  Errors               0
 -------------------- -----

Skipped violations の対象となり、exitコードも0です。


GITHUB ACTIONS でのアノテート

CIでの運用の場合、deptracはさらにフォーマッターとしてgithub-actions が用意されています。 弊社では、deptrac analyse
action-repository-entity.yaml --no-progress --formatter=github-actions
といったワークフローを設定しています。 なお、補足として、0.11.1以降ではGithub Actionsのフォーマッターでのスキップ対応
を含めスキップ分のレポートはデフォルトでは除外されるようになり、Github Actionsでのアノテートなどでの導入が行いやすくなりました。


継続的なアーキテクチャの維持・向上に向けて

上述のbaselineのサポートもあり、もし既存のコードに対してアーキテクチャを失敗していた！ということが見つかっても、恐れることなく即レイヤー設定の追加・アップデートが行えるようになりました。自身が担当した改修部分に限らず、コードレビューにおいて見つかった点をフィードバックする形で
deptrac.yaml に追加し継続的にアーキテクチャテストを行っていきたいと思います。

php
deptrac
アーキテクチャテスト

sasezaki 168日前


レイヤー間の依存関係の静的解析 - PHP deptrac ~ 実践編


 * もっと読む

コメントを書く
次のページ

株式会社オトバンク

日本最大級のオーディオブック配信サービス audiobook.jp や、新刊図書・話題の本を紹介する新刊 JP
を運営するオトバンクのエンジニアが発信しています！







読者です 読者をやめる 読者になる 読者になる
17
このブログについて
検索

最新記事
 * 2021-08-02
   uniqueByから始める低計算量アルゴリズムのすゝめ
 * 2021-05-17
   図でよくわかる Doctrine ORM の基本のキ
 * 2021-03-26
   レイヤー間の依存関係の静的解析 - PHP deptrac ~ 実践編

注目記事
 * 2016-09-20
   ログレベルちゃんと使い分けてますか？
 * 2017-05-09
   Symfony2で利用されているDoctrineに入門する(後編)
 * 2015-05-07
   Chrome のデベロッパーツールを別ウィンドウに分離できない、と困った話

OTOBANK OSS
 * monolog-fluent-handler
 * facebook-bundle
 * treasure-php
 * gcputils-php
 * monolog-console-processor

リンク
 * 株式会社オトバンク
 * audiobook.jp
 * 新刊JP
 * GitHub

月別アーカイブ
 * ▼ ▶
   2021 (4)
   * 2021 / 8 (1)
   * 2021 / 5 (1)
   * 2021 / 3 (1)
   * 2021 / 1 (1)
 * ▼ ▶
   2020 (15)
   * 2020 / 11 (3)
   * 2020 / 9 (3)
   * 2020 / 8 (2)
   * 2020 / 6 (1)
   * 2020 / 5 (3)
   * 2020 / 4 (2)
   * 2020 / 1 (1)
 * ▼ ▶
   2019 (13)
   * 2019 / 10 (1)
   * 2019 / 9 (1)
   * 2019 / 8 (2)
   * 2019 / 7 (5)
   * 2019 / 6 (2)
   * 2019 / 4 (1)
   * 2019 / 2 (1)
 * ▼ ▶
   2018 (4)
   * 2018 / 10 (2)
   * 2018 / 9 (1)
   * 2018 / 7 (1)
 * ▼ ▶
   2017 (12)
   * 2017 / 12 (1)
   * 2017 / 10 (1)
   * 2017 / 9 (1)
   * 2017 / 7 (1)
   * 2017 / 6 (1)
   * 2017 / 5 (1)
   * 2017 / 4 (1)
   * 2017 / 3 (1)
   * 2017 / 2 (2)
   * 2017 / 1 (2)
 * ▼ ▶
   2016 (22)
   * 2016 / 12 (4)
   * 2016 / 11 (3)
   * 2016 / 10 (3)
   * 2016 / 9 (2)
   * 2016 / 8 (2)
   * 2016 / 7 (1)
   * 2016 / 6 (2)
   * 2016 / 5 (1)
   * 2016 / 4 (1)
   * 2016 / 3 (1)
   * 2016 / 2 (1)
   * 2016 / 1 (1)
 * ▼ ▶
   2015 (22)
   * 2015 / 12 (2)
   * 2015 / 11 (3)
   * 2015 / 10 (2)
   * 2015 / 9 (1)
   * 2015 / 8 (1)
   * 2015 / 7 (1)
   * 2015 / 6 (1)
   * 2015 / 5 (3)
   * 2015 / 4 (3)
   * 2015 / 3 (1)
   * 2015 / 2 (1)
   * 2015 / 1 (3)
 * ▼ ▶
   2014 (6)
   * 2014 / 11 (2)
   * 2014 / 10 (4)



スターをつけました

引用をストックしました

ストック一覧を見る 閉じる

引用するにはまずログインしてください

ログイン 閉じる

引用をストックできませんでした。再度お試しください

閉じる

限定公開記事のため引用できません。

読者です 読者をやめる 読者になる 読者になる
17