データをビット列に押し込む

概要

データをビット列に押し込めることで、データサイズを小さくする事ができる

問題

データ数: 最大 10^7 （10,000,000）
データ: 10^7 より小さい整数 （0 〜 9,999,999）

問題の特徴

• 入力の範囲が限られている
• 同じ整数は出現しない
• 考える対象は整数のデータのみ

解決案

1. 一つのデータ（7桁の整数）を7バイトで表す
2. 一つのデータ（7桁の整数）を32bitで表す
3. ビット列で表す（各データを1bitにする）

   一つのデータサイズ| 全データサイズ
1.  7byte * 8 = 56bit| 56 * 10,000,000 = 560,000,000bit 
2.              32bit| 32 * 10,000,000 = 320,000,000bit 
3.               1bit|  1 * 10,000,000 =  10,000,000bit 

結論

案3.のビット列にする事で、全データを 10,000,000 ビットで表すことができる
上記案の 1/56、1/32にデータサイズを小さくすることが可能

ビット列で表すのに有効となるデータセットの条件

• 限られた範囲内にある
• 密
• 重複がなく、付随する情報がない

ビット列の例

データ

行番| data   
   1| 0000001
   2| 0000003
   3| 0000002
   4| 0000004
...

bit列

行番| データ | データのbit表記|| [bit列]
   1| 0000001| 0000010        || 0000010
   2| 0000003| 0001000        || 0001010
   3| 0000002| 0000100        || 0001110
   4| 0000004| 0010000        || 0011110
...

実装

参考書籍

珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造
https://amzn.to/3N5mMTI