Mise en œuvre plus rapide de la somme (pour le test de codité)

Cela ne vous aidera pas avec un algorithme O (N ^ 2), mais vous pouvez optimiser votre somme.

Lors d'une entreprise précédente, nous avons eu Intel viennent de venir et de nous donner des conseils d'optimisation. Ils avaient une astuce non évidente et un peu fraîche. Remplacer: xxx

avec xxx

pourquoi il est plus rapide: Dans la mise en œuvre initiale, votre variable R est un goulot d'étranglement. Chaque fois que traversez la boucle, vous devez tirer des données de la mémoire de mémoire A (qui prend quelques cycles), mais vous ne pouvez pas effectuer de multiples tirettes en parallèle, car la valeur de R dans la prochaine itération de la boucle dépend de la valeur. de r dans cette itération de la boucle. Dans la deuxième version, R1, R2, R3 et R4 sont indépendants, le processeur peut donc hyperthread leur exécution. Seulement à la fin, se réunissent-ils.

{In Pascal + Assembly}
{$ASMMODE INTEL}
function equi (A : Array of longint; n : longint ) : longint;
var c:Longint;
    label noOverflow1;
    label noOverflow2;
    label ciclo;
    label fine;
    label Over;
    label tot;
Begin
 Asm
    DEC n
    JS over
    XOR ECX, ECX   {Somma1}
    XOR EDI, EDI   {Somma2}
    XOR EAX, EAX
    MOV c, EDI
    MOV ESI, n
  tot:
    MOV EDX, A
    MOV EDX, [EDX+ESI*4]
    PUSH EDX
    ADD ECX, EDX
    JNO nooverflow1
    ADD c, ECX
    nooverflow1:
    DEC ESI
  JNS tot;
    SUB ECX, c
    SUB EDI, c
  ciclo:
    POP EDX
    SUB ECX, EDX
    CMP ECX, EDI
    JE fine
    ADD EDI, EDX
    JNO nooverflow2
    DEC EDI
    nooverflow2:
    CMP EAX, n
    JA over
    INC EAX
    JMP ciclo
    over:
      MOV EAX, -1
    fine:
  end;
End;

private static int equi ( int[] A ) {
    if (A == null || A.length == 0)
     return -1;
 long tot = 0;
 int len = A.length;
 for(int i=0;i<len;i++)
     tot += A[i];
 if(tot == 0)
     return (len-1);
 long partTot = 0;
 for(int i=0;i<len-1;i++)
 {
  partTot += A[i];
  if(partTot*2+A[i+1] == tot)
   return i+1;
 }
 return -1;
}I considered the array as a bilance so if the equilibrium index exist then half of the weight is on the left. So I only compare the partTot (partial total) x 2 with the total weight of the array. 
the Alg takes O(n) + O(n)

J'ai marqué 100% pour celui-ci:

int equi (int[] A)
{
    if (A == null) return -1;

    long sum0 = 0, sum1 = 0;

    for (int i = 0; i < A.Length; i++) sum0 += A[i];

    for (int i = 0; i < A.Length; i++)
    {
        sum0 -= A[i];
        if (i > 0)
        {
            sum1 += A[i - 1];
        }          
        if (sum1 == sum0) return i;      
    }        
    return -1;
}

Voici une pensée: xxx

solution 100% o (n) en C xxx

probablement pas parfait mais qu'il passe de toute façon :)

peut ' T Sense que je suis un grand fan de la codilité, c'est une idée intéressante, mais j'ai trouvé les exigences un peu trop vagues. Je pense que je serais plus impressionné s'ils vous ont donné des exigences + une suite de tests unitaires qui testent ces exigences et alors vous ont demandé d'écrire du code. C'est ainsi que la plupart du TDD survient de toute façon. Je ne pense pas que ça aveugle gagne vraiment autre chose que de leur permettre de jeter dans des cas de coin.