Clever Geek Handbook

An alliance with an insidious mistake

Having a problem understanding that when we want to go through the whole array and compare each value of the array with the number present in the array, say arr [0], then why is it recommended to initialize int with arr [0], just like int acomp = arr [0], and compare acomp with any integer present in the array, than compare any integer present in the array with arr [0]? For example, in the following union code, I was told that Code 2 is better than Code 1, but I'm not entirely sure why.

int unionarr(int p, int q){            //Code 1
    for(int i=0;i<size;i++)
        if(arr[i]==arr[p])
            arr[i]=arr[q];}

int unionarr(int p, int q){            //Code 2
    int pid=arr[p];
    int qid=arr[q];
        for(int i=0;i<size;i++)
        if(arr[i]==pid)
            arr[i]=qid;}
+3


source to share


3 answers


This is a correctness problem. An assignment within a loop for

can change the values ​​of the array. You can change the very elements that are used in the comparison or on the right side of the assignment. This is why you must save them before entering the loop.



+4


source


Making local copies of the pid and qid values ​​that would otherwise have to be re-searched in the array is a bit of a performance optimization.
However, I would be surprised if some modern compiler could not raise this value and do this optimization implicitly.



0


source


Using https://godbolt.org/ you can compare them. what you need is an instruction inside the loop.

With Clang 4.0 build:

  • Code 1

    movsxd  rax, dword ptr [rbp - 16]
mov     ecx, dword ptr [4*rax + arr]
movsxd  rax, dword ptr [rbp - 8]
cmp     ecx, dword ptr [4*rax + arr]
jne     .LBB0_4
movsxd  rax, dword ptr [rbp - 12]
mov     ecx, dword ptr [4*rax + arr]
movsxd  rax, dword ptr [rbp - 16]
mov     dword ptr [4*rax + arr], ecx

  • Code 2

    movsxd  rax, dword ptr [rbp - 24]
mov     ecx, dword ptr [4*rax + arr]
cmp     ecx, dword ptr [rbp - 16]
jne     .LBB0_4
mov     eax, dword ptr [rbp - 20]
movsxd  rcx, dword ptr [rbp - 24]
mov     dword ptr [4*rcx + arr], eax
0


source






More articles:


All Articles