エムスリーテックブログ

エムスリー(m3)のエンジニア・開発メンバーによる技術ブログです

Go1.19に採用されたPattern-defeating Quicksortの紹介

Go

エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(po3rin) です。検索とGoが好きです。

最近、Go1.19でsortパッケージのアルゴリズムが一部変更されました。

Pattern-defeating Quicksortが入った時のdiff

1.19リリースノートではPattern-defeating Quicksortが採用されたと紹介があります。実際にsort/zsortfunc.go、sort/zsortinterface.goにそれぞれpdqsort_func、pdqsortという関数があります。

// pdqsort sorts data[a:b].
// The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
// C++ implementation: https://github.com/orlp/pdqsort
// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
func pdqsort(data Interface, a, b, limit int)

今回はPattern-defeating Quicksortがどのようなアルゴリズムなのかを論文*1を読んで、実際にGoでどのように使われているかを調べてみました。

この記事ではPattern-defeating Quicksortのざっくりとした理解を目的とし、証明など細かい話はスキップしてなんとなく何をやってるのかの理解を目指します。

Pattern-defeating Quicksortはクイックソートが苦手な同じ値を持つシーケンスに対して効力を発揮します。実用では大量の被りがある値のソートがほとんど(カテゴリでソートするとか)なので、実用面でも非常に有用なアルゴリズムです。

この論文の貢献として、k個の異なる要素を持つ入力に対してO(nk)の最悪ケースに収まる3 方向比較手法を提案しており非常に面白いです。

論文はこちらです。

arxiv.org

*1:arxiv.org

続きを読む

論理レプリケーションを使ったAurora PostgreSQLのメジャーバージョンアップ

こんにちは、エムスリー 製薬企業向けプラットフォームチームでチームSREをやっている後藤です。

先日、担当しているサービスにてAmazon Aurora PostgreSQL を10から13にメジャーバージョンアップしました。
チームとして初めて論理レプリケーションを使ったバージョンアップを実施したので、その手順をご紹介しようと思います。

続きを読む

アーキテクチャと設計は全然違う⋯ただしあなたの想像する”違い”とは多分全然違う【輪読会発表紹介】

エムスリーエンジニアリンググループ製薬企業向けプラットフォームチームの三浦 (@yuba)です。エンジニアリンググループ内では技術書の輪読会が有志によりいくつか立ち上がっています*1。そうした勉強会の一つで発表した内容が社内で少々バズったので、これは社内だけじゃもったいないとご紹介させていただきます。

本は、「ソフトウェアアーキテクチャの基礎（オライリー・ジャパン、Mark Richards/Neal Ford著　島田浩二訳）」。その第2章です。

*1:勤務時間内にやっていますし、そういうのに参加するのに特に上司の許可とかもいりません。Googleの20％ルールのような規定が明にあるわけではありませんが、業務と直接関係ない調査・勉強・研究にも自分の判断で時間を使えるのがエンジニアリンググループの文化となっています。

続きを読む

3年半デプロイのなかったクラウド電子カルテ体験版をついに本番追従させた話

こんにちは、電子カルテチームの鳥山(@to_lz1)です。私のチームではクラウド電子カルテ「エムスリーデジカル」を開発運用しています。今回はそんなエムスリーデジカルの "オンラインデモ版"、つまり体験版アプリケーションを3年半ぶりにアップデートさせたお話です。具体的には

  • インフラをAWSに移行
  • 最新のコードベースでデプロイ
  • 製品版のリリースと同タイミングでCI/CDできるように変更

という大きく3点を一気に実施しました。

3年半ぶりというとなんだかすごいことのようですが、そもそもなぜ製品版と異なる環境にあったのか、アップデートできないままだったのはなぜなのかといった疑問は皆さま抱かれるかなと思います。

この記事では、オンラインデモ版サイトの移行に関連するエムスリーデジカルのインフラの変遷、そして移行に際して工夫したこと・考えたことをご紹介しようと思います。

  • 前提
  • オンラインデモ版更新の意義と機運
  • 設計と工夫点
    • 案件推進面でやったこと
    • 技術面でやったこと
      • アカウントレベルの構成
      • リバースプロキシの改修
      • マスタデータ同期
  • 結果と振り返り
  • まとめ
  • We are Hiring!
続きを読む