草庐IT

c++ - 具有随机数据访问的压缩 vector/数组类

coder 2023-11-13 原文

我想制作“压缩数组”/“压缩 vector ”类(详情如下)，它允许随机数据访问或多或少的常数时间。

“或多或少恒定时间”意味着虽然元素访问时间不是恒定的，但当我接近数组的某个点时它不应该继续增加。 IE。容器不应该做更多的计算(比如“再次解压所有东西以获得最后一个元素”，以及“几乎不做任何事情来获得第一个元素”)来获得一个元素。可以通过将数组拆分为压缩数据 block 来实现。 IE。访问一个元素应该采取 "averageTime"+- 一些偏差。我可以说我希望最好情况下的访问时间和最坏情况下的访问时间相对接近平均访问时间。

我有哪些选择(合适的算法/已经可用的容器 - 如果有的话)？

容器详细信息:

  1. 容器充当相同元素(例如 std::vector)的线性数组
  2. 一旦容器被初始化，数据是不变的，永远不会改变。容器需要提供只读访问权限。
  3. 容器的行为应该像 array/std::vector - 即通过 operator[] 访问的值，有 .size() 等。
  4. 如果我能把它做成模板类就好了。
  5. 对数据的访问应该或多或少是恒定时间的。我不需要对每个元素都使用相同的访问时间，但我不必解压缩所有内容来获取最后一个元素。

使用示例:
对数据进行二分查找。

数据详情:
1. 数据是主要由 float 和一些整数组成的结构。 float 多于整数。没有字符串。
2. 数组中不太可能有很多相同的元素，所以简单地索引数据是不可能的。
3. 一个元素的大小小于100字节。
4. 每个容器的总数据大小在几千字节到几兆字节之间。
5. 数据不是稀疏的——它是连续的元素 block ，所有元素都被赋值，没有“空槽”。

与未压缩的数组形式相比，压缩的目标是减少 block 占用的内存量，同时保持合理的读取访问性能，并允许随机访问数组元素。 IE。数据应该在内部以压缩形式存储，我应该能够像访问 std::vector 或类似容器一样访问它(只读)。

想法/意见？

最佳答案

我认为您需要一个数组，其元素不是原版存储，而是压缩，以最大限度地减少内存使用。

关于压缩，您对数据的结构没有特别的了解，因此您可以使用某种标准的熵编码。理想情况下，希望在整个阵列上运行 GZIP 并完成它，但这会失去 O(1) 访问权限，这对您来说至关重要。

一个解决方案是使用Huffmann coding连同一个索引表。

霍夫曼编码的工作原理是将每个输入符号(例如，ASCII 字节)替换为另一个可变 位长度的符号，具体取决于整个流中出现的频率。例如字符E出现的频率很高，所以它的位序列很短，而'W'很少出现，位序列很长。

E -> 0b10
W -> 0b11110

现在，用这个方法压缩你的整个数组。不幸的是，由于输出符号的长度可变，您无法再像以前那样为数据编制索引:项目编号 15 不再位于 stream[15*sizeof(item)] 中。

幸运的是，这个问题可以通过使用额外的索引表 index 来解决，该表存储每个项目在压缩流中的开始位置。换句话说，第 15 项的压缩数据可以在 stream[index[15]] 中找到；索引表累积可变输出长度。

因此，要获得第 15 项，您只需开始解压缩 stream[index[15]] 中的字节即可。这是可行的，因为霍夫曼编码不会对输出做任何花哨的事情，它只是连接新的代码字，您可以在流内部开始解码，而无需解码所有以前的项目。

当然，索引表增加了一些开销；您可能需要调整粒度，以便 压缩数据 + 索引表 仍然小于 原始数据。

关于c++ - 具有随机数据访问的压缩 vector/数组类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3423968/

ampvectorcode容器的c++algorithmcompression

有关c++ - 具有随机数据访问的压缩 vector/数组类的更多相关文章

  1. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  2. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  3. ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2

    我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..

  4. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  5. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  6. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  7. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  8. ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2

    我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah

  9. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  10. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

随机推荐