ホームページ >バックエンド開発 >PHPチュートリアル >アルゴリズムに国境はない、国産アルゴリズムも同等に優れている_PHPチュートリアル
アルゴリズムに国境はない、国産アルゴリズムも同等に優れている_PHPチュートリアル
- WBOYオリジナル
- 2016-07-13 10:37:35993ブラウズ
[CSDN レポート] 数日前、CSDN は、外資系 AddThis 社のデータ分析担当副ディレクター、マット エイブラムス氏が発表した高スケーラビリティに関する記事をまとめました。この記事では、マット エイブラムス氏は、AddThis が使用するメモリは 1.5KB のみであると読者に紹介しました。 10 億の異なるオブジェクトが計算され、アルゴリズムの魅力が十分に実証されました。
この記事は Weibo で広く注目を集めましたが、Yitao のアルゴリズムも同様に優れていることがわかりました。この目的のために、CSDN はイータオ データ部門の Zhang Yang 氏にインタビューしました (彼は煙台大学と北杭大学で学びました。2011 年に北杭大学でコンピュータ理論の修士号を取得しました。彼は同じ年にタオバオに入社し、現在イータオ データ部門で働いています) .work)、Yitao の関連アルゴリズムについて説明してもらいます。
写真: Yitao データ部門エンジニア、Zhang Yang
CSDN: まず初めに、自己紹介と普段の仕事について教えてください。
張楊: 私の名前は張楊、社内でのあだ名はイェジです。現在、彼はイータオのデータ部門で平凡なプログラマーとして働いており、何千人ものプログラマーと同じように、毎日コードを入力してプログラムを書くことが人生で 2 番目に大きな楽しみであると考えています。楽しみは食べることです）。私は PHP、Nginx、データ マイニング、機械学習、アルゴリズム、コンパイラー、分散ストレージ コンピューティングなどのテクノロジーに非常に興味があり、数学と歴史も好きです。私はプログラムを書くという仕事がとても好きで、プログラミングを生涯の仕事にしたいと思っています。プログラムを書くことに加えて、数学やアルゴリズムを学ぶことも好きです。同時に、学んだことを記事にまとめてブログに公開し、興味のある友人が私のブログ (codinglabs) にアクセスしてください。 .org。
Yitaoのデータ部門での私のポジションはフロントエンド開発ですが、私の「フロントエンド開発」は一般的なフロントエンドエンジニアよりも複雑で、HTML、CSS、JavaScriptを担当することに加えて、バックグラウンドプログラムの開発も行っています。 PHP と Lua については、自分の興味やニーズに基づいて C およびアルゴリズムのプログラムを開発することがあります (C とアルゴリズムを書くのがとても好きで、それをとても楽しんでいます)。同時に、運用とメンテナンスの作業も行います。 、サーバー環境の構築やオンラインサーバーの保守など。
CSDN: アルゴリズムに興味を持ったきっかけは何ですか?
張楊: 多分それは私が数学に興味を持っていたからかもしれません。私はずっと数学的なことが好きでした。私がアルゴリズムに正式に触れるようになったのは、大学 2 年生のときでした。当時『アルゴリズム入門』を購入し、漸近複雑性やアルゴリズム分析など、アルゴリズム分野の最も基本的な一連のことを実際に理解し始めました。 、動的計画法、貪欲アルゴリズム、および NP 問題。読んだとき、この本に書かれているすべてのアルゴリズムが人間の知恵の結晶であると感じ、これらを読んで学ぶと、言葉では言い表すのが難しい満足感と喜びを感じました。その後の研究や仕事の中で、アルゴリズムがさまざまな分野で現実的な問題をどのように解決し、人類の文明の発展を促進できるかを実際の応用から理解し、評価し続けました。これにより、アルゴリズムへの敬意が深まりました。
CSDN: なぜ Yitao データ部門はこのカーディナリティ推定アルゴリズムを開発したのですか?
Zhang Yang: Yitaoデータ部門は主に電子商取引の分野でデータ分析とマイニングを行っており、これらのテクノロジーをビジネスと密接に統合して、データ分析、推奨システムなどのデータ製品やサービスを形成しています。すべて。これらのデータ製品は、外部関係者にサービスを提供するだけでなく、企業またはグループの内部業務のサポートも提供します。
電子商取引データ分析の分野では、いくつかの非常に重要な指標 (特定の時間と空間の制約下での独立訪問者の数を指す UV と呼ばれるユニーク訪問者など) の計算が非常に一般的なタスクです。一般的に、最初に何らかの手段 (Cookie など) で各ユニークな訪問者をマークし、次にその訪問者のマークをすべてのアクセス ログに記録します。このようにして、UV の計算は、ユニークな要素の数を計算することと同じになります。反復可能なユーザー タグ セット。これは数学的なカーディナリティです。
底の計算には 2 つの困難があります:
第一に、これはリアルタイム ストリーム コンピューティングの実装には適していません。たとえば、当社の製品の中には、特定の時点 (今日の午前 0 時など) から現在までのユニーク ビジターの数であるリアルタイム UV を提供するものもあります。これを実現するには、検索パフォーマンスの高いデータ構造 (B ツリーなど) を UV 値ごとにメモリ内に維持する必要があります。これにより、リアルタイム ストリームで新しい訪問が来たときに、すぐにアクセスできるようになります。訪問者がすでにここにいたかどうかを調べます。これにより、UV 値が 1 増加するか変化しないかが決まります。この種のサービスを 100 万店舗に同時に提供したい場合は、100 万の B ツリーをメモリ内に維持する必要があり、また、さまざまなソース ディメンションから UV を計算する必要がある場合、この数は急速に拡大します。これは、サーバーのコンピューティング リソースとメモリ リソースにとって大きな課題です。
2 番目の点は、従来のカーディナリティ計算方法を効果的に組み合わせることができないということです。たとえば、前の 1 時間とこの時間の UV は別々に計算されていますが、これら 2 時間の合計 UV を確認するには複雑な計算を実行する必要があります。ビットマップ データ構造を使用したソリューションは迅速にマージできますが、期間の組み合わせの数は期間の数とパワーレベルの関係があるため、空間の複雑さが高すぎます。そのため、B ツリーも単純なビットマップも使用できません。ビッグデータの前でも同様です。
上記の背景に基づいて、Yitao データ部門の技術専門家である Wang Xiaozhe (名前は Qingwu) は、カーディナリティ推定の関連アルゴリズムと Clearspring (stream-lib) の Java 実装を研究し、ホログラフィック効果プラットフォーム (コードネーム Moonlight Treasure Box) ) は、プロジェクトにカーディナリティ推定アルゴリズムを導入し、大量の UV を計算するために少量のメモリを使用するという技術的問題を実現し、すべての会場のリアルタイム効果を実現しました。ダブル イレブンとダブル トゥエルブのプロモーション期間中に、Tmall と Taobao でピットインします。
より多くの非 Java プロジェクトがそのようなアルゴリズムを使用できるようにするために、Wang Xiaozhe と私は、関連する論文に基づいて、エンジニアの Zhang Wei (Hua Mingminzhan) を参照して、ccard-lib の C バージョンの実装を提供しました。 Yitao のデータ部門から) を使用し、PHP 拡張機能を実装しました。現在、この C の実装は Yitao データ部門の複数の製品で使用されており、github を通じてオープンソース化されています。
CSDN: イータオデータ部門のカーディナリティ推定アルゴリズムを読者に詳しく紹介してもらえますか?
Zhang Yang: 私たちが使用するアルゴリズムは主に適応カウンティング アルゴリズムです。このアルゴリズムは論文「適応カーディナリティ カウンティングを使用した高速かつ正確なトラフィック マトリックス測定」に記載されていますが、線形カウンティングや LogLog カウンティングなどの共通カーディナリティ推定アルゴリズムも実装しました。および HyperLogLog カウンティング。
これらのアルゴリズムは確率的アルゴリズムであり、ある程度の精度を犠牲にすることでコンピューティング リソースの使用量を大幅に節約します (ただし、精度は制御可能であり、精度を制御する方法は数学的分析によって提供できます)。たとえば、わずか 8k のメモリを使用して数億の UV を推定でき、誤差は 2% を超えないため、B ツリーやオリジナルのビットマップを使用する場合と比較してメモリを大幅に節約できます。同時に、カーディナリティ推定アルゴリズムはハッシュ変換されたビットマップ空間を使用するため、効率的なマージを実現しながらメモリを大幅に節約でき、上記の 2 つの問題を同時に解決できます。
2^16 (64K) ビットを使用する場合、推定結果は次のようになります:
Murmurhash を使用した線形カウント:
実際: 50000、推定: 50062、誤差: 0.12%
実際: 100000、推定: 99924、誤差: 0.08%
実際: 150000、推定: 149865、誤差: 0.09%
実際: 200000、推定: 199916、誤差: 0.04%
実際: 250000、推定: 250123、誤差: 0.05%
実際: 300000、推定: 299942、誤差: 0.02%
実際: 350000、推定: 349801、誤差: 0.06%
実際: 400000、推定: 400101、誤差: 0.03%
実際: 450000、推定: 449955、誤差: 0.01%
実際: 500000、推定: 500065、誤差: 0.01%
Lookup3hash による線形カウント:
実際: 50000、推定: 49835、誤差: 0.33%
実際: 100000、推定: 99461、誤差: 0.54%
実際: 150000、推定: 149006、誤差: 0.66%
実際: 200000、推定: 198501、誤差: 0.75%
実際: 250000、推定: 248365、誤差: 0.65%
実際: 300000、推定: 298065、誤差: 0.65%
実際: 350000、推定: 347504、誤差: 0.71%
実際: 400000、推定: 397292、誤差: 0.68%
実際: 450000、推定: 446700、誤差: 0.73%
実際: 500000、推定: 495944、誤差: 0.81%
Murmurhash を使用したハイパーログログのカウント:
実際: 50000、推定: 50015、誤差: 0.03%
実際: 100000、推定: 100048、誤差: 0.05%
実際: 150000、推定: 149709、誤差: 0.19%
実際: 200000、推定: 201595、誤差: 0.80%
実際: 250000、推定: 250168、誤差: 0.07%
実際: 300000、推定: 299864、誤差: 0.05%
実際: 350000、推定: 348571、誤差: 0.41%
実際: 400000、推定: 398583、誤差: 0.35%
実際: 450000、推定: 448632、誤差: 0.30%
実際: 500000、推定: 498330、誤差: 0.33%
Lookup3hash を使用したハイパーログログのカウント:
実際: 50000、推定: 49628、誤差: 0.74%
実際: 100000、推定: 99357、誤差: 0.64%
実際: 150000、推定: 148880、誤差: 0.75%
実際: 200000、推定: 200475、誤差: 0.24%
実際: 250000、推定: 249362、誤差: 0.26%
実際: 300000、推定: 299119、誤差: 0.29%
実際: 350000、推定: 349225、誤差: 0.22%
実際: 400000、推定: 398805、誤差: 0.30%
実際: 450000、推定: 448373、誤差: 0.36%
実際: 500000、推定: 498183、誤差: 0.36%
Murmurhash を使用した適応型カウンティング:
実際: 50000、推定: 50015、誤差: 0.03%
実際: 100000、推定: 100048、誤差: 0.05%
実際: 150000、推定: 149709、誤差: 0.19%
実際: 200000、推定: 201059、誤差: 0.53%
実際: 250000、推定: 249991、誤差: 0.00%
実際: 300000、推定: 300067、誤差: 0.02%
実際: 350000、推定: 349610、誤差: 0.11%
実際: 400000、推定: 399875、誤差: 0.03%
実際: 450000、推定: 450348、誤差: 0.08%
実際: 500000、推定: 500977、誤差: 0.20%
Lookup3hash を使用した適応型カウント:
実際: 50000、推定: 49628、誤差: 0.74%
実際: 100000、推定: 99357、誤差: 0.64%
実際: 150000、推定: 148880、誤差: 0.75%
実際: 200000、推定: 199895、誤差: 0.05%
実際: 250000、推定: 249563、誤差: 0.17%
実際: 300000、推定: 299047、誤差: 0.32%
実際: 350000、推定: 348665、誤差: 0.38%
実際: 400000、推定: 399266、誤差: 0.18%
実際: 450000、推定: 450196、誤差: 0.04%
実際: 500000、推定: 499516、誤差: 0.10%
Murmurhash を使用したログログのカウント:
実際: 50000、推定: 59857、誤差: 19.71%
実際: 100000、推定: 103108、誤差: 3.11%
実際: 150000、推定: 150917、誤差: 0.61%
実際: 200000、推定: 201059、誤差: 0.53%
実際: 250000、推定: 249991、誤差: 0.00%
実際: 300000、推定: 300067、誤差: 0.02%
実際: 350000、推定: 349610、誤差: 0.11%
実際: 400000、推定: 399875、誤差: 0.03%
実際: 450000、推定: 450348、誤差: 0.08%
実際: 500000、推定: 500977、誤差: 0.20%
Lookup3hash を使用したログログのカウント:
実際: 50000、推定: 59870、誤差: 19.74%
実際: 100000、推定: 103044、誤差: 3.04%
実際: 150000、推定: 150435、誤差: 0.29%
実際: 200000、推定: 199895、誤差: 0.05%
実際: 250000、推定: 249563、誤差: 0.17%
実際: 300000、推定: 299047、誤差: 0.32%
実際: 350000、推定: 348665、誤差: 0.38%
実際: 400000、推定: 399266、誤差: 0.18%
実際: 450000、推定: 450196、誤差: 0.04%
実際: 500000、推定: 499516、誤差: 0.10%
セクションの幅に限りがあるため、ここでこれらの計算法の詳細を説明することはできませんが、以前に私は博覧会で 1 つのセクションを翻訳した文章を公開しましたが、その内容は概説的なものではありませんでした。算法の数処理規則と文書のいくつかの解説が含まれており、興味のある友人と私たちの博客を歓迎しています。
CSDN: マイクロ博覧会で「ペイコード癖重度患者」と呼ばれているのを見て、これは非常に興味深い呼称ですが、ペイコードの性質を理解できるかどうか、平時に暗号化プロセス中にどのようにペイコードを維持するかが重要です。规范？
洋：これは実際に非常に重要な意思表示です。完璧な主がいます。
このような事情はともかく、算術のような比較的専門的な分野であれば、このような完璧な要求を維持することはできますが、多人数の協力が必要な分野では適していません。コードの維持に関しては、プログラムを完全に実行することは不可能であると考えられており、ツール (lint など) およびフロー解除保護の方がより効果的です。CSDN: 将来の工作においては、さらにいくつかの困難を克服する必要がありますか?
张洋:
克服する困難は主に双方向から来ます。 一方は、計算法自体が修正された困難
であり、この世界には完全に暇な計算法、たとえば上の基数転送計算法が存在せず、内部メモリの使用量が大幅に減少していますが、結果的に内部メモリの使用量が膨大で、ビットマップが結合されています。また、内部メモリと磁気ビットマップの結合が必要な場合もあり、ビットマップの量が多すぎると、磁気ビットマップがボトルネックと呼ばれるため、特定の分野に合わせてどのように演算法を拡張および変更するかが課題となる。別の方法は、関連するコンピューティングの最新の研究成果を、現在のボールボールのさまざまな研究機関や企業を介して知ることであり、これには、関連するプロセスの論理レベルを考慮した、コンピューティング自体の数学的分析の深い理解が必要です。要求はもっと高い。一方、アルゴリズムとビジネス製品の組み合わせです。結局のところ、アルゴリズムは比較的形式的なものであり、具体的に製品に適用できるまでにはまだ長い道のりがあります。アルゴリズムとプロダクトの最適な組み合わせを見つけることも、この作業の重要なポイントであり、難しさの 1 つです。
2012 年が過ぎ、私たちは世界の終わりを迎え、世界の新たな章の幕開けを迎えました。 2013 年には、あらゆる種類のデータがインターネットに溢れかえり、あらゆるインターネット企業が直面する問題の 1 つになります。最小限のリソースを消費してできるだけ多くの有用な情報を取得する方法は、すべてのインターネット企業が考慮すべき問題です。アルゴリズムに関する最近の 2 つの記事を通して、読者の皆さんは何らかのアイデアを持っていると思います。もちろん、各アルゴリズムにはそれぞれ長所と短所があり、日常業務での実際の使用状況に基づいてアルゴリズムを選択する必要があり、一般化することはできません。 (王暁東/著者 バオ・ヤン/評論家)