小编mar*_*nus的帖子

有时我看到Θ(n)带有奇怪的Θ符号,中间有一些东西,有时只有O(n).这只是打字的懒惰,因为没有人知道如何输入这个符号,或者它是否意味着不同的东西？

我总是想知道为什么编译器无法弄清楚对人眼来说显而易见的简单事物.他们做了很多简单的优化,但从来没有一点甚至有点复杂.例如,此代码在我的计算机上大约需要6秒才能打印零值(使用java 1.6):

int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
    x += x + x + x + x + x;
}
System.out.println(x);

很明显,x永远不会改变,所以无论你多久给自己添加0,它就会保持为零.因此编译器理论上可以用System.out.println(0)替换它.

或者甚至更好,这需要23秒:

public int slow() {
    String s = "x";
    for (int i = 0; i < 100000; ++i) {
        s += "x";
    }
    return 10;
}

首先,编译器可能会注意到我实际上正在创建一个100000"x"的字符串,因此它可以自动使用s StringBuilder,甚至更好地直接用结果字符串替换它,因为它总是相同的.其次,它没有意识到我根本没有使用该字符串,因此整个循环可能被丢弃!

为什么在这么多人力进入快速编译器之后,他们仍然是如此相对愚蠢？

编辑:当然这些是永远不应该在任何地方使用的愚蠢的例子.但每当我必须将一个漂亮且非常易读的代码重写为不可读的代码以便编译器很开心并生成快速代码时,我想知道为什么编译器或其他一些自动化工具不能为我做这项工作.

想象一下,你有各种各样大小的浮点数.计算总和的最正确方法是什么,误差最小？例如,当数组看起来像这样:

[1.0, 1e-10, 1e-10, ... 1e-10.0]

然后你用一个简单的循环从左到右加起来,比如

sum = 0
numbers.each do |val|
    sum += val
end

无论何时加起来,较小的数字可能会低于精度阈值,因此误差会越来越大.据我所知,最好的方法是对数组进行排序并开始将数字从最低到最高相加,但我想知道是否有更好的方法(更快,更精确)？

编辑:谢谢你的答案,我现在有一个工作代码,完美地总结了Java中的双重值.它是获胜答案的Python帖子的直接端口.该解决方案通过了我的所有单元测试.(这里有更长但优化的版本Summarizer.java)

/**
 * Adds up numbers in an array with perfect precision, and in O(n).
 * 
 * @see http://code.activestate.com/recipes/393090/
 */
public class Summarizer {

