CircleCIでマトリックスビルド

CircleCI

CircleCIでマトリックスビルド

現状CircleCIではマトリックスビルドはサポートされていませんが、実現するための方法がいくつかあります。

matrixキーがサポートされました 👏

Configuring CircleCI - CircleCI

node v8、v10、v12、それぞれの実行環境でライブラリのインストール、テスト、ビルドを行い、すべてに成功した場合のみ、ビルドした成果物をNode v10でデプロイしたいとします。また、テストとビルドは互いに依存しないが、インストールに依存するとします。

それぞれの実行環境ごとに、ジョブを定義する

次のように、実行環境(Nodeバージョン)ごとにジョブを定義することができます。

image

version: 2.1

jobs:
  install_deps:
    docker:
      - image: circleci/node:10
    steps:
      - checkout
      - restore_cache:
          keys:
            - v1-npm-{{ .Branch }}-{{ checksum "package-lock.json" }}
            - v1-npm-{{ .Branch }}-
            - v1-npm-
      - run: npm install
      - save_cache:
          paths:
            - node_modules
          key: v1-npm-{{ .Branch }}-{{ checksum "package-lock.json" }}
      - persist_to_workspace:
          root: ./
          paths:
            - node_modules

  "node-8":
    docker:
      - image: circleci/node:8
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm test
      - run: npm run build

  "node-10":
    docker:
      - image: circleci/node:10
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm test
      - run: npm run build
      - persist_to_workspace: # Node v10でビルドした成果物を永続化
          root: ./
          paths:
            - lib/
            - node_modules

  "node-12":
    docker:
      - image: circleci/node:12
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm test
      - run: npm run build

  deploy:
    docker:
      - image: circleci/node:10
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run deploy

workflows:
  version: 2
  matrix:
    jobs:
      - install_deps
      - "node-8":
          requires:
            - install_deps
      - "node-10":
          requires:
            - install_deps
      - "node-12":
          requires:
            - install_deps
      - deploy:
          requires:
            - "node-8"
            - "node-10"
            - "node-12"

testとbuildが直列に定義されていることが気になるところですが、テストとビルドが依存していないからと言って別ジョブに分けて定義したいという欲がでてくると、node-8-test、node-8-build、node-10-test…をそれぞれ定義しなければならなくなるため、ちょっと厳しくなります。

image

version: 2.1

jobs:

(略)

  "node-8-test":
    docker:
      - image: circleci/node:8
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm test

  "node-8-build":
    docker:
      - image: circleci/node:8
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run build

  "node-10-test":
    docker:
      - image: circleci/node:10
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm test

  "node-10-build":
    docker:
      - image: circleci/node:10
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run build
      - persist_to_workspace:
          root: ./
          paths:
            - lib
            - node_modules

  "node-12-test":
    docker:
      - image: circleci/node:12
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm test

  "node-12-build":
    docker:
      - image: circleci/node:12
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run build

  deploy:
    docker:
      - image: circleci/node:10
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run deploy

workflows:
  version: 2
  matrix:
    jobs:
      - install_deps
      - "node-8-test":
          requires:
            - install_deps
      - "node-8-build":
          requires:
            - install_deps
      - "node-10-test":
          requires:
            - install_deps
      - "node-10-build":
          requires:
            - install_deps
      - "node-12-test":
          requires:
            - install_deps
      - "node-12-build":
          requires:
            - install_deps
      - deploy:
          requires:
            - "node-8-test"
            - "node-8-build"
            - "node-10-test"
            - "node-10-build"
            - "node-12-test"
            - "node-12-build"

この場合、パラメータを使ってジョブコンフィグをまとめることができます。

ジョブパラメータで管理する

パラメータを使えば、テスト・ビルドのジョブは使い回すことができるため、設定ファイルがすっきりします。ただし、これでも手動で値を入れる必要があるため、2軸のマトリックス(言語バージョン×OSなど)はうまく管理できる気がしません。

version: 2.1

executor-template: &executor-template
  parameters:
    tag:
      default: "10"
      type: string
    persist_built_files:
      type: boolean
      default: false
  docker:
    - image: circleci/node:<< parameters.tag >>

