小编dsi*_*cha的帖子

我有一个与子集求和问题有关的问题,我想知道差异是否更容易,即在合理的时间内可解决.

给定一个值V,一个集合大小L和一个数字序列[1,N] S,S总和的多少个L子集总和小于V？

这与子集求和问题有三种不同:

1. 我关心有多少子集小于给定值,而不是有多少子集相等.
2. 子集大小是固定的.
3. 我关心有多少集合总和小于V,而不仅仅是否存在.

有没有合理有效的算法来解决这个问题？

编辑:显然,这可以使用组合生成算法在O(N选择L)中完成.我真正感兴趣的是聪明的黑客,以显着加快它的速度.

我明白了使一类的各个方法的动机sealed/ final,但什么用途从类全面禁止继承服务？虽然允许覆盖某些方法可能导致不良事件发生,但我无法看到如何允许从类中继承纯粹为了在不覆盖现有行为的情况下向其添加行为可能是一件坏事.如果你真的想要禁止在你的类中覆盖任何东西,为什么不只是让每个方法都最终但仍允许继承以增加行为？

XML发明要解决什么问题？据我所知,似乎它为可能具有截然不同的语义的事物指定了统一的语法.例如,与HTML文件,Java源文件或.docx文档不同,人们无法编写程序以从XML文件中提取任何类型的高级含义而无需额外的信息.即使语义意义完全未指定,某些标准委员会严格指定语法的价值是什么？XML只有滚动您自己的ad-hoc格式才能完全满足您的需求,仅此而已？简而言之,XML可以实现什么？为什么它如此广泛使用？

我正在尝试为D编程语言调试我的并行库.最近提交了一个错误报告,指出使用任务执行的某些浮点运算的低位比特在运行期间是不确定的.(如果您阅读报告,请注意并行缩减通过以确定的方式创建任务而在幕后工作.)

这似乎不是舍入模式问题,因为我尝试手动设置舍入模式.我也很确定这不是一个并发错误.该库是经过严格测试(包括传递金克斯压力测试),这个问题始终限制在低位,这甚至发生在单核的机器,其中低级别的内存模型问题是一个问题较少.浮点结果可能因调度操作的线程而异的原因还有哪些？

编辑:我在这里做一些printf调试,看起来各个任务的结果有时会在运行中有所不同.

编辑#2:以下代码以更简单的方式再现此问题.它总结了主线程中数组的术语,然后启动一个新线程来执行完全相同的函数.问题绝对不是我的库中的错误,因为这段代码甚至不使用我的库.

import std.algorithm, core.thread, std.stdio, core.stdc.fenv;

real sumRange(const(real)[] range) {
    writeln("Rounding mode:  ", fegetround);  // 0 from both threads.
    return reduce!"a + b"(range);
}

