问题标签 [programming-pearls]

我们可以通过将可用节点的集合保存在自己的结构中来避免对存储分配器的多次调用。

这个思想可以应用于二叉搜索树数据结构。

作者说：“一次分配所有节点可以大大减少树的空间需求，从而减少大约三分之一的运行时间。 ”

我很好奇这个技巧如何减少空间需求。我的意思是如果我们要构建一个有四个节点的二叉搜索树，我们需要为这四个节点分配内存，无论我们是一个一个分配节点还是一次性分配所有节点。

在“Programming Pearls”：Strings of Pearls，第 15.3 节（生成文本）中，作者介绍了如何从输入文档中生成随机文本。在源代码中，有一些我不明白的东西。

作者解释说：“在读取输入后，我们附加了 k 个空字符（因此比较函数不会跑到最后）。” 这个解释真的让我很困惑，因为在评论这两行之后它仍然很好用。为什么这是必要的？

来自编程珍珠的第 15.2 节

C代码可以在这里查看：http ://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

当我使用后缀数组在 Python 中实现它时：

我发现这idx.sort一步很慢。我认为这很慢，因为 Python 需要按值而不是按指针传递子字符串（如上面的 C 代码）。

测试文件可以从这里下载

C 代码只需 0.3 秒即可完成。

但是对于 Python 代码，它永远不会在我的计算机上结束（我等了 10 分钟并杀死了它）

有谁知道如何使代码高效？（例如，少于 10 秒）

我最近偶然发现了一个充其量似乎是一个错误的情况。在比较中使用时，两者null和false似乎都被评估为较低但不等于负无穷大。

我目前的测试用例：

这是在各种PHP 版本和我可以访问的一些 Windows 机器上运行的。所有人都有惊人的相同结果。

忽略前两个调试转储，如果您是一位经验丰富的 PHP 开发人员，接下来的 6 个结果是您所期望的。前两个是由于类型杂耍，后四个是由于PHP和math。

现在最后四个是困扰我的地方。

我不确定低于负无穷大的东西在数学中是否有效。

更奇怪的是前两个和后两个比较的组合。不知何故，相同类型的杂耍算法使其有效：

如果有人可以就这些类型转换如何以如此不同的方式进行评估以及为什么将不胜感激提供任何见解。

PS我一次又一次地尝试搜索SO ，PHP手册甚至PHP错误跟踪器，都无济于事。我尝试查看 C 源代码以确定使该代码以它的方式工作的点点滴滴。还是没有骰子。

实际上是 Programming Pearls 第 2 版第 8 章的第 10 题。它提出了两个问题：给定一个整数数组 A[]（正数和非正数），如何找到 A[] 的和最接近 0 的连续子数组？还是最接近某个值 t？

我可以想办法解决最接近0的问题。计算前缀和数组S[]，其中S[i] = A[0]+A[1]+...+A[i]。然后根据元素值对这个 S 进行排序，连同它保留的原始索引信息，找到最接近 0 的子数组和，只需迭代 S 数组并做两个相邻值的 diff 并更新最小绝对 diff。

问题是，解决第二个问题的最佳方法是什么？最接近某个值 t？任何人都可以给出代码或至少一个算法吗？（如果有人对最接近于零的问题有更好的解决方案，也欢迎回答）

这些列包括两个关键特征，一列要总结，以及其他一些（例如，1）不重要的列。

我想用相同的 key1 和 key2 添加 sum 列，并输出一个 3 列的 csv 文件。

在上述情况下，它是

（注479=23+456：）

使用 Perl 或 Shell 命令都可以。

我正在开始一个项目，该项目需要组装文件并将它们链接到 pdf 目录中的大约 140 行（每行一个文件）。问题是我必须这样做 80 次，每次手动执行似乎非常乏味。

TOC 已经存在，我希望每个行项目都链接到相应的 pdf。（链接已经存在，只是该位置尚不存在pdf）。pdf 已经存在于其他地方并且具有可预测的文件路径（随项目编号而变化）。

如果我有一个与每个行项目及其对应路径相对应的文件列表，是否可以编写一个脚本将文件复制到其原始位置并将副本放置在新位置？（如果是这样，如何使用，最好的语言是什么？）

谢谢！

问题：输入在顺序文件上。该文件最多包含 40 亿个整数。找到一个缺失的整数。

根据我的理解解决方案：

1. 制作两个临时文件，一个以 0 开头，另一个以 1 开头

2. 两个必须（4.3B 鸽洞和 4B 鸽子）中的一个小于 2B。选择文件并在第 2 位重复步骤 1 和 2，然后在第 3 位重复步骤，依此类推..

这个迭代的结束条件是什么？

此外，这本书提到算法的效率是 O(n) 但是，

第一次迭代 => n 次探测操作
第二次迭代 => n/2 次探测操作
。
.
.
n + n/2 + n/4 +... 1 => nlogn??

我错过了什么吗？

我正在尝试在 Pearl 中创建一个压缩文件，该文件可以在使用 zlib 的 iPad 应用程序中使用和压缩。Pearl 中的当前 zip 模块（即 IO::Compress::Zip ）似乎输出了不正确的数据以供 zlib 理解。我在 C 端使用 z_stream strm 来放气。我在应用程序中使用 inflate 时注意到的一点是，输出看起来像十六进制文本。在珍珠方面，它是非文本的。

这是来自编程珍珠版。2，第 2 栏，第 8 题：

给定一组 n 个实数、一个实数 t 和一个整数 k，你能多快确定该集合中是否存在一个总和为 t 的 k 元素子集？

一个简单的解决方案是对前 k 个元素进行排序和求和，这是我们找到这样一个和的最大希望。然而，在解决方案部分，Bentley 提到了一个需要 nlog(k) 时间的解决方案，尽管他没有给出如何找到它的提示。我一直在为此苦苦挣扎；我的一个想法是遍历列表并添加小于 t/k 的所有元素（在 O(n) 时间内）；假设有 m1 < k 这样的元素，它们的总和为 s1 < t。然后我们需要 k - m1 个元素，因此我们可以在 O(n) 时间内再次扫描列表，查找小于 (t - s1)/(k - m1) 的所有元素。再次添加，得到 s2 和 m2，然后如果 m2 < k，则再次查找小于 (t - s2)/(k - m2) 的所有元素。所以：

我的直觉是这可能是 O(nlog(k)) 算法，但我很难向自己证明。想法？