jobs:
  install_deps:
    <<: *executor-template
    steps:
      - checkout
      - restore_cache:
          keys:
            - v1-npm-{{ .Branch }}-{{ checksum "package-lock.json" }}
            - v1-npm-{{ .Branch }}-
            - v1-npm-
      - run: npm install
      - save_cache:
          paths:
            - node_modules
          key: v1-npm-{{ .Branch }}-{{ checksum "package-lock.json" }}
      - persist_to_workspace:
          root: ./
          paths:
            - node_modules

  test:
    <<: *executor-template
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run test

  build:
    <<: *executor-template
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run build
      - when:
          condition: << parameters.persist_built_files >>
          steps:
            - persist_to_workspace:
                root: ./
                paths:
                  - node_modules
                  - lib

  deploy:
    <<: *executor-template
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run deploy

workflows:
  version: 2
  matrix:
    jobs:
      - install_deps

      - test:
          name: node-8-test
          tag: "8"
          requires:
            - install_deps

      - test:
          name: node-10-test
          tag: "10"
          requires:
            - install_deps

      - test:
          name: node-12-test
          tag: "12"
          requires:
            - install_deps

      - build:
          name: node-8-build
          tag: "8"
          requires:
            - install_deps

      - build:
          name: node-10-build
          tag: "10"
          persist_built_files: true
          requires:
            - install_deps

      - build:
          name: node-12-build
          tag: "12"
          requires:
            - install_deps

      - deploy:
          tag: "10"
          requires:
            - node-8-test
            - node-8-build
            - node-10-test
            - node-10-build
            - node-12-test
            - node-12-build

パイプラインパラメータで管理する

少しトリッキーですが、パイプラインパラメータを使えば、ワークフロー全体にパラメータを渡すことができるため、より少ない記述量で実現できます。この設定ファイルを使用するには、APIトークン(CIRCLE_TOKEN)が必要です。

(パラメータを使った動的なジョブ名は前からできたっけ？)

parameters:
  tag:
    default: '10'
    type: string
  run-main-workflow:
    default: false
    type: boolean
  run-deploy-job:
    default: false
    type: boolean

executors:
  node:
    docker:
      - image: circleci/node:<< pipeline.parameters.tag >>

version: 2.1
jobs:
  install_deps:
    executor: node
    steps:
      - checkout
      - restore_cache:
          keys:
            - v1-npm-{{ .Branch }}-{{ checksum "package-lock.json" }}
            - v1-npm-{{ .Branch }}-
            - v1-npm-
      - run: npm install
      - save_cache:
          paths:
            - node_modules
          key: v1-npm-{{ .Branch }}-{{ checksum "package-lock.json" }}
      - persist_to_workspace:
          root: ./
          paths:
            - node_modules

  test:
    executor: node
    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run test

  build:
    executor: node

    steps:
      - checkout
      - attach_workspace:
          at: ./
      - run: npm run build

      - when:
          condition: << pipeline.parameters.run-deploy-job >>
          steps:
            - persist_to_workspace:
                root: ./
                paths:
                  - lib
                  - node_modules

  deploy:
    docker:
      - image: circleci/node:<< pipeline.parameters.tag >>
    steps:
      - when:
          condition: << pipeline.parameters.run-deploy-job >>
          steps:
            - checkout
            - attach_workspace:
                at: ./
            - run: npm run deploy
      - unless:
          condition: << pipeline.parameters.run-deploy-job >>
          steps:
            - run: echo "No deployment on Node v<< pipeline.parameters.tag >>"

  trigger-main-workflows:
    machine:
      image: ubuntu-1604:201903-01
    parameters:
      deploy-node-version:
        default: '10'
        type: string
    steps:
      - run:
          name: Trigger main worflow
          command: |
            VCS_TYPE=$(echo ${CIRCLE_BUILD_URL} | cut -d '/' -f 4)

            for NODE_VERSION in 8 10 12
            do
                PIIPELINE_PARAM_MAP="{\"run-main-workflow\": true, \"tag\":\"$NODE_VERSION\"}"
                if [ "$NODE_VERSION" = << parameters.deploy-node-version >> ]
                then
                    PIIPELINE_PARAM_MAP="{\"run-main-workflow\": true, \"tag\":\"$NODE_VERSION\", \"run-deploy-job\": true}"
                fi

                curl -u ${CIRCLE_TOKEN}: -X POST --header "Content-Type: application/json" -d "{
                  \"branch\": \"${CIRCLE_BRANCH}\",
                  \"parameters\": ${PIIPELINE_PARAM_MAP}
                }" "https://circleci.com/api/v2/project/${VCS_TYPE}/${CIRCLE_PROJECT_USERNAME}/${CIRCLE_PROJECT_REPONAME}/pipeline"
            done

