DBのACID特性
DB周りの理解が浅いなと最近感じ、ACID特性も雰囲気でしか理解してなかったので、自分用にまとめました。
内容を知りたい方は、wikipediaで十分だと思います。
ACID特性とは
一言でいうと、DBに求められるトランザクションの要件のことです。
- A: Atomicity(原子性)
- C: Consistency(一貫性)
- I: Isolation(独立性)
- D: Durability(耐久性)
それぞれ、説明します。
Atomicity(原子性)
トランザクションに含まれるタスクが全て実行されるか、あるいは全く実行されないことを保証する性質です。
例えば、ECサイトでユーザが購入完了する処理と、店舗の在庫が減る処理が片方だけ発生してしまったら、Atomicityを満たしてないです。
Consistency(一貫性)
トランザクション開始時と終了時に制約を満たす性質です。
例えば、決済だけ行われて与信枠が減らなかったり、銀行の残高がマイナスにはなるとConsistencyを満たしてないです。
Isolation(独立性)
トランザクション中に行われる操作の過程が他の操作から隠蔽されるという性質です。
独立性とパフォーマンスはトレードオフの関係にあります。
あまりにも独立性を高めようとすると、一つ処理するトランザクションがあるだけで、他のトランザクションは参照できなくなり、パフォーマンスが低下します。
そのため例えば、MySQLではトランザクションの分離レベルが設定できます。
MySQL :: MySQL 5.6 リファレンスマニュアル :: MySQL 用語集
Durability(永続性)
トランザクションが完了したら、障害が発生したとしても結果は失われないという性質です。
ディスクに保存されておらずメモリ上で残ってるだけの状態で、ハードウェアに障害が発生した場合に、データが飛んでしまうと永続性がないです。
「チャイナ・イノベーション データを制する者は世界を制する」を読んだ
- 作者: 李智慧
- 出版社/メーカー: 日経BP社
- 発売日: 2018/09/28
- メディア: 単行本
- この商品を含むブログを見る
目的、モチベーション
全体の感想
アリババやWeChatの歴史を中心に俯瞰できてよかった。
海外規制してるから中国は国内の大きなサービスが育ってるという印象を持っていたが、昼夜問わずハードに働いたり、学術研究に投資して優秀な人材を確保したりするなど、成功すべくして成功してるんだなと思った。
中国政府は規制に対して厳しい印象を持っていたが、緩やかにその事業が世間にどのような影響を与えるか様子を見て、事業者と連携しながら規制しているのも印象的だった。
キャッシュレスを制するには、オンラインと連動してクーポンを配布したり、ミニプログラムを提供するなどして利便性を確保して、オフラインとの境界を抑えるのが重要なのかなと思った。
そこで得たデータを元に信用情報を構築して、新たなサービスも提供できる。
日本でのキャッシュレスキャンペーンは少し不毛だなと思っていたが、それで一大ブームになって定着するという側面もあるので、一面的には判断できないとも思った。
中国のITの現状や歴史をあまり詳しくなくて、アリババやWeChatを中心に中国のFintech事情を知りたい人にはオススメです。
目次
- 目的、モチベーション
- 全体の感想
- 目次
- 概要のメモ
概要のメモ
序章 米中貿易戦争とチャイナ・イノベーション
第１章 習近平国家主席とデジタル強国路線
国策として推し進めてる。 アメリカから制裁を受けたり、若者の就職先がないことの解決策の一つとして、国が起業やイノベーションを支援する。 その中で中小企業が飛躍できるように大手企業がプラットホームとして、機能などを提供することを要請。 その流れで、アリババやテンセントの決済がプラットホームとなり様々なサービスが生まれていくことになる。 技術の中ではAIで世界一になれるように、教育や、優秀な人材が集まる支援を積極的に行われた。
第2章 なぜ中国でイノベーションが爆発的に生まれているのか？
モバイル決済がイノベーションの起点
3G回線のインフラが整ったことや、シャオミやファーウェイなどの格安スマホによって、爆発的にモバイルのユーザ数が増えた。
また、国土が広くATMが日本と比べて便利なレベルでATMがなく、クレジットカードの普及も進んでいない。
そのやめ、オンラインでの決済ができないユーザが多かったが、アリペイがその解決になった。
モバイルの移行に伴い、アリペイウォレットを提供開始。急成長の要因は2つある。
1つ目は、6％を超える利息を受け取れるMMF（マネー・マーケット・ファンド）の発売（銀行の普通金利は0.35%）によって収益を生む財布として人気を得たこと。
2つ目は、独身の日のキャンペーンで、好調だったアリババのネットショッピングのユーザをモバイルへの誘導が功を奏したこと。
これらのシェアリングエコノミーは、利用者の信用情報の蓄積にも繋がる。
芝麻信用では、決済履歴や資産運用履歴、行動特性などの情報を分析し、ゴマスコアとして信用情報を数値化している。
欧米ではプライバシーが重視されてしばしば問題になるが、中国では利便性をもたらしてくれるなら気にしないぐらいの温度感で社会的にも受け入れられている。
アリペイのおかげで、サービスに必要な本人認証と決済をプラットフォームに任せることで、オフラインの様々なシェアリングエコノミーも普及している。
オフラインで使えるサービスを提供し、モバイル決済を普及させると共に、利用データや信用情報を蓄積させ、そのビッグデータから新しいサービスを提供していく。
データ蓄積によって個人の信用を点数化
アント・フィナンシャルの手掛けるゴマ信用は、取引履歴や支払履歴、行動特性などのデータを分析し、個人の信用力をゴマスコアとして数値化。
ゴマスコアに応じて少額融資を行い、TmallやTaobao等で買い物する際にも使える。
従来の中国人民銀行の信用情報サービスでは、銀行のデータから構築したために半分以上の国民は基礎情報しかないのに対して、ネット企業は様々な情報からスコアリングが行える。
個人情報が企業に利用される形になるが、利用者の殆どは、様々な利便性をもたらしてくれるならあまり気にしないという温度感。
第３章 阿里巴巴（アリババ）集団と騰訊控股（テンセント）――中国版巨大プラットフォーマーの誕生
なぜアリババが成功したのか？
信用情報が未整備で、クレジットカードの保有率の低い中国では決済のコンバージョンが悪く、eBayなどの欧米のスタイルがなじまなかった。
それに対して、アリババはエスクローサービスを中国で最初に導入した。
ジャック・マーの「問題が起きれば、僕が刑務所に行く」という強い決心で開発が急ピッチで進んだ。
いざリリースしても、非銀行であるアリババを不安に思うユーザが多く、不安を払拭するために全額補償のキャンペーンを行った。
さらに、手数料を無料化してeBayと差別化を図った。
独身の日のセールの負荷に耐えられるように、Ocean BaseやAliyunを自社で開発し、分散型アーキテクチャに移行して対応した。
これらの技術力を活かし、他社にもアリババクラウドを提供する。
決済手段から生活サービスのプラットフォームへ
ダブル11のオフライン版であるダブル12では、スーパーやレストランなどで半額のキャッシュバックキャンペーンを行い、デジタルに疎い50,60代にリーチすることができた。
決済件数が増えるだけでなく、加盟店はレジ精算時間も大幅に短縮され業務改善にもつながった。
海外展開は、ローカルの企業に出資などして提携を結んで進めた。
微信（ウィーチャット）発展史
単なるメッセンジャーから、SNS的な機能を付け加えていき、国内では独占状態になった。
「テンセントが進出する事業には手を出さない」という暗黙のルールができるほど無双状態になる一方で、独占状態に批判が集まるように。
そこでオープン化戦略を取ることにし、サービス提供者向けにユーザとつなげるツールを提供。
- 購買アカウント
- 情報発信
- サービスアカウント
- 会員管理、販促
- 企業アカウント
- 内部管理の効率化、関連企業や顧客とのコミュニケーションの円滑化を支援するSaas
2017年1月には、wechat内で完結しDLも不要なミニプログラムをリリース。
お年玉をwechatで送れる機能では、ゲーム性を取り込み、テレビの人気番組と連動したキャンペーンを行い、ユーザを引き込んだ。
大晦日の0〜19時の間で、2000万人が4億回のお年玉のやり取りを行った。
第４章 ２強を追う先端技術企業
滴滴出行（DiDi）――本家も飲み込む生命力
滴滴出行は最初は投資家やユーザもおらず、運転手の10数名しかいない状態でスタート。
SNSのクチコミで徐々にユーザ数が増え、優秀なエンジニアを雇って開発を内製にすると、マッチングの効率化等の改善を行い、事業が成長していった。
wechatで決済できるなどして連携を図っていく一方で、アリババが出資する快的打车も順調にユーザ数を伸ばす。
キャンペーン合戦となりお互い大きな赤字を掘り、最終的には合併にいたった。
UBERは中国に進出し、運転手に高い奨励金を出して繋ぎ止めを図る。
真っ向から勝負となったが、CS対応は電話が一般的な中国でメールで対応するなどローカライズできず、細やかな改善を重ねた滴滴出行がシェアを守った。
泥沼の赤字の戦いは、投資家主導で休戦することになり、UBERが滴滴出行の5.89%の株式を取得することで幕を閉じた。
フィンテック企業やAIスタートアップの紹介
- 世界最先端のフィンテック企業
- 衆安保険－―従来の発想に捉われない商品開発で急成長
- 微衆銀行（WeBank、ウィーバンク）――中国初の民営銀行
- 京東金融（ＪＤファイナンス）――アント・フィナンシャルの後を追う
- 急成長するAIスタートアップ企業
第５章 急速に進むデジタル化の負の側面
頻発する悪質ネット詐欺
資金を投資家から集めながらも、私的に利用されて資金が回収できなくなった事例等が紹介されていた。
ICOでも詐欺的な問題が発生し、規制による取締が行われた。
羊毛党ｖｓネット企業――テクノロジーを悪用した詐欺集団
セール商品を大量に転売されたり、プロモーションのキャンペーンを不正に受け取るために、架空の取引を発生させるなどの事例が紹介されていた。 犯罪にもAIが応用されて、ツールが販売するなどして不正収入を受け取られてる。
第６章 中国型イノベーションの本質と先端企業との付き合い方――ユニクロ、メルカリの事例
ユニクロの中国戦略
wechatの公式アカウントを広めるために、シェアすればするほど当選確率の上がるキャンペーンを行った。
独身の日は売上が立つが、流通が追いつかない。 そのため独身の日だけ、オンラインとオフラインでセール価格を統一して、オフラインの店舗で受け取れるようにした。
- 作者: 李智慧
- 出版社/メーカー: 日経BP社
- 発売日: 2018/09/28
- メディア: 単行本
- この商品を含むブログを見る
「aCrew Vol.1 for FinTech ~メルペイ、Origami、d払い登壇！スマホ決済サービスのグロース特集~」に参加してきた
本編
講演 ① App Annie 向井氏 「スマホ決済アプリ市場の海外/日本のトレンドについて」(仮)
参加できなかったので割愛。
講演 ② Repro 平田「スマホ決済アプリのグロースのポイント」
参加できなかったので割愛。
トークセッション「キャッシュレスアプリとデータ活用（仮）」
登壇者
モデレーター
- Repro株式会社 CEO 平田 祐介
- App Annie Japan（株）日本代表ディレクター 向井 俊介 氏
パネリスト
- Fintech協会 代表理事 丸山 弘毅 氏
- （株）メルペイ 営業統括 兼 社長室長 金 高恩 氏
- （株）ＮＴＴドコモ プラットフォームビジネス推進部 ペイメントビジネス担当課長 高須 真 氏
- （株）Origami マーケティング責任者 古見幸生 氏
各サービス紹介
d払い
- docomoのpaypay w
- 500万DL
- 使える店舗も増えてる
- 1600億ポイント/年
- 2019FY〜
- ウォレットチャージ機能
- ミニアプリ
- 中小店向け 読み取る決済
Origami
- ミッション：お金、決済、商いの未来を創造する
- 2015年でOrigamiPayローンチ
- 2016年11月：Alipayと提携
- アプリの機能
- 支払い前: 使える店舗の情報、キャンペーンなど
- 支払い後: 支払履歴など
- 強み
- 即時割引
- チャージ不要
- キャンペーン
- 地域活性化型キャッシュレス
- インバウンド/アウトバウンド
- オープン化（金融プラットフォーム解放）
- データも他の銀行とかも使えるように
merpay
- 信用を創造して、なめらかな社会を創る
- 他のサービスとは、給料以外のお金の流入源を持ってるのが大きな違い
トークセッション
アプリを使ってもらうために、可処分時間やマインドシェアを取るために、意識してること
- Origami
- merpay
- 決済は目的ではなく、あくまでも手段
- 独立とかメディア化は考えてない
- メルカリ自体が滞在時間長いアプリで、アプリの種類としてはSNSでの行動に近い
- d払い
- 長期的にはメディア化を目指す
- 決済だけだとお得かどうかで選ばれてしまうので、便利な方向性を目指す
- ミニプログラムの提供等を通して、安心安全な決済基盤の上に他社が乗っかるプラットフォームを目指す
日本ではアプリ多すぎるが、どうなっていきそうか
- Fintech協会
- Origami
- ドンドン増えていくと予想
- クレジットカードを見てるとドンドン増えてる
- Origamiはクレジットカードでいうvisaとかになるイメージ
- merpay
- ユーザがどう使うかを重視していて、paymentは手段でしかない
- merpayを全員に使ってもらうというよりは、paymentがシームレスになることが重要
- 3,5年後アプリでない形になるのもありえるのでは
- d払い
- 6個ぐらいでは
- QRコードが統一されていないので、淘汰されていく
- 送金とかの決済以外のシーンとかを考えると特にいくつかに絞られていくのでは
お金ばらまいてるがビジネスモデルは？
- merpay
- 信用を創造して
- 後払いは既にローンチして使われている
- paymentという文脈でECとか見てると決済は儲からない
- 価値交換や物々交換とかを考えると、信用に行き着く
- 信用でマネタイズしていくのが一つ
- 銀行
- 現金なくなった方が管理コスト減るので、ATMの設置費用とか減る
- B2Bとか含めて送金できてるのが差別化になりそう
- Origami
- できることとやっていいことは別
- 個人情報で信用ビジネスになるのは少しアレルギー感
- 1企業がデータを持つのはGAFA問題みたいになるので、オープンにしていくべきでは
- LINE@的なポジションを狙いたい
- d払い
- 携帯回線7000万人のデータはある
- オフラインだけの額はそんなに大きくないが、リアルの決済額は大きいので決済手数料0.5%でも事業は成り立つのでは
- Fintech協会
- 信用が変わるのは革新的
- 現在は、勤め先や収入と給与で信用が今決まってる
- それ以外で決まるのは、大きな革新
- マネタイズ
- キャッシュレスが進むとレンディングは伸びる
- 今はキャッシュレスの割合が2割とかなので、レンディングの額が小さく使われていない
- キャッシュレス化が進めば、レンディングの額が大きくなっていく
- 銀行がAPI使って勝つ可能性も
- 信用が変わるのは革新的
外国人に向けた何かは考えているか
外資のサービスが日本に入ってきていて、データが海外に行ってる。
日本の労働人口もどんどん減っている一方で、海外からくるヒト（観光客、労働者）も増えてる。
人口と流通額に依存したビジネルモデルだとシュリンクしていくので、インバウンド狙った方が良いのでは
- d払い
- 現状は、国内で手一杯
- Origami
- 各社が各店舗に営業していくのは厳しいので、連携していく流れになるのでは
- merpay
- 法律で守られてるとこもあるが、データの取扱に関しては別
- 詳しくはここでは話せない
- Fintech協会
- エコシステムでデータ保護主義
- data flow with trust
- エコシステムでデータ保護主義
- Origami
- やりきるつもりではいる
- merpay
- やるつもりだが、仕様を早く決めてほしいw
- Fintech協会
- 協議会が決めていて、今進めているので仕様はもう少し待ってくれ
- d払い
- 努力はしてる
日本は災害大国だが、災害時の対応は想定しているか
Maas
ETCの普及はしたが、ドライブスルーの支払いはまだ物理だが、車載のアプリ等で解決しないのか
- Origami
- TOYOTAとのLEXUS Origami Payで進めてる
- スマートシティとか街全体の環境が必要
- QRコードが普及してるのもコストが低いから
- merpay
- インフラ重要
- 他の国で進んだのは国策なのが大きい
- d払い
- ミニプログラムの根本は、利便性を向上したいというところからなので、そこにつながる
- 今年は提携業者と組んでリリース。来年は順次解放予定
「顧客体験をデザインする。#03」に参加してきた
参加メモ
大規模B2B Eコマース "モノタロウ" におけるテクノロジー - ECサイトから物流まで -
登壇者: 株式会社MonotaRO 執行役 データマーケティング部門長 久保 征人 @masatokubomro
フルスタックEコマース
モノタロウの紹介
- 特徴
- 在庫を持ってる
- 全て自社開発、運用
- 商品1800万点 353万事業者
- グローバル企業
フルスタックECにおける顧客体験の向上
会社として、顧客の接点の種類が多い
当社のケースでは、全ての業務担当者が、顧客体験を向上させることが可能な当事者である
- 管理
- CS
- IT
- 物流
=> その全ての業務担当者をエンジニアがサポートできれば、それが最も顧客体験の向上に繋がる
仕事が捗る基盤を作るとは
- 業務を自動化して生産をあげる => IT基盤を整える
- 業務分析と改善を加速させる => データ基盤を整える
データドリブンカンパニーとは
- 意思決定を支える経営と文化
- 意思決定を支える基盤
- 意思決定を支えるデータリテラシー
モノタロウのデータ基盤
- オンプレ時代
- 日時バッチでdata warehouseに突っ込んでた
- 新しいデータ基盤の必要性
- データが分散してる
- テーブル増える度に運用が限界
- スペックが足りない
- まだまだデータ増やしたい
- BigQuery
- GoogleAnalytics
- ApplicationLog
- MySQLのデータをリアルタイムで
- Binlog Connector
- 擬似的にMySQLのスレーブとして接続
- GitHub - shyiko/mysql-binlog-connector-java: MySQL Binary Log connector
- 3〜5分ぐらいの遅延レベルでリアルタイムに同期
成果
- データ量の限界はなくなった
- 100テーブル => 1000テーブル〜
- ダッシュボードの数も増えた
- 〜30 => 300
まとめ
- ECにおける顧客体験には業務担当者の業務が関わる
- それを達成する一つの方法が、業務分析 => 改善をサポート
ショップと顧客の絆を深める、デジタル＆リアルでデザインするEコマース顧客体験
登壇者: 株式会社ecbeing 製品開発統括部 統括部長/執行役員 渡邊 健太
会社紹介
本編
ECの中では、アプリの割合が大きいので、アプリも重要。
しかし買い物全体のうちECの占める割合がだんだん増えている一方で、オフラインでの行動が購入には重要であり続けている。
そのため、ECとオフラインの連携が重要である。
デジタルとリアルの顧客体験が重要
カスタマージャーニーマップ
デジタル&リアルで
nano universeの事例
ちゃんと、リアル店舗の在庫を連携できてるところは少ない
絆を深める、専門性の高いコンテンツ
ユーザが納得して購入できるように、ストーリー性を持って理解できるコンテンツを提供。
ライフスタイル提案・体験機会の提供
インテリア領域では特に、実際に家具を置いたらどうなるのかイメージを持ってもらうことが重要である。
unicoでは、3Dコーディネートの機能でカバーしている。
ユーザとブランドの絆の創出
設計・開発のポイント
- 「体験」を先に設計する
- デジタルとリアルの補完関係
- プロトタイピング
- 開発チーム / UXデザインチームの密度
- 「万人受け」よりも「こだわり派の納得性」を重視
- ペルソナ設定
- ユースケース記述
- リサーチと使い込み
- 体験の中心にスマホを考える
- スマホのGPS連動で、店舗の近くにユーザが来たらプッシュ通知
- 店舗に入ったユーザに対して、チェックインスタンプ、来店クーポンの配布
- スタッフ用のアプリで、連携してユーザを特定して、購入履歴、接客履歴、レコメンド商品
ABCマート スタッフ用のアプリで在庫状況をデータで把握
このあたりから、インスタとの連携などのチャネルや少しボイスコマースなどの話がありましたが、個人的にはあまり興味の範囲でなかったので割愛します。
まとめ
- あらゆる行動の中心にスマホがある
- モノ・情報・ヒトをデジタル＆リアルの体験に活用する
- 体験から先に、ペルソナを明確に設計する
- ファンと共に創り上げる顧客体験がSNSによって拡散する
- 5G時代には、顧客体験は動画が中心になる
- これから来るかも「ボイスコマース」
楽天スーパーSaleの舞台裏 - お買い物カゴシステムの負荷対策
登壇者: 楽天株式会社 ECマーケットプレイス開発部 Marketplace Core Architect Section シニアマネージャー 橋山 牧人 @capyogu
自己紹介
- 経歴
- 現在の仕事
- プライベート
- ゲーム
- プログラミングスクール講師、執筆活動
前提の説明
楽天スーパーセール => 2012年3月より開始した大型セールイベント
楽天スーパーセールの当日の様子
100名以上のエンジニアが同じフロアで監視
監視内容
- The Four Golden Signals
- Latency
- Traffic
- Errors
- Saturation
独自の監視項目
ビジネス的に重要なポイントを重点的に
- エントリー数
- 売上高
- 受注件数
- メール配信
トリアージの具体例
あくまでも、お買い物の継続が最優先で、外部要因であれば機能を切り捨てる。
例えば、外部APIを利用して表示してる機能や、お買い物のフローに関係のないサブ的な機能は切り捨てる。
トリアージの失敗例
会員ランクに応じて付与するポイントが変わるため、半年ぐらいかかる地獄に陥った。。
事後影響を考えると、会員サービスダウン時はお買い物かごを停止させるべきであった。
緊急時に何を優先するか、ビジネスや補償の観点を含めて事前に決めておくことが重要。
負荷試験
負荷状況の再現方法
※ 結構過去の話だそうです。
開始直後のピーク時には、通常ピーク時の約20倍のアクセス
深夜に本番環境で負荷試験
当時のエンジニアがノウハウを持っていたJMeterを採用。
イメージとしては、負荷生成サーバを構築して本番のユーザと同様に振る舞ってリクエストするみたいです。
試行錯誤その1 負荷テストの設計
- 全ユーザシナリオを再現するのは非現実的
- 90%のユーザアクセスがカバーできるシナリオを設計し、呼び出すAPI・システムを選別
- 何を目標とするか:
- 共通の目標数値: 分間受注件数
- 覚えやすい、理解しやすい共通目標を設定することで、課題や達成度を明確にできる。
試行錯誤その2 データの追加、フィルタリング、破棄
- トラフィック量・レイテンシが想定よりも少ない
- 原因1: 各ダミーデータのデータサイズが本番よりも小さかった
- 原因2: 特定のページや商品に集中したためキャッシュが効いた
- 大量のダミーデータを用意(20万の会員、6500の店舗、100万の商品)
- テストデータのフィルタリング、掃除
- 負荷試験のために、ダミーのデータの処理はさせたい
- その一方で、サービス影響出ないようにダミーのデータは早く破棄したい
対策
人気商品への対応
セール商品の分類
特性が異なるので、対応策も別々になる。
| 商品タイプ | 概要 | アクセス | 在庫数 | 商品例 |
|---|---|---|---|---|
| タイムセール商品 | 通常のセール商品。普段から売られてることが多い。 | 中 | 多い | カニ、肉、水 |
| 目玉商品 | スーパーSaleのみで販売。希少性や割引額が特に高い商品。 | 大 | 少ない | 車、宝石、時計 |
| 人気商品 | 特定の層に人気。値段はそれほど高くない。テレビで紹介された、など。 | 大 | 多い | 特定のファッションアイテム、おもちゃ、消耗品 |
今回の事例では、 人気商品に該当する、当時人気だった妖怪ウォッチのおもちゃ等の事例。
なぜシステム上の問題が出たのか
対策1: 専用システムを構築し、検知の仕組みを導入
人気商品を別のシステムに隔離することで、負荷でシステムがスローダウンしても通常のお買い物は継続させる。
対策2: 在庫キャッシュの更新を非同期にする
そもそも同期処理したところで、ユーザがアクションするタイミングで在庫状況がずれるので意味がない
今後の取り組み
| 課題 | アクション |
|---|---|
| スーパーSALE同様の負荷を受けきれる試験用の環境が用意できていない | クラウドプラットフォームに簡単にデプロイできるためのコンテナ化、マイクロサービス化 |
| スーパーSALE同様の負荷を柔軟かつ安全にかける手段が十分に用意できていない | システムメトリクスと紐付いた、クラウドベースの自動テスト実行プラットフォームの開発 |
| 複数のサービスを跨ったトラブルシューティングが十分なスピード・精度・統一された手段でできていない | 統一プラットフォーム上のサービスメッシュの導入 (1)分散トレーシングによるトラフィックの追跡 (2)Circuit BreakerによるSystem Reliability |
今後のシステムアーキテクチャ
素数の一覧を求めるアルゴリズムのメモ
素数の一覧を求めるアルゴリズムの問題を出されて、良い計算量のアルゴリズムがわからなかったときに調べたメモです。
素数の一覧を求めるアルゴリズム
素数の定義
学術的には不正確かもしれないですが、今回はwikipediaで十分なので、こちらで進めます。
1 より大きい自然数で、正の約数が 1 と自分自身のみであるもの
普通の方法
約数が1以外は自身のみなので、自身より小さい素数で割り切れるものが一つも無ければ、自身は素数となります。
def normal(max_number) (2..max_number).each_with_object([]) do |i, primes| primes << i if primes.detect {|p| i % p == 0 }.blank? end end
この方法では、計算量がO(N2)になるので効率が悪いです。
エラトステネスの篩(ふるい)
というアルゴリズムがあるそうです。
ステップ 1 探索リストに2からxまでの整数を昇順で入れる。
ステップ 2 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
ステップ 3 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
ステップ 4 探索リストに残った数を素数リストに移動して処理終了。
例はwikipediaにも詳しく載ってるので割愛します。
アルゴリズムのイメージ
上に示したステップだけだとよくわからなかったので、腹落ちするように流れを分解して解釈しました。
- 数字のリストから、素数の小さいものから順にその素数の倍数(ex. 3の場合は 9, 12, 15...)を取り除いていけば、リストに残るのは素数のみになる。
- また除外する際には、自身の2乗以上の倍数のみでよい。
- 自身より小さい値との組み合わせは既に取り除かれているため(ex. 3の場合は 6は2の倍数なので、取り除かれている)
- その倍数として取り除いていく素数の必要最小限の値は、リストの最大値の平方根になる。
- 平方根の値より大きい値との倍数は、リストの最大値を超えるため
実装
def eratosthenes(max_number)
primes = []
max_sqrt = Math.sqrt(max_number).to_i
options = (2..max_number).to_a
prime = 1
while prime <= max_sqrt
prime = options.shift
primes << prime
multiples = (max_number / prime - (prime - 1) ).times.map {|m| prime * (m + prime) }
options = options - multiples
end
primes + options
end
結果の比較
MAX_NUMBER = 10000 Benchmark.bm 10 do |r| r.report 'normal' do normal(MAX_NUMBER) end r.report 'Eratosthenes' do eratosthenes(MAX_NUMBER) end end
| MAX_NUMBER | normal | Eratosthenes |
|---|---|---|
| 1000 | 0.001585 | 0.000413 |
| 10000 | 0.070549 | 0.004512 |
| 100000 | 3.807569 | 0.059691 |
| 1000000 | 248.255773 | 1.362347 |
