标签: space-efficiency

C中两个函数有什么区别？

void f1(double a[]) {
   //...
}

void f2(double *a) {
   //...
}

如果我要在一个相当长的数组上调用这些函数,这两个函数的行为会不同,它们会占用更多的空间吗？

所以Quicksort的空间效率是O(log(n)).这是维护调用堆栈所需的空间.

现在,根据Quicksort上的维基百科页面,这可以作为就地算法,因为算法只是交换输入数据结构中的元素.

然而,根据这个页面,空间效率O(log n)使Quicksort不合格,因为它的空间效率大于O(1).根据该定义,任何空间效率大于O(1)的算法都不是就地的.所以我认为这意味着根据定义,所有递归算法都没有到位？

显然,这里有两种不同的就地定义.维基百科并不总是一个完全可靠的来源,所以我咨询了我的一位教授.

我的教授同意第二个定义.他说Quicksort不到位.即使数据保留在输入数组中,堆栈所需的额外空间也会使其失去资格.我的教授写了一本关于算法的畅销书,所以我非常尊重他的观点,但这个答案对我来说似乎不正确.

我认为就地的属性非常直观.数据保持不变.它不会从它的原始数据结构中移动.对我来说,这个定义更有用,因为它意味着您可以使用指针执行算法,而不是要求您复制数据.这似乎是算法的一个有价值的属性,并且名副其实"就地".

假设您有一个,List<List<Boolean>>并且您希望以最紧凑的方式将其编码为二进制形式.

我不关心读写性能.我只是想使用最小的空间.此外,该示例在Java中,但我们不限于Java系统.每个"列表"的长度是无限的.因此,编码每个列表长度的任何解决方案本身必须编码可变长度数据类型.

与此问题相关的是可变长度整数的编码.您可以将每个List<Boolean>视为可变长度unsigned integer.

请仔细阅读问题.我们不仅限于Java系统.

编辑

我不明白为什么很多答案都谈论压缩.我本身并不是在尝试压缩,而只是编码随机的位序列.除了每个比特序列具有不同的长度并且需要保留顺序.

你可以用不同的方式思考这个问题.假设您有一个随机无符号整数列表(无界).如何在二进制文件中编码此列表？

研究

我做了一些阅读,发现我真正想要的是通用代码

结果

我将使用本文中描述的Elias Omega Coding的变体一个新的正整数的递归通用代码

我现在明白,较小整数的表示越小,整数就越大.通过简单地选择具有第一个整数的"大"表示的通用代码,当您需要对任意大整数进行编码时,从长远来看可以节省大量空间.

pickle模块似乎在酸洗时使用字符串转义字符; 这在numpy数组上变得低效.考虑以下

z = numpy.zeros(1000, numpy.uint8)
len(z.dumps())
len(cPickle.dumps(z.dumps()))

长度分别为1133个字符和4249个字符.

z.dumps()显示类似"\ x00\x00"(字符串中的实际零),但pickle似乎使用字符串的repr()函数,产生"'\ x00\x00'"(零为ascii零).

ie(z.dumps()中的"0"== False)和(cPickle.dumps中的"0"(z.dumps())== True)

我想将一个C#数组的子集传递给一个方法.我不在乎该方法是否覆盖数据,因此希望避免创建副本.

有没有办法做到这一点？

谢谢.

人们发现所有算法都具有惊人的(艰难的,奇怪的)复杂性分析 - 结果O符号和分析方式的唯一性？

我正在开发一个开源备份实用程序,它可以备份文件并通过FTP/SFTP/SCP协议将它们传输到各种外部位置,如Amazon S3,Rackspace Cloud Files,Dropbox和远程服务器.

现在,我收到了进行增量备份的功能请求(如果所做的备份很大并且转移和存储成本很高).我一直在环顾四周,有人提到了这个rsync实用程序.我对此进行了一些测试,但我不确定这是否合适,所以希望听到任何有经验的人rsync.