workflows:
  version: 2
  matrix:
    unless: << pipeline.parameters.run-main-workflow >>
    jobs:
      - trigger-main-workflows:
          deploy-node-version: "10"

  main:
    when: << pipeline.parameters.run-main-workflow >>
    jobs:
      - build:
          name: build-<< pipeline.parameters.tag >>
      - test:
          name: test-<< pipeline.parameters.tag >>
      - deploy:
          requires:
            - build-<< pipeline.parameters.tag >>
            - test-<< pipeline.parameters.tag >>

trigger-jobsワークフローが、Node v8, v10, v12の実行環境において、それぞれmainワークフローをトリガーします。

Nodeバージョン×DBといったマトリックスも可能です。

全文

(略)
  trigger-main-workflows:
    machine:
      image: ubuntu-1604:201903-01
    parameters:
    steps:
      - run:
          name: Trigger main worflow
          command: |
            VCS_TYPE=$(echo ${CIRCLE_BUILD_URL} | cut -d '/' -f 4)

            for NODE_VERSION in 8 10 12
            do
                for DB in mongo mysql
                do
                    PIIPELINE_PARAM_MAP="{\"run-main-workflow\": true, \"tag\":\"$NODE_VERSION\", \"db\":\"$DB\"}"
                    if [ "$NODE_VERSION" = "10" ] && [ "$DB" = "mongo" ]
                    then
                        PIIPELINE_PARAM_MAP="{\"run-main-workflow\": true, \"tag\":\"$NODE_VERSION\", \"db\":\"mongo\", \"run-deploy-job\": true}"
                    fi
                    curl -u ${CIRCLE_TOKEN}: -X POST --header "Content-Type: application/json" -d "{
                      \"branch\": \"${CIRCLE_BRANCH}\",
                      \"parameters\": ${PIIPELINE_PARAM_MAP}
                    }" "https://circleci.com/api/v2/project/${VCS_TYPE}/${CIRCLE_PROJECT_USERNAME}/${CIRCLE_PROJECT_REPONAME}/pipeline"
                done
            done

ただし、APIを叩く必要があるため、これでもまだ他のCIでできるようなマトリックスビルドと比べれば、やぼったさは否めません。また、デプロイジョブをすべてのワークフローが成功した場合のみ実行するしくみ(ファンイン)にすることが非常に難しく、APIを使ってビルド結果をポーリングするか、承認ジョブを使って目視で確認してから手動で起動にするしかなさそうです。

(ファンアウト・ファンインについて)

RFC: Matrix Jobs syntaxを見ると、マトリックスビルドの開発が今まさに行われているようなので、正式サポートされるまではファンアウトだけなら上記のパイプラインパラメータ、ファンインが必要ならジョブパラメータが良さそうかな。

CircleCIからnpm packageを公開するためのOrb

circleci

作りました。よろしくお願いします。

Orb Registry: npm-publisher

GitHub Repo: npm-publisher

使用例

使い方

NPMトークンを取得し、環境変数NPM_TOKENとしてセット。package.jsonの情報に従ってパッケージを公開します。

モジュールのダウンロードやビルドはpre-publish-stepsパラメータを使用します。

orbs:
  npm-publisher: uraway/npm-publisher@x.y.z

version: 2.1
workflows:
  build_publish:
    jobs:
      - npm-publisher/publish-from-package-version:
          publish-token-variable: NPM_TOKEN
          push-git-tag: true
          fingerprints: <fingerprints>
          pre-publish-steps:
            - restore_cache:
                keys:
                  - v1-node-cache-{{ .Branch }}-{{ checksum "package-lock.json" }}
                  - v1-node-cache-{{ .Branch }}
                  - v1-node-cache-
            - run: npm install
            - run: npm build
          post-publish-steps:
            - save_cache:
                key: v1-node-cache-{{ .Branch }}-{{ checksum "package-lock.json" }}
                paths:
                  - node_modules
          filters:
            branches:
              only: master

また、push-git-tagオプションを有効にしてフィンガープリントをセットすればタグをコミットします。

配列の積和演算のアルゴリズム

algorithm

配列の積和演算のアルゴリズム

「特別な配列」が与えられるので積和演算を行って値を返す。「特別な配列」は数値あるいは「特別な配列」をもつ。「特別な配列」内の数値をすべて加算するが、ネストレベルに応じてその和を乗算する。 例えば、

