相关疑难解决方法(0)

更新:原来在解析器中有一个生成树的错误.更多在最终编辑.

我们T是一个二叉树,使得每一个内部节点正好有两个孩子.对于这棵树,我们要的代码,为每个节点的功能v中T发现了被定义子树的节点数目v.

例

输入

期望的输出

用红色表示我们想要计算的数字.树的节点将存储在一个数组中,让我们TreeArray按照预先排序布局调用它.

对于上面的示例,TreeArray将包含以下对象:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

树的节点由以下结构描述:

struct tree_node{

    long long int id; //id of the node, randomly generated
    int numChildren; //number of children, it is 2 but for the leafs it's 0
    int size; //size of the subtree rooted at the current node,
    // what we want …

我写了一个函数来确定两个单词是否是字谜.单词A是单词B的字谜,如果你可以通过重新排列字母来构建单词B,例如:

lead is anagram of deal

这是我的功能:

bool is_anagram(std::string const & s1, std::string const & s2)
{
    auto check = [](std::string const & x)
    {
        std::map<char, unsigned> counter;
        for(auto const & c : x)
        {
            auto it = counter.find(c);
            if(it == counter.end())
                counter[c] = 1;
            else
                ++counter[c];
        }
        return counter;
    };

    return check(s1) == check(s2);
}

这样可以正常工作,但随着单词数量的增加(这个函数在我的应用程序中使用了数百万次),很快就成了我应用程序的主要瓶颈.

有没有人知道如何加快这个功能？

我写的代码看起来像以下......

if(denominator == 0){
    return false;
}
int result = value / denominator;

...当我考虑CPU中的分支行为时.

/sf/answers/785953171/ 这个答案说CPU将尝试正确猜测分支将走向哪个方向,并且如果发现分支错误地猜测分支,那么只停下该分支停止.

但是如果CPU预测上面的分支不正确,它将在以下指令中除以零.虽然这不会发生,我想知道为什么？CPU是否实际执行除零并在执行任何操作之前等待分支是否正确,还是可以告诉它在这些情况下不应该继续？这是怎么回事？

这对我来说是一种耻辱,但我不知道:

您应该使用clone来复制数组,因为这通常是最快的方法.

正如Josh Bloch在本博客中所述:http://www.artima.com/intv/bloch13.html

我总是用System.arraycopy(...).这两种方法都是原生的,所以可能没有深入到我无法弄清楚的库的来源,为什么会如此.

我的问题很简单:为什么它是最快的方式？ 有什么区别System.arraycopy？这里 解释了不同之处,但它没有回答为什么Josh Bloch认为clone()最快的方式.

我有一个数组,long matrix[8*1024][8*1024]和两个函数sum1和sum2:

long sum1(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (i=0; i < ROWS; i++) {
        for (j=0; j < COLS; j++) {
            sum += m[i][j];
        }
    }
    return sum;
}

long sum2(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (j=0; j < COLS; j++) {
        for (i=0; i < ROWS; i++) {
            sum += m[i][j];
        }
    }

    return sum;
}

当我用给定的数组执行这两个函数时,我得到运行时间:

sum1:0.19s

sum2:1.25s

任何人都可以解释为什么会有这么大的差异？

几天前在Facebook上的演讲 - 幻灯片,视频,Andrei Alexandrescu谈到可能证明我们错了的共同直觉.对我来说,幻灯片7中出现了一个非常有趣的观点,他指出假设"更少的指令=更快的代码"是不正确的,更多的指令并不一定意味着更慢的代码.

这就是我的问题:他的谈话的音质(大约6:20分钟)不是那么好,我不太理解这个解释,但从我得到的是他将退役指令与算法的最优性进行比较绩效水平.

但是,根据我的理解,这是不可能做到的,因为这是两个独立的结构层面.说明(特别是实际上已退役的说明)是一项非常重要的措施,基本上可以让您了解实现目标的绩效.如果我们省略指令的延迟,我们可以推断出更少的退出指令=更快的代码.现在,当然有些情况下,在循环内执行复杂计算的算法即使在循环内执行也会产生更好的性能,因为它会更早地破坏循环(想想图遍历).但是,与复杂程度的算法进行比较而不是说这个循环有更多指令并且比另一个更好会不会更有用？从我的观点来看,更好的算法最终会有更少的退役指令.

有人可以帮助我了解他的例子,以及如何(显着)更多退休指令可以带来更好的表现吗？

由于对性能的巨大影响,我不知道我当前的桌面CPU是否有分支预测.当然可以.但各种ARM产品怎么样？iPhone或Android手机有分支预测吗？旧版的Nintendo DS？基于PowerPC的Wii怎么样？PS 3？

它们是否具有复杂的预测单元并不是那么重要,但是如果它们至少具有一些动态预测,以及它们是否在预期分支之后执行一些指令.

具有分支预测的CPU的截止点是多少？几十年前的手持计算器显然没有一个,而我的桌面确实没有.但是,任何人都能更清楚地概述可以预期动态分支预测的位置吗

如果不清楚,我说的是条件变化的预测类型,在运行时改变预期的路径.

int[] arr = {800,11,50,771,649,770,240, 9};

int temp = 0;

for (int write = 0; write < arr.Length; write++)
{
    for (int sort = 0; sort < arr.Length - 1; sort++)
    {
        if (arr[sort] > arr[sort + 1])
        {
            temp = arr[sort + 1];
            arr[sort + 1] = arr[sort];
            arr[sort] = temp;
        }       
    }   
    Console.Write("{0} ", arr[write]);  
}

我试图做的就是使用这个数组进行简单的冒泡排序.我想弄清楚为什么排序搞砸了.例如,这里的数组是{800,11,50,771,649,770,240, 9}:

以下是显示的内容: 11, 50, 649, 9, 649, 770, 771, 800

我想我可能会在比较中遗漏一些东西.

在C和/或C++中操作动态(所有维度直到运行时才知道)的多维数组的接受/最常用方法是什么.

我正在努力找到完成此Java代码的最简洁方法:

public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 int rows=sc.nextInt();
 int cols=sc.nextInt();
 int[][] data=new int[rows][cols];
 manipulate(data);
}