让我简要介绍一下备份时会发生什么.基本上它会开始转储MySQL,PostgreSQL,MongoDB,Redis等数据库.它可能需要文件系统中的一些常规文件(如图像).一旦一切就绪,它将把它们全部捆绑在一个.tar中(另外它将使用gzip和压缩和加密openssl).

完成所有操作后,我们会看到一个如下所示的文件:
mybackup.tar.gz.enc

现在我想将此文件传输到远程位置.目标是降低带宽和存储成本.因此,我们假设这个小备份包1GB大小不一.因此我们使用它将rsync其传输到远程位置并在本地删除文件备份.明天会生成一个新的备份文件,结果是在过去24小时内添加了更多的数据,我们构建了一个新mybackup.tar.gz.enc文件,看起来我们的1.2GB规模已经达到了.

现在,我的问题是:是否可以仅转移200MB过去24小时内添加的内容？我尝试了以下命令:

rsync -vhP --append mybackup.tar.gz.enc backups/mybackup.tar.gz.enc

结果:

mybackup.tar.gz.enc 1.20G 100%36.69MB/s 0:00:46(xfer#1,to-check = 0/1)

发送200.01M字节
接收849.40K字节
8.14M字节/秒
总大小为1.20G
加速为2.01

看看sent 200.01M bytes我会说数据的"附加"工作正常.我现在想知道的是它是否转移了整体1.2GB以便计算出现有备份的附加量和附加量,还是真的只转移了200MB？因为如果它转移了整体,1.2GB那么我看不出它与scp在单个大文件上使用该实用程序有多大不同.

另外,如果我想要完成的是什么,你建议用什么标志？如果不可能rsync,您可以建议使用任何实用程序吗？

任何反馈都非常感谢!

我需要为大量8位值创建一个节省空间的2D数组.我开始使用几层抽象和泛型来编写我的类,以允许代码重用.一旦我开始实现具体类,它就发生在我身上,我不能将原始类型作为泛型类参数传递,我将不得不使用包装类.因为我担心空间效率,我需要知道:使用包装类的 Byte 数组与原始 byte 数组之间的空间效率差异是什么？

我有创建和使用集合的代码，例如：

List<Map<String, Object>> tableData;

该映射列表由n 个映射填充，每个映射代表数据库中的一行。每行都表示为字段名称和与该字段对应的对象之间的映射（在这种情况下类型不相关）。某些字段可能会丢失。字段数m始终远小于行数 ( n ≈ 10000 × m )。我需要多次重复使用同一个集合来读取所有行，所以我不能只使用某种惰性迭代器。

是否有一个有效的数据结构来存储它？Guava 提供了一个Table集合，但似乎不符合要求。我正在考虑创建一个界面，例如：

interface TableData{
  int size();
  Map<String, Object> get(int i);
  // ... (interators, etc.)
}

然后创建一个使用一个的实现Map<String,List<Object>>，以便我只实例化m个列表而不是n 个映射，并且仅在需要时动态创建映射，但我想知道是否有更通用的数据结构。

谢谢

我一直在研究最佳实践是对尝试在网站上注册的用户进行电子邮件验证。（我正在运行 laravel 安装，这发生在 php 中，尽管这更多是一个理论问题）。我有几个问题想请教大家意见！

1. 将激活密钥存储的时间比需要的时间长还有什么用吗？截至目前，我已将其设置为在用户激活他/她的帐户后删除密钥。
2. 当我从表中清除数据并激活后，空间是否会被取消分配？或者它只是被清空了？
3. 有没有更好的方法来完成这个过程？（我有一个模糊的想法，使用一个临时“令牌”表，其中密钥和电子邮件 ID 作为列，每次注册时都会添加一个新行，然后在用户确认后将其删除（或者在特定超时后）时期）
4. 理想情况下，生成的密钥的大小应该是多少？一个简单的 5 位字母数字代码可以容纳超过 6000 万种组合，那么是否真的需要对其进行哈希处理呢？

我已经研究这个问题有一段时间了，我的目标是使我的系统完美可扩展并且尽可能高效。欢迎任何信息/讨论。