[x, y] → x + y
[x, [y, z]] → x + 2(y + z)
[1, [2, [3, 4]]] → 1 + 2 * (2 + 3 * (3 + 4)) → 47

アルゴリズム実装(1) $O(n)$

再帰関数を別途作るのが楽。見たまんまで、配列ならdepthに1を加えて再帰関数を実行し、数値なら加算する。

function productSum(array) {
    return productSumHelper(array, 1)
}

function productSumHelper(array, depth) {
    let result = 0
    for (const ele of array) {
        if (Array.isArray(ele)) {
            result += productSumHelper(ele, depth + 1)
        } else {
            result += ele
        }
    }
    return result * depth
}

要素数n回実行されるので、計算量は$O(n)$

二分探索木(binary search tree)から近似値を求める

algorithm

二分探索木(binary search tree)から近似値を求める

二分探索木のデータとtargetが与えられる。二分探索木のデータの中からtargetの近似値を求める。

例えば次のような二分探索木のデータとtarget 5が与えられるとき、答えは6である。

        8
        /\
       3  10
      /\   \
     1 6   14
       /\   /
      4  7 13

ref: https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8

二分探索木の定義

二分探索木のデータ構造は「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。与えられた値の近似値を求めるには、一時的にそれまで見つかった近似値を保持しておいて、次の子ノード、孫ノード、…と子ノードが存在しなくなるまで探索を続ける必要があるため、計算量はどのアルゴリズムでも最低O(n)となるはず。

子ノードが存在しないときに保持していた近似値が解となる。

与えられる引数

引数はtreeとtargetが与えられる。

treeオブジェクトは数値value、treeオブジェクトleft、treeオブジェクトrightのプロパティを持つ再帰的なオブジェクト。targetは数値。

アルゴリズム実装(1) O(n)

ノードが存在しないとき、treeオブジェクトはnullをとる。近似値を保持しておいて、tree === nullとなるまでループを続ける。二分探索木の定義から、leftプロパティのvalueは必ず現在のノードのvalueより小さく、rightプロパティのvalueは必ず現在のノードのvalueより大きい。

function findClosestValueInBst(tree, target) {
    return traverseNode(tree, target, null);
}

function traverseNode(node, target, closest) {
    while (node !== null) {
        if (closest === null || Math.abs(target - closest) > Math.abs(target - node.value)) {
            closest = node.value
        }
        if (target < node.value) {
            node = node.left
        } else if (target > node.value) {
            node = node.right
        } else {
            break
        }
    }
    
    return closest
}

アルゴリズム実装(2) O(n)

メモリ的には優しくないかもしれないが、再帰関数のほうが理解しやすいかも？

function findClosestValueInBst(tree, target) {
    return traverseNode(tree, target, null);
}

function traverseNode(node, target, closest) {
    if (node === null) {
        return closest
    }
    if (closest === null || Math.abs(target - closest) > Math.abs(target - node.value)) {
        closest = node.value
    }
    if (target < node.value) {
        return traverseNode(node.left, target, closest)
    } else if (target > node.value) {
        return traverseNode(node.right, target, closest)
    }
    
    return closest
}

VS Code Extensionの公開を簡単にするCircleCI Orb作りました

CircleCI

VS Code Extensionの公開を簡単にするCircleCI Orb作りました

作りました: https://circleci.com/orbs/registry/orb/uraway/vsce

リポジトリ: https://github.com/uraway/vsce

使い方

環境変数としてVSCODE_MARKETPLACE_TOKENにPersonal Access Tokenをセットして、package.jsonのバージョンフィールドを更新してコミットすればあとは自動的に公開されます。

push-git-tagオプションをtrueにしてフィンガープリントもつければ、タグリリースやってくれるのでかんぺき。キャッシュの処理はキャッシュキーがややこしくなりそうなので、post-install-stepsとpre-install-stepsでユーザー定義にしました。

orbs:
  vsce: uraway/vsce@0.0.3
version: 2.1
workflows:
  test-publish:
    jobs:
      - vsce/publish:
          filters:
            branches:
              only: master
          post-install-steps:
            - save_cache:
                key: v1-node-cache-{{ .Branch }}-{{ checksum "package-lock.json" }}
                paths:
                  - node_modules
          pre-install-steps:
            - restore_cache:
                keys:
                  - v1-node-cache-{{ .Branch }}-{{ checksum "package-lock.json"}}
                  - v1-node-cache-{{ .Branch }}
                  - v1-node-cache-
          push-git-tag: true
          ssh-fingerprints: <フィンガープリント>

