Kaip įvertinti dvejetainio kodo sudėtingumą?

Binarinio kodo sudėtingumo įvertinimas nėra standartinė užduotis Frontend kūrėjui. Paprastai tai atlieka našumo analizės specialistai, atgalinės inžinerijos ar saugumo srityje.

Tačiau, hipotetiškai manytume, kad kalbame apie kodo našumo analizę (pavyzdžiui, WebAssembly, kuris yra binarinis formatas), tada požiūriai galėtų būti šie:

• Statinė analizė: kodo struktūros tyrimas be jo vykdymo. Tai leidžia įvertinti:
  • kodo dydį.
  • instrukcijų skaičių.
  • registrų naudojimą.
  • steko gylį.
  • ciklų ir rekursijos buvimą (su apribotu tikslumu).
• Dinaminė analizė: kodo vykdymas ir metrikų rinkimas. Tai leidžia įvertinti:
  • vykdymo laiką.
  • procesoriaus apkrovą.
  • atminties naudojimą.
  • elgseną su įvairiais įėjimo duomenimis. Įrankiai gali apimti profilinius įrankius.
• Vadybos srauto grafo (Control Flow Graph - CFG) analizė: galimų kodo vykdymo kelių vizualizacija. Tai padeda atskleisti sudėtingus šakotus ir ciklus.
• Duomenų priklausomybės analizė: kaip duomenys perduodami tarp instrukcijų. Tai padeda nustatyti duomenų apdorojimo vietas.
• Specializuotų įrankių naudojimas: yra įrankių, skirtų binarinių kodų atgalinei inžinerijai ir analizei (pvz., Ghidra, IDA Pro), tačiau jų naudojimas dažnai viršija įprastų Frontend kūrėjų užduotis.

Frontend kūrėjui labiau aktualu ir tinkama įvertinti JavaScript ar kitų šaltinio kodų sudėtingumą, kuris dažnai grindžiamas:

• Laiko sudėtingumu (Time Complexity): kaip vykdymo laikas auga su įvesties duomenų dydžio padidėjimu (pavyzdžiui, O(1), O(n), O(n log n), O(n^2)).
• Atminties sudėtingumu (Space Complexity): kaip atminties naudojimas auga su įvesties duomenų dydžio padidėjimu.

Laiko sudėtingumo įvertinimas dažnai atliekamas analizuojant algoritmą. Populiarios notacijos apima:

Notacija	Pavadinimas	Aprašymas	Operacijos pavyzdys
O(1)	Pastovus	Laiko trukmė nepriklauso nuo duomenų	Masivo elemento prieiga pagal indeksą
O(log n)	Logaritminis	Laiko trukmė lėtai auga	Dvejetinis paieška
O(n)	Linijinis	Laiko trukmė proporcinga duomenų kiekiui	Linijinis paieška
O(n$^2$)	Kvadratinis	Laiko trukmė greitai auga	Burbuliukų rūšiavimas

Pavyzdys JavaScript kalba, įvertinant laiko sudėtingumą:

// O(n) - linijinis sudėtingumas
function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

// O(n^2) - kvadratinis sudėtingumas
function multiplyMatrices(matrixA, matrixB) {
  const rowsA = matrixA.length;
  const colsA = matrixA[0].length;
  const rowsB = matrixB.length;
  const colsB = matrixB[0].length;
  if (colsA !== rowsB) {
    throw new Error("Neatitinkančių matricos dydžių");
  }
  const result = new Array(rowsA).fill(0).map(() => new Array(colsB).fill(0));

  for (let i = 0; i < rowsA; i++) {
    for (let j = 0; j < colsB; j++) {
      for (let k = 0; k < colsA; k++) {
        result[i][j] += matrixA[i][k] * matrixB[k][j];
      }
    }
  }
  return result;
}

Taigi, binarinio kodo sudėtingumo įvertinimas yra uždavinys, kuris viršija įprastų Frontend kūrėjų pareigas, skirtingai nuo šaltinio kodo sudėtingumo įvertinimo, kuris yra svarbus našiai interneto programų kūrimo aspektas.