public static void manipulate(int[][] data){
   for(int i=0;i<data.length;i++)
   for(int j=0;j<data[0].length.j++){
         System.out.print(data[i][j]);       
   }    
}

(从std_in读取只是为了澄清维度直到运行时才知道).

编辑:我注意到这个问题非常受欢迎,即使它很老了.我实际上并不同意最高投票的答案.我认为C的最佳选择是使用一维数组,如Guge所说:"你可以分配行cols sizeof(int)并通过表[row*cols + col]来访问它."

C++有很多选择,如果你真的喜欢boost或stl,那么下面的答案可能更好,但最简单也可能最快的选择是使用C中的单维数组.

如果你想要[] []语法,那么在C和C++中另一个可行的选择是lillq在底部的答案是手动构建具有大量malloc的数组.

使用条件移动(汇编cmov)来优化?:C中的条件表达式是一种常见的优化.但是,C标准说:

第一个操作数被评估; 在其评估与第二或第三操作数的评估之间存在一个序列点(以评估者为准).仅当第一个操作数不等于0时才评估第二个操作数; 仅当第一个操作数比较等于0时才评估第三个操作数; 结果是第二个或第三个操作数的值(无论哪个被评估),转换为下面描述的类型.110)

例如,以下C代码

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int c= a > b ? a + 1 : 2 + b;
    printf("%d", c);
    return 0;
}

将生成优化的相关asm代码,如下所示:

call    __isoc99_scanf
movl    (%rsp), %esi
movl    4(%rsp), %ecx
movl    $1, %edi
leal    2(%rcx), %eax
leal    1(%rsi), %edx
cmpl    %ecx, %esi
movl    $.LC1, %esi
cmovle  %eax, %edx
xorl    %eax, %eax
call    __printf_chk

根据标准,条件表达式将仅评估一个分支.但是这里对两个分支进行了评估,这违反了标准的语义.这是针对C标准的优化吗？或者许多编译器优化是否与语言标准不一致？