    /**
     * Perfectly sums up numbers, without rounding errors (if at all possible).
     * 
     * @param values
     *            The values to sum up.
     * @return The sum.
     */
    public static double msum(double... values) {
        List<Double> …

在算法中,每当我添加一个值时,我都必须计算数据集的第75个百分位数.现在我这样做:

1. 获得价值 x
2. x在后面插入已排序的数组
3. 交换x,直到数组排序
4. 读取位置处的元素 array[array.size * 3/4]

点3是O(n),其余是O(1),但这仍然很慢,特别是如果阵列变大.有没有办法优化这个？

UPDATE

谢谢尼基塔!由于我使用的是C++,因此这是最容易实现的解决方案.这是代码:

template<class T>
class IterativePercentile {
public:
  /// Percentile has to be in range [0, 1(
  IterativePercentile(double percentile)
    : _percentile(percentile)
  { }

  // Adds a number in O(log(n))
  void add(const T& x) {
    if (_lower.empty() || x <= _lower.front()) {
      _lower.push_back(x);
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
    } else {
      _upper.push_back(x);
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
    }

    unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
    if (_lower.size() …

有没有办法测试哈希函数的质量？我想在哈希表中使用时有一个很好的传播,如果在单元测试中可以验证它会很好.

编辑:为了澄清,我的问题是我使用longJava中的值,使得前32位编码ID,第二位32位编码另一个ID.不幸的是,Java的长值散列只是将前32位与第二位32位异或,这在我的情况下导致在使用时的性能非常差HashMap.所以我需要一个不同的哈希,并希望有一个单元测试,以便这个问题不再蔓延.

George Marsaglia编写了一个优秀的随机数发生器,它非常快速,简单,并且具有比Mersenne Twister高得多的周期.这是带有描述的代码:

好的C随机数发生器

我想将CMWC4096代码移植到Java,但它使用了几种无符号数据类型,因此我不确定如何正确执行此操作.这是完整的C代码:

/* choose random initial c<809430660 and */
/* 4096 random 32-bit integers for Q[]   */
static unsigned long Q[4096],c=362436;

unsigned long CMWC4096(void) {
    unsigned long long t, a=18782LL;
    static unsigned long i=4095;
    unsigned long x,r=0xfffffffe;
    i = (i+1) & 4095;
    t = a*Q[i] + c;
    c = (t>>32);
    x = t + c;
    if (x < c) {
        x++;
        c++;
    }
    return (Q[i] = r - x);
}

任何人都可以将其移植到Java吗？当您只有签名号码时,这是如何工作的？

编辑:谢谢大家快速解答!对于前1亿个数字,这个java代码似乎产生与C代码相同的结果.它比Java的java.util.Random快3倍.

public class ComplimentaryMultiplyWithCarryRandom { …

我最近发现在STL中存在一个名为nth_element的方法.引用描述:

Nth_element类似于partial_sort,因为它部分地对一系列元素进行排序:它排列范围[first,last],使得迭代器nth指向的元素与该位置中的元素相同(如果整个范围[第一个,最后一个]已经排序.另外,[nth,last]范围内的元素都不小于[first,nth]范围内的任何元素.

它声称平均具有O(n)复杂性.算法如何工作？我找不到任何解释.

我们有几种不同的优化算法,可以为每次运行产生不同的结果.例如,优化的目标可以是找到函数的最小值,其中0是全局最小值.优化运行返回如下数据:

[0.1, 0.1321, 0.0921, 0.012, 0.4]

这与全球最小值非常接近,所以这没关系.我们的第一种方法是选择一个阈值,如果结果发生得太高,让单元测试失败.不幸的是,这根本不起作用:结果似乎有一个高斯分布,因此,虽然不太可能,但即使算法仍然很好而且我们运气不好,测试也会不时发生.

那么,我该如何正确测试呢？我想这里需要相当多的统计数据.同样重要的是测试仍然很快,只需让测试运行几百次,然后取平均值就太慢了.

以下是一些进一步的说明:

• 例如,我有一个算法将Circle拟合成一组点.它非常快,但并不总能产生相同的结果.我想写一个单元测试,以保证在大多数情况下它足够好.

• 不幸的是我无法为随机数生成器选择固定种子,因为我不想测试算法是否产生与以前完全相同的结果,但我想测试类似"有90%确定性我得到0.1或者0.1的结果"更好".

我想将引用传递给函数.这段代码不起作用,正如我所期望的那样:

struct A {
};

void foo(A& a) {
    // do something with a
}

int main(int, char**) {
    foo(A());
}

我收到编译错误

A&从类型的右值开始无效初始化类型的非const引用A

但是当我只是将方法添加A& ref()到A下面并在传递它之前调用它时,似乎我可以使用它a.调试时,A对象在foo()被调用后被销毁:

struct A {
    A& ref() {
        return *this;
    }
};

void foo(A& a) {
    // do something with a
}

int main(int, char**) {
    foo(A().ref());
}

这个有效的代码是否符合标准？调用是否会ref()神奇地延长对象的生命周期直到foo()返回？

在我的工作场所,我们有一个大型Subversion存储库,可容纳大约100个项目.有些项目通过svn:externals互相使用.通常所有人都对所有内容都具有读写权限,但有时外部人员和实习生只限制对某些自定义文件夹的读/写访问权限,因此他们无法获得我们的皇冠上的宝石.

你会如何在git中构建它？每个Project都有自己的存储库？你怎么能重用代码？你能以某种方式实现访问权限吗？