検索
ホームページバックエンド開発PHPチュートリアルアルゴリズムに国境はない、国産アルゴリズムも同等に優れている_PHPチュートリアル

[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 つの記事を通して、読者の皆さんは何らかのアイデアを持っていると思います。もちろん、各アルゴリズムにはそれぞれ長所と短所があり、日常業務での実際の使用状況に基づいてアルゴリズムを選択する必要があり、一般化することはできません。 (王暁東/著者 バオ・ヤン/評論家)

www.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/735165.html技術記事 [CSDN レポート] 数日前、CSDN は、外資系企業 AddThis のデータ分析担当副ディレクター、Matt Abrams が公開した高スケーラビリティに関する記事をまとめました。この記事では、Matt Abrams が読者に次のことを紹介しました。
声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
PHP対Python:違いを理解しますPHP対Python:違いを理解しますApr 11, 2025 am 12:15 AM

PHP and Python each have their own advantages, and the choice should be based on project requirements. 1.PHPは、シンプルな構文と高い実行効率を備えたWeb開発に適しています。 2。Pythonは、簡潔な構文とリッチライブラリを備えたデータサイエンスと機械学習に適しています。

PHP:それは死にかけていますか、それとも単に適応していますか?PHP:それは死にかけていますか、それとも単に適応していますか?Apr 11, 2025 am 12:13 AM

PHPは死にかけていませんが、常に適応して進化しています。 1)PHPは、1994年以来、新しいテクノロジーの傾向に適応するために複数のバージョンの反復を受けています。 2)現在、電子商取引、コンテンツ管理システム、その他の分野で広く使用されています。 3)PHP8は、パフォーマンスと近代化を改善するために、JITコンパイラおよびその他の機能を導入します。 4)Opcacheを使用してPSR-12標準に従って、パフォーマンスとコードの品質を最適化します。

PHPの未来:適応と革新PHPの未来:適応と革新Apr 11, 2025 am 12:01 AM

PHPの将来は、新しいテクノロジーの傾向に適応し、革新的な機能を導入することで達成されます。1)クラウドコンピューティング、コンテナ化、マイクロサービスアーキテクチャに適応し、DockerとKubernetesをサポートします。 2)パフォーマンスとデータ処理の効率を改善するために、JITコンパイラと列挙タイプを導入します。 3)パフォーマンスを継続的に最適化し、ベストプラクティスを促進します。

PHPの抽象クラスまたはインターフェイスに対して、いつ特性を使用しますか?PHPの抽象クラスまたはインターフェイスに対して、いつ特性を使用しますか?Apr 10, 2025 am 09:39 AM

PHPでは、特性は方法が必要な状況に適していますが、継承には適していません。 1)特性により、クラスの多重化方法が複数の継承の複雑さを回避できます。 2)特性を使用する場合、メソッドの競合に注意を払う必要があります。メソッドの競合は、代替およびキーワードとして解決できます。 3)パフォーマンスを最適化し、コードメンテナビリティを改善するために、特性の過剰使用を避け、その単一の責任を維持する必要があります。

依存関係噴射コンテナ(DIC)とは何ですか?また、なぜPHPで使用するのですか?依存関係噴射コンテナ(DIC)とは何ですか?また、なぜPHPで使用するのですか?Apr 10, 2025 am 09:38 AM

依存関係噴射コンテナ(DIC)は、PHPプロジェクトで使用するオブジェクト依存関係を管理および提供するツールです。 DICの主な利点には、次のものが含まれます。1。デカップリング、コンポーネントの独立したもの、およびコードの保守とテストが簡単です。 2。柔軟性、依存関係を交換または変更しやすい。 3.テスト可能性、単体テストのために模擬オブジェクトを注入するのに便利です。

通常のPHPアレイと比較して、SPL SPLFIXEDARRAYとそのパフォーマンス特性を説明してください。通常のPHPアレイと比較して、SPL SPLFIXEDARRAYとそのパフォーマンス特性を説明してください。Apr 10, 2025 am 09:37 AM

SplfixedArrayは、PHPの固定サイズの配列であり、高性能と低いメモリの使用が必要なシナリオに適しています。 1)動的調整によって引き起こされるオーバーヘッドを回避するために、作成時にサイズを指定する必要があります。 2)C言語アレイに基づいて、メモリと高速アクセス速度を直接動作させます。 3)大規模なデータ処理とメモリに敏感な環境に適していますが、サイズが固定されているため、注意して使用する必要があります。

PHPは、ファイルを安全に処理する方法をどのように処理しますか?PHPは、ファイルを安全に処理する方法をどのように処理しますか?Apr 10, 2025 am 09:37 AM

PHPは、$ \ _ファイル変数を介してファイルのアップロードを処理します。セキュリティを確保するための方法には次のものが含まれます。1。アップロードエラー、2。ファイルの種類とサイズを確認する、3。ファイル上書きを防ぐ、4。ファイルを永続的なストレージの場所に移動します。

Null Coulescingオペレーター(??)およびNull Coulescing Assignment Operator(?? =)とは何ですか?Null Coulescingオペレーター(??)およびNull Coulescing Assignment Operator(?? =)とは何ですか?Apr 10, 2025 am 09:33 AM

JavaScriptでは、nullcoalescingoperator(??)およびnullcoalescingsignmentoperator(?? =)を使用できます。 1.??最初の非潜水金または非未定されたオペランドを返します。 2.??これらの演算子は、コードロジックを簡素化し、読みやすさとパフォーマンスを向上させます。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。

PhpStorm Mac バージョン

PhpStorm Mac バージョン

最新(2018.2.1)のプロフェッショナル向けPHP統合開発ツール

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

SublimeText3 英語版

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境