最近、プロジェクトの1つで、問題が発生しました。RAMに効率的に格納する必要があるセットのセット（Set）があります。セットはたくさんありますが、メモリが少ないからです。そして、私たちはそれについて何かをしなければなりません。
これがすべて書かれている言語はC＃、つまりニュアンスなので。つまり、標準のHashSet <int>は1つの数値を格納するために16バイトを費やし、フィルファクターも影響します。より効率的な実装がありますが（いつかそれらについて書きます）、一方で、1つの番号につき4バイト（intを格納する必要があります）の配列に愚かに格納できます。これは非常に効率的です。しかし、それをさらに減らすことはできますか？
特定のデータの分布の特殊性に関連する多くの要因があるため、私はそれを行うための最善の方法についての答えがない、おそらくそれは存在しないとすぐに言わなければなりません。しかし、私が共有するアイデアがあります。メモリを節約するためのオプションはありますか。また、投稿を読む前に自分で考えることをお勧めします。それでも心のウォームアップにはなります。明確にするために、次のように問題を定式化します。
非負の一意のint（32ビット）のセットがあります。セットの作成とすべての要素の取得などの操作から、それらをRAMに効率的に保存する必要があります。インデックスでアイテムを取得したり、新しいアイテムを追加したり、削除したりする必要はありません。
記事には多くの文字と数字が含まれ、1枚の写真は含まれません（KDPVに詰め込まれた猫を除く）。
どのようなプロジェクト、どのようなタスクが具体的であるかを具体的に示すことはしません。一般的に、それは問題ではありません。有効なソリューションはデータに大きく依存します。ある人にとってより適している人もいれば、他の人にとっても、仕事のスピードを忘れない人もいます。どこかでメモリをできるだけ節約する方が良いですが、どこかでバランスを保つ価値があります。
また、私はこの形式の解決策を検討していません。ディスクに保存してホットデータにキャッシュを使用するのはばかげています。これは別のタスクです。
私が遭遇したデータの量を理解するためだけに：それぞれが1つの要素から200万までの数百万のセット。メモリでは約10GBかかります
つまり、基本的なデータがあります。intの配列で、数値ごとに4バイト（32ビット）です。この指標に基づいて構築します。
まず、素晴らしいアイデアを表現します。メモリ内の数値が32ビット未満を占めるためには、より少ないビットを使用して格納する必要があります。かっこいいアイデアですね そして、人々はこれに対して名声と認識を得ます。だから私はもっと悪いです。
叙情的な逸脱：数年前、ロシア鉄道の専門家は、車輪を同じサイズで丸くすると、列車がより速く静かになることを発見しました。
サイズによる数字の区切り
開始する簡単な解決策：0から255までの数値は、数値ごとに1バイトを使用して保存でき、2つで最大65536、3つで最大16777216です。したがって、最初の解決策：
4つの配列を作成します。1つは1バイトで、もう1つは2で、3つ目は3で、4つ目は自分で推測することを提案します。
拍手、そして私たちはすでに保存しています。しかし、なぜあなたがいた場所にとどまるのですか？ 32個のアレイを使いましょう！そして、1、2 ...ビットで番号を格納します。それはさらに経済的になりました。
一方、配列とは何ですか？これは、メモリのブロック（8バイト）、長さ、およびC＃の場合はアレイオブジェクト自体のメモリ（20バイト）へのポインタです。合計で、各配列のコストは32バイトです（実際、C＃では、オブジェクトは8刻みで少なくとも24バイトを必要とし、そのうち20バイトはオブジェクトごとであり、4は残っているものまたは位置合わせに愚かです）。以下、64ビットシステムの計算。 32ビットの場合、ポインターは2分の1になり、配置も4になります。したがって、ほとんどすべてが2倍経済的です。
この一節は何のためにあるのですか？さらに、32個のアレイは1KBのメモリを自分たちだけで消費します。それについてどうしますか？そして、すべてが単純です。これらの32個の配列を1つの配列に格納します。
最初の要素には、1ビット配列の長さ、次に配列自体、次に2ビットの長さなどを格納します。その結果、32バイトのオーバーヘッドと効率的なストレージしかありません。
好奇心旺盛な読者（私はいつもこのフレーズが好きです）は、特定の問題に気付くかもしれません。1ビットの数字を保存するには、最初に長さ（0、1、または2）に2ビットを費やし、次に数字自体に2ビットを費やします。ただし、使用できるのは2ビットのみです。最初のビットは0があるかどうか、2番目のビットは1があるかどうかです。ビットマップを
思いついたところです。この方法を使用すると、0から255までの数値を格納することはあまり心配できません。数値は-1、no-0です。それに32バイトを費やします（1バイトに8ビット* 32 = 256）。当然、新しい値が追加されるたびに、カードの有効性は低下し始めます。それら。すべてのintを格納するには、536870912バイトが必要です...少し多すぎます。したがって、いつ停止するか：256、16、65536-データによって異なります。 256にします。私はこの数字が好きです、それは美しいです。
それら。最初の256個の数値をビットマップで格納し、次に特定の長さの数値の長さをビット単位で格納し、数値自体を格納します。
しかし、何が起こるか見てください。0から511までの数値は、格納するために9ビットを必要とします。同時に、0から255までの番号があります-すでにそれらを保存しています。それら。 9ビットの範囲では12という数字は見つかりません。256以上のみです。それでは、0から255までの数値を格納してから、不足している256を頭に追加できるのであれば、なぜそれらを9ビットで格納するのでしょうか。もう1ビット節約できました。当然、次の各範囲も1ビット経済的です。我々は素晴らしいです！
他に何ができますか？そして、あなたはデータを見ることができます。それらが非常に密集している場合（1,2,3,5,6）、数値自体ではなく、存在しない数値を格納できます（4）。それら。条件付きの5つの数値を格納する代わりに、1つを格納します。単純なルール：半分以上あります-存在しないものを保持します。そうでない場合はその逆です。どこに保管しますか？そして長さ！見てください：10ビット長の数字を保存するには、11ビットが必要です（0から1024まで）。しかし同時に、2048個の値を11ビットに押し込むことができ、1025個しか使用しません。したがって、次の値を格納します：正の長さ-数値を格納します。ネガティブ-そうでないものを保存します。私は、読者自身のために、独立した演習として詳細な計算を行うことを提案します（すべてがうまくいくかどうかわからないため、必要なふりをします）。
その結果、最初の16バイトが0から255までの数字の存在のビットマスクである配列が得られ、次に-指示付きの長さ-数字またはその不在、数字自体、次のビット長などを格納します。
これを実装した後、エラーがなくても、すぐにダークに行くと思います。このコードを理解しようとする後続のプログラマーがあなたをフォローします。それでは、さらにいくつかのオプションを試してみましょう。
秩序について考える
見て。配列があります。多くとは対照的に、彼は何を持っていますか？そして彼は持っています：要素の順序。これは追加情報であり、まだ使用していません。あなたはそれについて何ができますか？
：そして、あなたはない要素そのものが、その差保存することができ
1,2,3,4,8 => 1,1,1,1,4
すなわち。最初の値をそのまま保存し、2番目の値を2番目の値に追加します。それは私たちに何を与えますか？そして、事前に配列をソートすると、その中の値は一般に小さくなり、より少ないビットで格納できるという事実。
さらに、問題の状態に応じて、すべての要素が異なります。差から1を引いて、ビットを節約することもできます
。1,2,3,4,8=> 1,1,1,1,4 => 1,0,0,0,3
これは難しいことではないので、なぜですか。いいえ。
しかし今、問題は解決しました。なぜなら現在、番号を個別に保存することはできませんが、同じ順序でしか保存できないため、配列と長さを使用する方法は適切ではなくなります。何か他のものを考え出す必要があるのですべての番号を順番に保存する必要があります。
番号自体の前に、番号の長さをビット単位で格納し
ます。悪いオプションではありません。数は1〜32ビットです。長さには5ビットが必要で、次に番号自体が必要です。便宜上、極端なケースを切り取ることができます（まあ、なぜそこに保存するのですか？ペニー！）、またはその逆の場合は、別々に強調表示します-たとえば、長さが0の場合、それは数値0を意味し、長さが1の場合、数値-1、長さが2の場合、次の2ビット番号2、3、4、5（シフトできないものにシフトできることはすでにわかっています）など。
または、番号の長さを番号自体に格納できますか？
可変長数量
私たちが最初にこの質問をしたとしても、標準的な解決策があります。UTF-8や他の多くの場所に文字列を格納するために使用されます。意味は簡単です。
数値が0から127までの場合、1バイトに格納します（ただし、7ビットのみを使用しました）。それ以上の場合は、8番目のビットを1に設定し、同じ方法で次のバイトを使用します（7ビット、欠落-チェックボックスと次へ）。それら。小さい数は1バイトに、もう少しは2つに、というように最大5つまで格納されます。次のように
言うことができます。はい、それはクールではありませんが、バイトでの作業はビットでの作業よりも簡単で、節約は少し少なくなりますが、作業の速度は速く、コードはより明確です。しかし...バイトごとにビットを費やすことはどういうわけかあまりクールではありません、多分より良い解決策がありますか？
値をフラグとして使用する
すべての推論をスキップして、すぐに決定しましょう。次のように保存します。
- 0から252までの数字が1バイトに格納されます。それ以上の場合：
- 数値が252から252+ 256 = 508の場合、値252を設定し、次のバイトで数値は252になります（はい、値をシフトする方法はすでにわかっています）
- 252 +256から252+ 256 + 65536の場合、253を設定し、次の2バイトを使用して番号自体を格納します-不要な違い
- 252 + 256 +65536から252+ 256 + 65536 + 16777216の場合、254バイトと3バイトを入力します
- それ以外の場合-255および4バイト。
これは良い方法ですか？すべてが相対的です。1バイトで最大252の値をプッシュできますが、VLQでは最大127ですが、2バイトでは508のみであり、VLQではすでに16383です。あなたの数が十分に密集しているなら、この方法は良いです、そしてここで私たちは勝ちます。しかし、この方法の良いところは、さまざまな範囲に調整できることです。たとえば、ほとんどの数値が10,000〜50,000であることがわかっている場合は、いつでも2バイトで保存できますが、大きな数値が出た場合は、65535を書き込んで、すでに4を使用します。実際、必要な範囲のストレージを最適化して、非効率的なストレージを犠牲にします。不要。
結論
私たちはメモリを節約する主な方法を検討しました（実際、私の想像力は尽きましたが、私はそれを認めません）。これらの手法を組み合わせたり、他のタスクに使用したり、状況に合わせて変更したりできます。最終的に最高のテクニックは何ですか？それはすべてあなたのデータに依存します。それらを取り、それらを試してみてください。幸い、すべてを一度に完全に実装する必要はありません。長さを評価するだけのコードを書くのは簡単です。そして、評価の後、あなたが好きなものをすでに実装します。
この全体の速度を忘れないでください。データの準備や取得に多くの時間を費やす準備ができていますか。ビットで戦いを始める価値はありますか、それともバイトを下回るべきではありませんか。頻繁な状況を最適化するだけで十分であり、まれな状況では効果のない実装が残ります。データに応じて、さまざまな保存方法を使用することは可能ですか（たとえば、サイドコストがすべてのゲインをむさぼり食うため、最大8バイトを配列に保存するのは愚かです。1バイトから-通常、1つの要素の疑似配列に保存します。数）。
また、圧縮について一言：ここではあまり効果的ではありません。圧縮アルゴリズムは繰り返しが非常に好きですが、ここではそれほど多くはありません。 LZ77 + Huffmanで構成される条件付きZipを使用する場合、LZ77で何か便利なものが出てくる可能性は低いですが、Huffmanはバイトを節約しようとする場合があります。したがって、Zipは半分役に立たなくなります。しかし、速度は非常に低下します。
多くのセットがあり、異なるスライスを使用してそれらをすべて一緒に保存できることがわかっている状況は、まだまったく考慮されていません。ここで私は告白します-それがうまくいくかどうかはわかりません。すぐに、私はオプションを思いつきませんでした。しかし、それは難しいだろうと気づきました。ただし、意見が異なる場合があります。
だからコメントであなたのアイデアを共有してください、多分私はさらに多くのバイトを節約し、洗剤広告（一滴で十分です）からの主婦が私たち全員を羨むような結果を得るいくつかの明白な象を逃しました！