ANSI标准是否要求逻辑运算符在C或C++中被短路？

我很困惑,因为我记得K&R的书说你的代码不应该依赖于这些操作被短路,因为它们可能没有.有人可以指出标准中的哪个位置逻辑操作始终是短路的吗？我最感兴趣的是C++,C的答案也很棒.

我还记得读(不记得在哪里)评估顺序没有严格定义,所以你的代码不应该依赖或假设表达式中的函数将按特定的顺序执行:在语句的末尾所有引用的函数将被调用,但编译器可以自由选择最有效的顺序.

标准是否表明该表达式的评估顺序？

if( functionA() && functionB() && functionC() ) cout<<"Hello world";

我有一个程序需要重复计算数据集的近似百分位数(顺序统计),以便在进一步处理之前删除异常值.我目前正在通过对值数组进行排序并选择适当的元素来实现这一目标; 这是可行的,但它在配置文件上是一个值得注意的昙花一现,尽管它是该计划的一个相当小的部分.

更多信息:

• 该数据集包含了100000浮点数字的顺序,并认为是"合理"分配 - 有不太可能在不久的特定值密度的重复,也不巨大的尖峰; 如果一些奇怪的原因分布为奇数,这是确定一个近似是不太准确的,因为数据很可能搞砸总之,进一步处理可疑.但是,数据不一定是统一的或正态分布的; 它不太可能退化.
• 近似解决方案没问题,但我确实需要了解近似值如何引入错误以确保其有效.
• 由于目标是去除异常值,我在任何时候都在同一数据上计算两个百分点:例如一个在95%,一个在5%.
• 该应用程序在C#中,在C++中有点繁重; 任何一个伪代码或预先存在的库都可以.
• 一个完全不同的去除异常值的方法也可以,只要它是合理的.
• 更新:似乎我正在寻找一种近似选择算法.

虽然这都是在一个循环中完成的,但每次数据(略微)都不同,因此重用数据结构并不像这个问题那样容易.

实施解决方案

使用Gronim建议的维基百科选择算法将这部分运行时间减少了大约20倍.

由于我找不到C#实现,这就是我想出的.即使对于小型输入,它也比Array.Sort更快; 在1000个元素上它快25倍.

public static double QuickSelect(double[] list, int k) {
    return QuickSelect(list, k, 0, list.Length);
}
public static double QuickSelect(double[] list, int k, int startI, int endI) {
    while (true) {
        // Assume startI <= k < endI
        int pivotI = (startI + endI) / 2; //arbitrary, but good if sorted
        int splitI = partition(list, startI, …

假设您有大量的键/值对,其中值是一些任意实数.您有兴趣创建支持以下操作的数据结构:

• Insert,为集合添加新的键/值对,
• 删除,从集合中删除键/值对,
• 百分,它告诉哪个百分与给定键相关联的值是,和
• Tell- Percentile,接受百分位数并返回其值为至少给定百分位数的最低值的键.

例如,该数据结构可以用于在接收全国范围的测试分数流时有效地确定给定学生的百分位数,或者识别具有异常好的或差的服务质量的医院.

有没有办法让这些操作有效运行(比如,次线性时间？)

我正在寻找一个提供列表语义的集合,但也允许数组语义.假设我有一个包含以下项目的列表:

apple orange carrot pear 

然后我的容器数组将:

container[0] == apple 
container[1] == orangle 
container[2] == carrot 

然后说我删除了橙色元素:

container[0] == apple 
container[1] == carrot 

我想在不必显式调整大小的情况下折叠数组中的间隙,即如果我删除容器[0],则容器会崩溃,因此容器[1]现在被映射为容器[0]和容器[2]作为容器[1]等我仍然需要使用数组语义访问列表,并且不允许空值(在我的特定用例中).

编辑:

回答一些问题 - 我知道O(1)是不可能的,但我不希望容器的数组语义接近O(log N).排序失败的目的,我可以迭代列表.

我原本在排序顺序上有一些措辞,我不确定我当时的想法(星期五啤酒时钟最有可能).其中一个用例是包含图像的Qt列表 - 从列表中删除图像应该折叠列表,不必从列表中取出最后一项并将其放入其中.在这种情况下,我确实想要保留列表语义.

我看到的关键差异是分隔列表和数组:数组 - 常量时间访问列表 - 任意插入

如果重新平衡使迭代器失效,我也不会过分担心.