void main() {
    immutable n = 1_000_000;
    immutable delta = 1.0 / n;

    auto terms = new real[1_000_000];
    foreach(i, ref term; terms) {
        immutable x = ( i - 0.5 ) * delta;
        term = delta / ( 1.0 + x * x ) * 1;
    } …

在当前函数退出之前,是否可以显式释放由C的alloca()分配的内存？如果是这样,怎么样？

我现在的主要语言是D,我正在学习Python,因为这是我正在学习的课程所必需的.虽然我理解为什么动态语言会让人们在没有类型推断或模板的情况下使用静态语言进行编程(IMHO模板在很大程度上是编译时的鸭子打字),但我很好奇动态语言的好处是什么即使你有那些.

最重要的是,如果我要学习Python,我想以一种真正改变我对编程思路的方式来学习它,而不仅仅是在Python中编写D.我没有使用动态语言,因为我是一个相当新手的程序员,无法欣赏他们所提供的灵活性,并希望学会现在充分利用它们.在静态语言中,即使使用模板,多态,静态类型推断以及可能的运行时反射,在动态类型化的解释语言中,可以轻松/优雅地完成哪些操作？

我希望在性能关键代码中多次计算熵和互信息.作为中间步骤,我需要计算每个值的出现次数.例如:

uint[] myArray = [1,1,2,1,4,5,2];
uint[] occurrences = countOccurrences(myArray);
// Occurrences == [3, 2, 1, 1] or some permutation of that.
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5.

当然,显而易见的方法是使用关联数组或使用"标准"排序算法(如快速排序)对输入数组进行排序.对于小整数,如字节,代码目前专门用于使用普通的旧数组.

是否有任何聪明的算法比哈希表或"标准"排序算法更有效地做到这一点,例如一个非常有利于插入更新的关联数组实现,或者当你的数据有很多关系时会发光的排序算法？

注意:非稀疏整数只是可能数据类型的一个示例.我想在这里实现一个合理的通用解决方案,但由于只包含整数的整数和结构是常见的情况,如果它们非常有效,我会对这些特定的解决方案感兴趣.

从历史上看,为什么它似乎只是关于每个人和他们的孩子兄弟定义他们自己的呼叫惯例？你有C,C++,Windows,Pascal,Fortran,Fastcall以及其他可能没有提及的其他人.对于绝大多数用例,一项公约不应该是最有效的吗？是否有任何理由更喜欢一个而不是另一个？

我需要一个适用于Windows和Linux的良好的分析器(它们不必是相同的;对每个操作系统的单独建议都很好)可以附加到一个已经运行的进程,该进程没有以任何"特殊"方式编译并给出我什么功能的过程中花费了大量的时间,我有一些长期运行的科学代码,我想在那里的花费大部分时间在执行的各个阶段的快照,统计,并能够获得满意的结果,而不必须运行整个程序开始完成.

我正在使用的编译器(Digital Mars D)带有一个仪器分析器.这对我正在运营的工作来说太慢了.由于我只对识别主要瓶颈感兴趣,因此我想要快速且易于使用的东西,即使它只是大致准确.理想情况下,它还应该能够同时分析所有线程并给我一个汇总报告.

在Linux上,我一直在使用GDB作为穷人的采样分析器(暂停我的应用程序几次并查看它的功能).基本上,我正在寻找一个更自动化的版本.

最后一个要求:在Linux上,它必须易于安装而没有root权限,因为我将在我没有root权限的服务器上运行它.

编辑:虽然代码是用D编写的,D的编译模型等与C类似,但为C编写的工具应该可以正常工作.

是否存在任何现代的通用CPU,从不同的线程同时写入数组的相邻元素是不安全的？我对x86特别感兴趣.你可以假设编译器没有做任何明显荒谬的事情来增加内存粒度,即使它在技术上是在标准范围内.

我对编写任意大型结构的情况感兴趣,而不仅仅是本机类型.

注意:

请不要提及有关虚假共享的性能问题.我很清楚这些,但它们对我的用例没有实际意义.我也知道从除读者之外的线程写入的数据的可见性问题.我的代码解决了这个问题.

澄清:出现这个问题是因为在某些处理器(例如,旧的DEC Alphas)上,内存只能在字级处理.因此,以非字大小增量(例如,单个字节)写入存储器实际上涉及要写入的字节的读 - 修改 - 写入以及引擎盖下的一些相邻字节.要想象这一点,请考虑写入单个位所涉及的内容.你读取了字节或单词,对整个事物执行按位操作,然后将整个事情写回来.因此,您无法安全地从不同的线程写入相邻的位.

理论上,当硬件不需要时,编译器也可以通过这种方式实现内存写入,这在理论上是可行的,尽管非常愚蠢.x86可以解决单个字节,所以它主要不是问题,但我想弄清楚是否有任何奇怪的角落情况.更一般地,我想知道,如果写在不同的线程的阵列的相邻元件仍然是一个现实的问题或大多只是一种理论上只适用于掩盖/古硬件和/或很奇怪的编译器.

又一个编辑:这是一个很好的参考,描述了我正在谈论的问题:

http://my.safaribooksonline.com/book/programming/java/0321246780/threads-and-locks/ch17lev1sec6