Orb開発

orbs:
  orb-tools: circleci/orb-tools@9.0.0
  your-orb: your-namespace/your-orb@<<pipeline.parameters.dev-orb-version>>

parameters:
  dev-orb-version:
    default: 'dev:alpha'
    type: string
  run-integration-tests:
    default: false
    type: boolean

jobs:
  integration-tests:
    executor: orb-tools/ubuntu
    steps:
      - checkout

version: 2.1
workflows:
  integration-tests_prod-release:
    jobs:
      - integration-tests
      - orb-tools/dev-promote-prod-from-commit-subject:
          add-pr-comment: true
          bot-user: your-namespace
          fail-if-semver-not-indicated: true
          publish-version-tag: true
          ssh-fingerprints: <フィンガープリント>
          filters:
            branches:
              only: master
          orb-name: your-namespace/your-orb
          requires:
            - integration-tests
    when: << pipeline.parameters.run-integration-tests >>
  lint_pack-validate_publish-dev:
    jobs:
      - orb-tools/lint
      - orb-tools/pack:
          requires:
            - orb-tools/lint
      - orb-tools/publish-dev:
          orb-name: your-namespace/your-orb
          requires:
            - orb-tools/pack
      - orb-tools/trigger-integration-tests-workflow:
          name: trigger-integration-dev
          requires:
            - orb-tools/publish-dev
    unless: << pipeline.parameters.run-integration-tests >>

orb-toolsをフルに使う

https://circleci.com/orbs/registry/orb/circleci/orb-tools

orb-tools、これはもうOrb開発に必須。だいたいこれで良い。v9.0.0になってまた使いやすくなりました。orb-tools/lint、orb-tools/pack、orb-tools/publish-devはもちろん便利ですが、orb-tools/dev-promote-prod-from-commit-subjectジョブがまた良い仕事してくれる。

      - orb-tools/dev-promote-prod-from-commit-subject:
          add-pr-comment: true
          bot-user: your-namespace
          fail-if-semver-not-indicated: true
          publish-version-tag: true
          ssh-fingerprints: <フィンガープリント>
          filters:
            branches:
              only: master
          orb-name: your-namespace/your-orb

プルリクエストをマージするときに、下記図のようにコミットサブジェクトに[semver:patch|minor|major|skip]を入れるとsemverにそってプロモートしてくれます。

また、add-pr-comment: trueを渡して、環境変数PR_COMMENTER_GITHUB_TOKENとしてbot-userに対応するGitHubトークンをプロジェクトに追加すれば、そのプルリクエストに、Orb公開したよ、とコメントしてくれます。

さらに、publish-version-tag: trueを渡して、デプロイキーのフィンガープリントをセットすればタグコミットをプッシュしてくれます。さいこう

必要であればインテグレーションテスト

Orbによっては必要なこともあるインテグレーションテスト。vsce Orbでは、外部APIであるVS Code Marketplaceとの連携をテストしたいので、リポジトリ内にテスト用のVS Code Extension (vsce-orb-integration-test)を持ち、そのExtensionの公開・非公開をワークフロー内で繰り返しています。API制限とかあるのかな？

https://github.com/uraway/vsce

workflows:
  integration-tests_prod-release:
    jobs:
      - vsce/publish:
          name: publish-vsce
          publish-token-variable: VSCODE_MARKETPLACE_TOKEN
          push-git-tag: false
          package-path: vsce-orb-integration-test
          pre-install-steps:
            - restore_cache:
                keys:
                  - v1-node-cache-{{ .Branch }}-{{ checksum "vsce-orb-integration-test/package-lock.json" }}
                  - v1-node-cache-{{ .Branch }}
                  - v1-node-cache-
          post-install-steps:
            - save_cache:
                key: v1-node-cache-{{ .Branch }}-{{ checksum "vsce-orb-integration-test/package-lock.json" }}
                paths:
                  - node_modules
      - vsce/unpublish:
          name: unpublish-vsce
          publish-token-variable: VSCODE_MARKETPLACE_TOKEN
          package-path: vsce-orb-integration-test
          requires:
            - publish-vsce

2つの数の和

algorithm

2つの数の和

2つ以上のユニークな数字の集合Aの中から、ターゲット(target)の数字の和となる数字のペアを見つけ出す。数字のペアは最大1つある。答えは値が小さい順に並べるとする。

