1

値が 1<=x<=1,000,000,000 の一意のランダム整数の並べ替えられた配列があります。それらをデータベースに格納するために使用できる最もスペース効率の良い圧縮アルゴリズムは何ですか? 私はおそらくビットフィールドを含む何かを考えています..

編集: 配列のサイズは最大で 1,000,000,000 です。

4

4 に答える 4

3

narrayRuby で大きな数値配列を効率的に処理するために使用します。

より高速で、メモリ使用量が少なくなります。http://narray.rubyforge.org/

DBストレージ部分について。マーシャリングを追加することができnarrayます (デフォルトではマーシャリングはありません):

# This adds support for Marshal to NArray - found it at: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/194510
class NArray
  def _dump *ignored
    Marshal.dump :typecode => typecode, :shape => shape, :data => to_s
  end
  def self._load buf
    h = Marshal.load buf
    typecode = h[:typecode]
    shape = h[:shape]
    data = h[:data]
    to_na data, typecode, *shape
  end
end

. . . これは、特定のコードを記述する必要がなく、非常に効率的です。

数値が完全にランダムな場合、圧縮で達成できることには限界があります。真にランダムなデータはほとんど圧縮できません。

数値の配置方法に関する優れた制約モデルがある場合は、その知識を使用して、より優れた圧縮率を作成できます。a の使用を提案する投稿Rangeはその極端な例ですが、もちろん非常に単純な構造の場合にのみ機能します。

構造が多かれ少なかれ恣意的である場合は、データをマーシャリングして、 のような既製の圧縮アルゴリズムを適用しますzlib。

編集：アイテムがソートされているという事実は、より良い圧縮に役立ちます。また、ボックスにチェックを入れますnarray-Rubyで手動で行うよりも速く数字をソートしますArray

サンプルコード:

require 'narray'
require 'zlib'

# Ten thousand integers . . .
n = NArray.int(10000).random(100000).sort

# Compressed . . .
stored = Zlib::Deflate.deflate( Marshal.dump(n), 9 )

stored.length

 => 14297

数値あたり 1.5 バイトです (実際の圧縮率は大きく異なりますが、通常、この手法を使用すると数値あたり 4 バイト未満になります)。

于 2013-04-04T09:55:19.253 に答える
1

1..1,000,000,000 は 32 ビット整数で保持できます。配列がまばらな場合、合理的なエンコーディングは、有効な各要素を 2 つの 32 ビット整数として表すことです。1 つは要素値で、もう 1 つは要素インデックスです。配列内の有効な要素ごとに 64 ビット / 2 整数に加えて、配列内の有効な要素の数を格納するために 32 ビット / 1 つの整数が必要です。

于 2013-04-04T02:57:04.550 に答える
1

1..1e9 の範囲に 1e9 のランダムな一意の整数があり、並べ替えられています。つまり、範囲内の各整数が 1 つだけあるということです。Ruby を使用した最適な圧縮は次のとおりです。

これを保存します：

"(1..10**9).to_a"

それからそれを読み返しますeval。

于 2013-04-04T03:41:07.690 に答える