在Ruby中高效地存储/压缩整数数组？

我有一个独特的随机整数排序数组，值为1 < = x < = 1,000,000,000。什么是我可以用来将它们存储在数据库中的最节省空间的压缩算法？我想可能是涉及位域的东西..在Ruby中高效地存储/压缩整数数组？

编辑：该数组的大小最多为1,000,000,000。

2013-04-04 Zack Burt

你有十亿个随机整数吗？或者这个数组的大小是多少千兆字节？ – 2013-04-04 03:11:14

像@ctide，我也为这个问题感到困惑。一个大小为N ... a [i] = i的数组中的唯一随机整数的排序数组，范围为1到N，因此您可以使用函数def a（i）;回报我; end'？ – 2013-04-04 08:39:41

你有可能提供更多的数据限制吗？一个从4到10亿完全随机整数的有序数组是相当大的压缩挑战。他们真的是随机的，还是以某种方式受到限制？例如，如果有序数组中的下一个项总是在前一个数的256之内，那么可以只使用一个字节来存储偏移量。。。 – 2013-04-04 11:29:25

使用narray可以有效处理Ruby中的大数值数组。

它更快，并使用更少的内存。 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

。。。如果不需要编写特定的代码，这将非常高效。

如果这些数字是完全随机的，那么压缩可以实现的功能是有限制的。真正的随机数据几乎是不可压缩的。

如果你有一个很好的数字排列约束模型，那么你可以使用它的知识来创建一个更好的压缩比。建议使用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-04 09:55:19

不错！但是你的例子假设一个非稀疏数组。 NArray不支持稀疏数组，因此需要很大的空间来存储一个两个元素数组，其索引为1和900,000,000。 – Fred 2013-04-04 13:03:23

OP没有要求稀疏阵列AFAICT。事实上，考虑到数组是排序的，对我来说似乎不太可能。然而，它还没有100％清楚要求什么。 – 2013-04-04 15:02:08

是的。这听起来像是你为了让他们认识到每个解决方案都有折衷而抛出的问题之一。每次提出提案时，老师都会添加一个条件来解决问题。它可以很有趣！ – Fred 2013-04-04 15:19:40

你没有提到你的数据集的大小。数据如何随机访问？用位域压缩它可能会奏效，但是你会失去解压数据的时间，更不用说Ruby不如C处理这些数据那么高效了。除非空间是主要关心我只是将它作为数据库存储在一个单一整数字段的表中。

来源

2013-04-04 02:13:11

更新尺寸。随机访问不是必需的。 – 2013-04-04 02:28:03

如果它们被排序，并且有10亿个项目，范围在1到10亿之间，这是不是意味着它只有1亿美元？为什么要存储它？ – ctide 2013-04-04 02:31:18

@ctide：也许他们不是唯一的？ – angelatlarge 2013-04-04 03:07:23

1..1,000,000,000可以保持在32位整数中。如果数组稀疏，则合理的编码是将每个有效元素表示为2个32位整数，其中一个是元素值，另一个是元素索引。对于数组中的每个有效元素，您需要64位/ 2个整数，再加上32位/一个整数来存储阵列中有效元素的数量。

来源

2013-04-04 02:57:04 Fred

+1简单的方法备件，虽然OP似乎想要允许一个非常大范围的可能性。 – 2013-04-04 10:23:01

你有1e9随机唯一整数范围1..1e9，按排序顺序。这意味着您只有一个范围内的每个整数。这里的红宝石你最好的压缩：

商店这样的：

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

然后读回和eval它。

来源

2013-04-04 03:41:07 dbenhur

该数组* *最多* 10亿个大小。 – 2013-04-04 06:32:48

@ZacharyBurt编辑历史显示_at most_在我的翻转答案后三个小时添加。事实是，这是一个可怕的提出的问题，有太多模糊的规范和限制，并没有暗示任何目的。弄清楚如何说出你真正的问题是什么，然后再试一次。 – dbenhur 2013-04-04 15:28:18

在Ruby中高效地存储/压缩整数数组？

回答

相关问题