例えばAが1, 10, 5, -1、12、targetが15であれば、答えは10, 5のペアである。Aを数字の配列の引数、targetを数字の引数としてこれを実装する。

アルゴリズム実装(1) O(n2)

最も簡単なアルゴリズムは二重ループして、すべての要素の和のパターンを出すこと。計算量はO(n^2)。使用しているsortは2つの数値の比較なので無視する。

function twoNumberSum(A, target) {    
    for (let i = 0; i < A.length; i++) {
            for (let j = 0; j < A.length; j++) {
                if (i === j) continue;
                if (A[i] + A[j] === target){
                    return [A[i], A[j]].sort((a, b) => a - b)
                }
            }
        }

        return [];
}

アルゴリズム実装(2) O(n)

計算し終えた要素を配列storeに保存していき、ワンループで済ます。計算量はO(n)

ループ中の数値をxとすると、ペアになる可能性のある数値yはtarget - xと表せる。storeにyが存在しなければ、xをstoreに保存する。

こちらも使用しているsortは2つの数値の比較なので無視する。

function twoNumberSum(A, target) {    
        const store = []

        for (const x of A) {
            const y = target - x
            if (store.includes(y)) {
                return [x, y].sort((a, b) => a - b)
            } else {
                store.push(x)
            }
        }

        return [];
}

includesの実装が気になる。ハッシュテーブルに保存のほうがいいかも？

アルゴリズム実装(3) O(n log n)

まず、Aを小さい順に並び替える。ソートに関しては、JavaScriptの実装はブラウザにもよるがここではクイックソート、計算量O(n log n)とする。

[-1, 1, 5, 10, 12]

現在の最小の値のインデックスをmin、最大の値のインデックスをmaxとおくと

sum = array[left] + array[right]

となる。sumがtargetより大きい場合、値を小さくしたいのでrightを小さくする。逆にsumがtargetより小さい場合、値を大きくしたいので、leftを小さくする。

例えば初期状態でleft=0、right=4であるためsum=11

left          right
  |             |
[-1, 1, 5, 10, 12]

targetはそれより大きいのでleftを右に動かしてleft=1、right=4ならばsum=13

    left      right
     |          |
[-1, 1, 5, 10, 12]

targetはそれより大きいのでleftを右に動かしてleft=2、right=4ならばsum=17

       left   right
        |       |
[-1, 1, 5, 10, 12]

targetはそれより小さいのでrightを左に動かしてleft=2、right=3ならばsum=15

      left right
        |   |
[-1, 1, 5, 10, 12]

クイックソートと一回のループの計算量は

O(n log n) + O(n) = O (n log n)

であることからO(n log n)

答えのペアはユニークな数値となることに注意してこれを実装すると

function twoNumberSum(A, target) {    
    A.sort((a, b) => a - b)
    let left = 0
    let right = A.length - 1
    while (left < right) {
        const sum = A[left] + A[right]
        if (sum === target) {
            return [A[left], A[right]]
        } else if (sum < target) {
            left++
        } else if (sum > target) {
            right--
        }
    }
    return [];
}

バイナリサーチ

algorithm

バイナリサーチ

問: ソートされた数値の配列と数値targetを受け取り、配列中のtargetのインデックスを求める。その際、バイナリサーチを用いること。

アルゴリズム実装 $O(\log n)$

配列の要素数をnとしたとき、left=0、right=nの変数を作る。また、leftとrightの中央の位置をmidとする。

  1. array[mid] === targetならtargetが見つかったとして探索終了。left >= rightなら見つからなかったとして探索終了。
  2. array[mid] > targetならtargetは配列の左半分にあるので、right=mid-1として0へ
  3. array[mid] < targetならtargetは配列の右半分にあるので、left=mid+1として0へ
function binarySearch(array, target) {
    let left = 0
    let right = array.length - 1

    while (left <= right) {
        const mid = Math.floor((left + right) / 2)
        if (array[mid] > target) {
            right = mid - 1
        } else if (array[mid] < target) {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

バイナリサーチは一回実行するごとに対象の配列の要素数が1/2になる。最悪の場合要素数が1になるまで実行されるので、計算量はその繰り返し回数をkとすると

{\displaystyle
\begin{aligned}
1 &= n(\frac{1}{2}) ^k \\\
n &= 2^k \\
k &= \log_2 n 
\end{aligned}
}

底数を無視して、$O(\log n)$となる