一番下の行は次のとおりです。
- データの量が開発の複雑さに重大な影響を与えてはなりません。 原則として、開発の主な複雑さは、量ではなくデータ処理アルゴリズムの複雑さに関連しています。 データの実際の量を事前に知っていれば、小さなデータで動作するコードを開発するだけで十分で、必要な量に適用できます。
- すべての主要な計算アルゴリズムは長い間知られています（少なくとも現在は数十年）。 主なことは、できるだけ早く（開発開始前）、タスクへの正しいアプローチを決定することです。 しかし、これは労働集約度の問題ではなく、専門的な適合性です。つまり、機器は事前に調査し、迅速に開発する必要があります。
- 数百行のコード開発の複雑さが長い時間を要した理由を理解している顧客は一人もいません。 顧客は、誰かの学習プロセスや理解できない実験に時間とお金を費やすよりも、チームを変える方が簡単です。
- もちろん、データ量に関連する小さなオーバーヘッドが発生する可能性があります。 ただし、これらのコストは、原則として、労働投入量の初期（正しい）推定値の誤差を超えず、個別に考慮することは意味がありません。
開発者にとっては、率直に言って、結論はあまりおかしくなく明確ではありませんでした。
しかし、議論はゼロからではなく、単純な計算アルゴリズムを使用した問題の議論の一部として、しかし大量のデータを使用して行われました。
この出版物の目的は、妥当な時間内に、それぞれ10億エントリの2つのリンクリストを処理する方法に関する経験を共有することです。
問題の声明
この出版物に示されているデータは、元の問題のデータと似ています。 変更は主に適用される用語に影響しました。 「蟻塚の会計」と呼びましょう。
明確にするために、プロセスは次のとおりです。
ある素晴らしい森で、彼らは動物を数えることにしました。 これを行うために、彼らはすべての動物が記録された単純な会計システムを作成しました。 システムが作成され、動物に番号が割り当てられ、その番号にはミンク、隠れ家、巣も与えられました。 要するに、すべてが簡単かつ迅速に判明しました。
彼らは蟻塚でこれについて学び、また独自の会計システムを開発することを決めました。 動物の会計システムに基づいています。
その結果、各アリは名前番号と家の住居番号を受け取りました。 各アリには、労働者、兵士などのタイプが割り当てられました...家は、蟻塚エリアに分布していました：中央、上部、下部、...
登録が完了し、アリ会議で全員が作業の完了を喜んで祝った後、主要なアリの兵士が床に着きました。 彼は（もちろん、あらゆる種類のフェロモンを広めることを言った-それは蟻にとってより理解しやすい）彼は会計が好きだ、これは必要かつ有用なことだ、そして今、彼は蟻塚のこの部分に住んでいる蟻-兵士のリストを蟻塚のすべての部分に送る必要がある このような場合には慣習的であるように、これは緊急かつ緊急に行われなければなりません。
ここで、他のアリの代表者は大騒ぎし始めました-彼らはまた、あらゆる種類のワームバグの分布と他の同様に重要なイベントのためのリストを必要としました。
そしてアリがいた-10億。
彼らは蟻塚でこれについて学び、また独自の会計システムを開発することを決めました。 動物の会計システムに基づいています。
その結果、各アリは名前番号と家の住居番号を受け取りました。 各アリには、労働者、兵士などのタイプが割り当てられました...家は、蟻塚エリアに分布していました：中央、上部、下部、...
登録が完了し、アリ会議で全員が作業の完了を喜んで祝った後、主要なアリの兵士が床に着きました。 彼は（もちろん、あらゆる種類のフェロモンを広めることを言った-それは蟻にとってより理解しやすい）彼は会計が好きだ、これは必要かつ有用なことだ、そして今、彼は蟻塚のこの部分に住んでいる蟻-兵士のリストを蟻塚のすべての部分に送る必要がある このような場合には慣習的であるように、これは緊急かつ緊急に行われなければなりません。
ここで、他のアリの代表者は大騒ぎし始めました-彼らはまた、あらゆる種類のワームバグの分布と他の同様に重要なイベントのためのリストを必要としました。
そしてアリがいた-10億。
データ構造を図に示します。
- ant_type-アリの種類（1-女王、2-幼虫、3-乳母、4-労働者、5-兵士）
- hill_type-ant hill area（1-中央、2-上部、3-下部、4-北、5-南、6-東、7-西）
- ant_list-アリのリスト（10億エントリ）
- cell_list-家のリスト（10億レコード）
- ant_to_cell-どのアリがどの家に住んでいるか（10億レコード）
タスクは、各蟻塚地域（hill_type）に、そこに住むアリのリスト（ant_list）、特定のタイプ（ant_type）、およびその家番号（cell_list）を準備することです。
試験データ
気にする人は、テストデータを生成するためのユーティリティがあります。 このユーティリティは、C＃（Visual Studio Community 2013）で記述されたコンソールプログラムとして準備されました。
ユーティリティコードはGitHubのanthill-makedata.csファイルに投稿されています 。 Visual Studioで動作するプログラムを取得するには、コンソールプロジェクトを作成し、program.csファイルをanthill-makedata.csに置き換えてプロジェクトをビルドする必要があります。 このアプローチは、コンパクトさ、可視性、流通の安全性の観点から選択されました。
デフォルトでは（パラメータなし）、ユーティリティは1000レコードごとに一連のテストデータ（CSV形式の5ファイル）を準備します。 パラメーターとして、1,000から10億までの目的のデータサイズを指定できます。
anthill-makedata.exe 1000000000
10億件のレコードでテストデータを準備するには、最大30分、約50ギガバイトのディスクスペースが必要です。 ログ（anthill-makedata.log）でランタイムを確認できます。
FARを使用してデータを表示できます。
解決策
ここで、誰が興味を持っているか、あなたは考えるかもしれません-彼らはどのようにこの問題を解決し始めるでしょうか。
開発プロセス中に、最初の呼び出しまたは2番目の呼び出しから許容可能な速度に到達できなかったため、資材では「それほど多くない」ことがわかりました。 完全なデータの処理は、非常に遅くなりました。 この理由は、小さなデータに対して迅速に実行された検索手順でしたが、データが増加するにつれて、すべてが下品になりました。
最終的に、解決策が見つかりました。 さらに、完全なデータで作業するには、それほど強力ではないコンピューターのフードの下でさえ十分でした：CPU-コア5i、RAM-12Gb（8、4を追加）、HDD-最も簡単（5400 rev）。
ソリューションの本質は、通常のインデックス配列を使用することです。 リストごとに10億の配列が作成されます。 配列内のセル番号-オブジェクト（ant、house）の番号に対応します。 蟻の識別子タイプと蟻塚の部分のタイプは、それぞれ配列のセルに配置されます。 蟻と家の配列が満たされた後（テストデータ— anthill-ant-list.csvおよびanthill-cell-list.csvファイルから）、anthill-ant-to-cell.csv通信ファイルが「プル」され、ファイルが同時に書き込まれます（ CSV）と結果。
検索に時間がかからないため、インデックスによる配列セルへのアクセスは即座に行われます。 この場合、大部分の時間はファイルの読み取りと書き込み（HDDでの作業）です。
ソリューションは、C＃（Visual Studio Community 2013）で記述されたコンソールプログラムとして準備されました。
プログラムコードはGitHubのanthill-makeresult.csファイルに投稿されています 。 Visual Studioで作業プログラムを取得するには、コンソールプロジェクトを作成し、program.csファイルをanthill-makeresult.csに置き換えてプロジェクトをアセンブルする必要があります（注：プロジェクトプロパティの[ビルド]セクションで、[32ビットを優先]をオフにします）。 テストデータファイルがある同じディレクトリでプログラムを実行します。
デフォルトでは（パラメーターなし）、プログラムは兵士アリのリスト（CSVファイル）を準備します。 パラメーターとして、目的のタイプを指定できます。
anthill-makeresult.exe 4（4-コードタイプ「working」）
完全なデータに基づく結果の準備には最大30分かかります。 テストデータに基づいて、約100ギガバイトのディスク領域が必要です。
簡単な要約
考慮された問題については、データの量が開発の複雑さに大きく影響しないという主張は真実であることが判明しました。
- ターンキーソリューションはシンプルで、エラー処理、ロギング、コメントを含む300行のコードに収まることがわかりました。
- このソリューションは、小さいデータと大きいデータ（指定されたサイズまで）の両方で同じように機能します。
- メインブレーキはデータ処理ではなく、I / O操作（低速のHDD操作）です。
マイナスのうち、注意することができます：
- このアプローチは普遍的ではありません。 たとえば、異なる構造または異なるアプリケーションデータ形式は、ソリューションに大きな影響を与える可能性があります。
- CSVファイルの操作は常に便利なわけではなく、エラーから保護されておらず、データの整合性を保証するものでもありません。