ហេតុអ្វីរចនាសម្ព័ន្ធទិន្នន័យ និងក្បួនដោះស្រាយសំខាន់

មាតិកា

1. ទំព័រដែលក្លាយជាយឺត
2. និយមន័យនៃរចនាសម្ព័ន្ធទិន្នន័យ និងក្បួនដោះស្រាយ
3. កន្លែងដែលអ្នកជួបពួកវាក្នុងការងារ
4. Big-O ក្នុងប្រាំនាទី
5. រៀបចំគម្រោង algolab
6. Benchmark ដំបូងរបស់អ្នក៖ includes ទល់នឹង Set
7. រចនាសម្ព័ន្ធគឺជាល្បឿន
8. ពេលវេលាទល់នឹងអង្គចងចាំ
9. របៀបប្រើស៊េរីនេះ
10. រូបមន្ត៖ module bench
11. សាកល្បងដោយខ្លួនឯង

1. ទំព័រដែលក្លាយជាយឺត

នេះគឺជារឿងដែលកើតឡើងលើស្ទើរតែគ្រប់ក្រុម។ អ្នកអភិវឌ្ឍន៍ម្នាក់សាងសង់ទំព័រ admin ដែលបង្ហាញបញ្ជីការបញ្ជាទិញ (order) ហើយនៅជាប់នឹងការបញ្ជាទិញនីមួយៗ វាបង្ហាញឈ្មោះអតិថិជន។ កូដសាមញ្ញ៖

interface Customer {
  id: number;
  name: string;
}

interface Order {
  id: number;
  customerId: number;
  total: number;
}

function attachNames(orders: Order[], customers: Customer[]) {
  return orders.map((order) => {
    const customer = customers.find((c) => c.id === order.customerId);
    return { ...order, customerName: customer?.name ?? "unknown" };
  });
}

ជាមួយការបញ្ជាទិញ 50 និងអតិថិជន 20 នាក់ក្នុង database សាកល្បង វាដំណើរការភ្លាមៗ។ មួយឆ្នាំក្រោយមក ហាងមានអតិថិជន 20,000 នាក់ និងការបញ្ជាទិញ 200,000។ function ដដែលនោះឥឡូវធ្វើការប្រៀបធៀបរហូតដល់ 200,000 គុណ 20,000 ដងដែលស្មើនឹងបួនពាន់លានជំហាន។ ទំព័រចំណាយពេលកន្លះនាទី ហើយកង្ហារម៉ាស៊ីនមេចាប់ផ្តើមបក់យ៉ាងខ្លាំង។

គ្មាននរណាសរសេរ bug ទេ។ កូដត្រឹមត្រូវ។ វាគ្រាន់តែសាងសង់លើ រចនាសម្ព័ន្ធទិន្នន័យ ខុស៖ array ធម្មតាដែលត្រូវស្វែងរកពីដើមរាល់ពេល។ រក្សាអតិថិជននៅក្នុង Map ដែលមាន key ជា id នោះរាល់ការស្វែងរកក្លាយជាជំហានតែមួយ៖

function attachNamesFast(orders: Order[], customers: Customer[]) {
  const byId = new Map<number, Customer>();
  for (const c of customers) byId.set(c.id, c);

  return orders.map((order) => ({
    ...order,
    customerName: byId.get(order.customerId)?.name ?? "unknown",
  }));
}

កំណែថ្មីធ្វើ 20,000 ជំហានដើម្បីសាងសង់ map បន្ទាប់មកស្វែងរកលឿន 200,000 ដង។ ប្រហែលមួយភាគបួនលានជំហាន ជំនួសឲ្យបួនពាន់លាន។ លទ្ធផលដូចគ្នា តែការរៀបចំទិន្នន័យខុសគ្នា។ ការផ្លាស់ប្តូរតែមួយនោះគឺជាអ្វីដែលស៊េរីទាំងមូលនេះនិយាយអំពី។

2. និយមន័យនៃរចនាសម្ព័ន្ធទិន្នន័យ និងក្បួនដោះស្រាយ

ពាក្យពីរ គំនិតពីរ។

រចនាសម្ព័ន្ធទិន្នន័យ (data structure) គឺជាវិធីរៀបចំទិន្នន័យក្នុងអង្គចងចាំ ដើម្បីឲ្យប្រតិបត្តិការខ្លះមានតម្លៃថោក។ Array រក្សាធាតុជាជួរ ដូច្នេះអ្នកអាចលោតទៅកាន់ទីតាំងណាមួយបាន។ Hash map រក្សាគូ key-value ដូច្នេះអ្នកអាចរកតម្លៃតាម key របស់វាបាន។ Stack រក្សាធាតុដូច្នេះអ្នកអាចប៉ះបានតែធាតុថ្មីបំផុត។ រចនាសម្ព័ន្ធនីមួយៗគឺជាសំណុំនៃការដោះដូរ៖ វាធ្វើឲ្យប្រតិបត្តិការខ្លះលឿន និងខ្លះទៀតយឺត ហើយគ្មានរចនាសម្ព័ន្ធណាល្អបំផុតក្នុងគ្រប់យ៉ាងទេ។

ក្បួនដោះស្រាយ (algorithm) គឺជាបញ្ជីជំហានច្បាស់លាស់ដែលដោះស្រាយបញ្ហាមួយ។ "មើលធាតុនីមួយៗ ចងចាំធាតុធំបំផុតរហូតមកដល់ពេលនេះ ហើយ return វា" គឺជាក្បួនដោះស្រាយសម្រាប់រកតម្លៃធំបំផុត។ "កាត់បញ្ជីដែលបានតម្រៀបជាពាក់កណ្តាលរហូតរកឃើញគោលដៅ" គឺជាក្បួនដោះស្រាយដែលហៅថា binary search។

ទាំងពីរជាដៃគូគ្នា។ ក្បួនដោះស្រាយត្រូវការកន្លែងមួយដើម្បីរក្សាទិន្នន័យរបស់វា ហើយរចនាសម្ព័ន្ធមានប្រយោជន៍តែនៅពេលមានក្បួនដោះស្រាយល្អៗសម្រាប់ធ្វើការជាមួយវា។ អ្នកនឹងឃើញរឿងនេះម្តងហើយម្តងទៀត៖ ជំហានឆ្លាតវៃក្នុងក្បួនដោះស្រាយជាធម្មតាគឺ "ដាក់ទិន្នន័យក្នុងរចនាសម្ព័ន្ធដែលសំណួរនេះមានតម្លៃថោក"។

មានចំណុចពីរបន្ថែមទៀតមុននឹងបន្ត។

• ត្រឹមត្រូវមកមុន លឿនមកទីពីរ។ ក្បួនដោះស្រាយដែលផ្តល់ចម្លើយខុសយ៉ាងលឿន គឺគ្មានតម្លៃ។ រាល់ជំពូកបង្ហាញអ្នកនូវកំណែសាមញ្ញជាមុន ហើយបន្ទាប់មកទើបធ្វើឲ្យវាលឿន។
• អ្នកស្ទើរតែមិនដែលបង្កើតពួកវាថ្មីទេ។ អ្នកវិទ្យាសាស្ត្រកុំព្យូទ័របានសិក្សាបញ្ហាទាំងនេះអស់រាប់ទសវត្សរ៍។ ការងាររបស់អ្នកគឺសម្គាល់ថាឧបករណ៍ដែលស្គាល់ណាមួយសមស្រប ហើយដឹងថាវាមានតម្លៃប៉ុនណា។

3. កន្លែងដែលអ្នកជួបពួកវាក្នុងការងារ

អ្នកប្រហែលជាកំពុងគិតថា៖ "ខ្ញុំប្រើ Array និង Map រាល់ថ្ងៃ ហើយមិនដែលគិតអំពីវាទេ។" នោះជាការពិត ហើយជាហេតុផលដែលប្រធានបទទាំងនេះសមនឹងមានជំពូកពីរបីជំពូក។ ស្ទើរតែគ្រប់កម្មវិធីដែលអ្នកប៉ះ គឺជារចនាសម្ព័ន្ធទិន្នន័យក្នុងទម្រង់ក្លែងបន្លំ៖

អ្នកក៏នឹងជួបពួកវានៅក្នុង ការសម្ភាសន៍បច្ចេកទេស ដែរ។ អ្នកសម្ភាសន៍សួរអំពី array, hash map, tree និង graph មិនមែនដោយសារការងាររបស់អ្នកនឹងត្រូវបញ្ច្រាស linked list ពេញមួយថ្ងៃនោះទេ ប៉ុន្តែដោយសារបញ្ហាតូចមួយបង្ហាញថាអ្នកបំបែកអ្វីមួយ សាកល្បងវា និងវិនិច្ឆ័យតម្លៃរបស់វាយ៉ាងដូចម្តេច។ ស៊េរីនេះបង្រៀនខ្លឹមសារ ហើយផ្តល់ឲ្យអ្នកនូវវិធីសាស្ត្រសម្រាប់រឿងនោះនៅក្នុងជំពូកចុងក្រោយ។

4. Big-O ក្នុងប្រាំនាទី

ដើម្បីប្រៀបធៀបវិធីសាស្ត្រពីរ យើងត្រូវការវិធីពណ៌នាតម្លៃរបស់វាដែលមិនអាស្រ័យលើកុំព្យូទ័រយួរដៃរបស់អ្នកណាដែលដំណើរការវា។ នោះគឺជា សញ្ញា Big-O។ វាពណ៌នាអំពីរបៀបដែលចំនួនជំហាន លូតលាស់ នៅពេលទំហំ input n លូតលាស់។ រឿងពេញលេញមាននៅក្នុង សញ្ញា Big-O ពីស៊េរីគណិតវិទ្យាសម្រាប់អ្នកសរសេរកម្មវិធី។ ប្រសិនបើអ្នកបានអានវា នេះគឺជាការរំលឹកខ្លីៗ។ ប្រសិនបើអ្នកមិនទាន់បានអាន សូមអានផ្នែកនេះ ហើយបន្ទាប់មករំលងមើលជំពូកនោះ។

ច្បាប់បីដែលអ្នកត្រូវការនៅថ្ងៃនេះ៖

1. រាប់ loop។ Loop មួយលើ input គឺ O(n)។ Loop ក្នុង loop ទាំងពីរលើ input គឺ O(n^2)។ ការកាត់បញ្ហាជាពាក់កណ្តាលរាល់ជំហានគឺ O(log n)។
2. Loop ដែលលាក់ក៏រាប់ដែរ។ arr.includes(x), arr.indexOf(x), arr.find(...), arr.slice() និង string.includes(...) ទាំងអស់ loop នៅខាងក្នុង។ ហៅមួយក្នុងចំណោមពួកវានៅក្នុង loop របស់អ្នកផ្ទាល់ នោះអ្នកមាន O(n^2)។ នោះគឺជា bug ក្នុងផ្នែកទី 1៖ customers.find គឺជា loop ដែលលាក់។
3. ទម្លាក់ចោល constant និងតួតូចៗ។ 3n + 7 គឺគ្រាន់តែជា O(n)។ Big-O ពណ៌នាអំពី រូបរាង នៃការលូតលាស់ មិនមែនពេលវេលាពិតប្រាកដទេ។

Big-O គឺជាការទស្សន៍ទាយអំពីការលូតលាស់។ វាមិនមែនជានាឡិកាចាប់ពេលទេ។ ចងចាំជានិច្ចថា សម្រាប់ input តូចៗ ក្បួនដោះស្រាយ "អាក្រក់ជាង" អាចលឿនជាង ហើយកូដពិតក៏យកចិត្តទុកដាក់លើអង្គចងចាំ និងភាពអានបានដែរ។ ប៉ុន្តែនៅពេលទិន្នន័យលូតលាស់ រូបរាងឈ្នះ។

5. រៀបចំគម្រោង algolab

ក្នុងស៊េរីនេះ អ្នកសាងសង់បណ្ណាល័យតូចមួយហៅថា algolab។ ជំពូកនីមួយៗបន្ថែម module TypeScript និងឯកសារ test។ យើងដំណើរការអ្វីៗទាំងអស់ជាមួយ Node.js ដោយគ្មានជំហាន build និងគ្មាន browser។

ត្រូវប្រាកដថា Node ត្រូវបានដំឡើង (កំណែ LTS គឺល្អ)៖

node --version

អ្នកគួរឃើញអ្វីដូចជា v22.x ឬខ្ពស់ជាងនេះ។ ឥឡូវបង្កើតគម្រោង៖

mkdir algolab
cd algolab
npm init -y
npm install --save-dev typescript tsx @types/node
mkdir src

tsx គឺជាឧបករណ៍ដែលដំណើរការឯកសារ TypeScript ដោយផ្ទាល់ក្នុង Node ដូច្នេះគ្មានជំហាន compile ទេ។ typescript ផ្តល់ឲ្យអ្នកនូវការពិនិត្យ type ហើយ @types/node បង្រៀន TypeScript អំពីឈ្មោះដែលមានស្រាប់ដូចជា performance និង node:test។

បើក package.json ហើយធ្វើការផ្លាស់ប្តូរពីរ៖ បន្ថែម "type": "module" ដើម្បីឲ្យ Node ចាត់ទុកឯកសាររបស់អ្នកជា ES module ទំនើប ហើយជំនួសផ្នែក scripts ដោយ script សម្រាប់ test និង script សម្រាប់ពិនិត្យ type។ ឯកសារគួរមើលទៅដូចនេះ (លេខកំណែរបស់អ្នកនឹងខុសគ្នា)៖

{
  "name": "algolab",
  "version": "1.0.0",
  "type": "module",
  "private": true,
  "scripts": {
    "test": "tsx --test",
    "typecheck": "tsc"
  },
  "devDependencies": {
    "@types/node": "^22.0.0",
    "tsx": "^4.0.0",
    "typescript": "^5.0.0"
  }
}

បន្ទាប់មកបង្កើត tsconfig.json ក្នុង folder ដូចគ្នា៖

{
  "compilerOptions": {
    "target": "ES2022",
    "module": "NodeNext",
    "moduleResolution": "NodeNext",
    "strict": true,
    "noEmit": true,
    "allowImportingTsExtensions": true,
    "skipLibCheck": true,
    "types": ["node"]
  },
  "include": ["src", "demo.ts"]
}

អ្វីដែលការកំណត់ទាំងនេះធ្វើ៖

• strict បើកការពិនិត្យសុវត្ថិភាពទាំងអស់របស់ TypeScript។ ទុកវាបើកចុះ។
• noEmit មានន័យថា tsc ពិនិត្យតែ type ហើយមិនសរសេរឯកសារ .js ទេ។ tsx ទទួលបន្ទុកការដំណើរការ។
• allowImportingTsExtensions អនុញ្ញាតឲ្យយើងសរសេរ import ... from "./bench.ts" ដែលជាអ្វីដែល Node និង tsx រំពឹងទុកនៅពេលដំណើរការឯកសារ TS ដោយផ្ទាល់។

ឥឡូវអ្នកមានរចនាសម្ព័ន្ធដូចនេះ៖

algolab/
  package.json
  tsconfig.json
  src/
    (modules and tests will go here)
  demo.ts        <- you will create this

ពិនិត្យថាអ្វីៗទាំងអស់បានតភ្ជាប់ត្រឹមត្រូវ។ បង្កើត hello.ts៖

const message: string = "algolab is ready";
console.log(message);

ដំណើរការវា៖

npx tsx hello.ts

algolab is ready

ឥឡូវអ្នកអាចលុប hello.ts បាន។ ពាក្យបញ្ជាពីរដែលអ្នកនឹងប្រើជាប់ជានិច្ច៖

• npx tsx demo.ts ដំណើរការឯកសារមួយ។
• npm test ដំណើរការគ្រប់ឯកសារ *.test.ts ជាមួយ test runner ដែលភ្ជាប់មកជាមួយ Node។ គ្មានបណ្ណាល័យ test ត្រូវដំឡើងទេ។

6. Benchmark ដំបូងរបស់អ្នក៖ includes ទល់នឹង Set

តោះបង្ហាញជាមួយនាឡិកាចាប់ពេលថា រចនាសម្ព័ន្ធដែលអ្នកជ្រើសរើសផ្លាស់ប្តូរល្បឿន។ ទាំង Array និង Set អាចឆ្លើយសំណួរ "តើតម្លៃនេះនៅក្នុងនេះទេ?" ប៉ុន្តែពួកវាធ្វើវាខុសគ្នា៖

• array.includes(x) ដើរកាត់ array ពីដើមរហូតរកឃើញ x។ ក្នុងករណីអាក្រក់បំផុត វាមើលរាល់ធាតុ៖ O(n)។
• set.has(x) គណនាកន្លែងដែល x នឹងត្រូវរក្សាទុក ហើយពិនិត្យតែកន្លែងនោះ។ ជាមធ្យម វាចំណាយ O(1)។ (ជំពូកទី 3 បង្ហាញពីរបៀបដែលវាដំណើរការ។)

បង្កើតឯកសារ demo.ts នៅ root នៃគម្រោង៖

// demo.ts
const arr = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const set = new Set(arr);
const target = arr[arr.length - 1]; // the last item: worst case for the array

let start = performance.now();
for (let i = 0; i < 100; i++) arr.includes(target);
const arrayMs = performance.now() - start;

start = performance.now();
for (let i = 0; i < 100; i++) set.has(target);
const setMs = performance.now() - start;

console.log("array.includes x100:", arrayMs.toFixed(3), "ms");
console.log("set.has x100:       ", setMs.toFixed(3), "ms");
console.log("set is faster:", setMs < arrayMs);

ដំណើរការវាជាមួយ npx tsx demo.ts។ នៅលើកុំព្យូទ័រយួរដៃមួយ លទ្ធផលគឺ៖

array.includes x100: 13.952 ms
set.has x100:        0.032 ms
set is faster: true

ពេលវេលាទាំងពីររបស់អ្នកនឹងខុសគ្នា ហើយនោះជារឿងធម្មតា។ អ្វីដែលមិនគួរផ្លាស់ប្តូរគឺលំដាប់ និងទំហំប្រហាក់ប្រហែលនៃគម្លាត៖ Set លឿនជាងរាប់រយដងនៅទីនេះ។ Array បានស្កេនមួយលានធាតុ 100 ដង។ Set បានធ្វើការស្វែងរកលឿន 100 ដង។

ឥឡូវធ្វើឲ្យទិន្នន័យធំជាងមុនដប់ដង។ ប្តូរ 1_000_000 ទៅ 10_000_000 ហើយដំណើរការម្តងទៀត។ ពេលវេលារបស់ array កើនប្រហែលដប់ដង (នោះគឺ O(n) កំពុងធ្វើការ) ហើយពេលវេលារបស់ Set ស្ទើរតែមិនកម្រើក (នោះគឺ O(1))។ នេះគឺជាអត្ថន័យរបស់ Big-O ក្នុងការអនុវត្តជាក់ស្តែង៖ មិនមែនជាលេខទេ តែជា និន្នាការ។

កំណត់ចំណាំស្មោះត្រង់ពីរបីអំពី benchmark ដែលអនុវត្តចំពោះស៊េរីទាំងមូល៖

• ពេលវេលាមានភាពរំខាន។ ប្រៀបធៀបសមាមាត្រ មិនមែនមីលីវិនាទីពិតប្រាកដទេ ហើយដំណើរការលើសពីម្តង។
• ការដំណើរការលើកដំបូងជារឿយៗយឺតជាង ពីព្រោះ JavaScript engine នៅតែកំពុង optimize កូដរបស់អ្នក។ ធ្វើការងារម្តងទៀត ដូចដែលយើងបានធ្វើជាមួយ loop 100។
• សាកល្បងករណីអាក្រក់បំផុតដោយចេតនា។ ការស្វែងរកធាតុ ចុងក្រោយ បង្ហាញតម្លៃពិតនៃការស្កេនលីនេអ៊ែរ។ ការស្វែងរកធាតុដំបូងធ្វើឲ្យ array ណាក៏មើលទៅលឿនដែរ។

7. រចនាសម្ព័ន្ធគឺជាល្បឿន

Benchmark មុនគឺជាឧទាហរណ៍មួយនៃគំនិតទូទៅ៖ តម្លៃនៃប្រតិបត្តិការអាស្រ័យលើរចនាសម្ព័ន្ធដែលរក្សាទិន្នន័យ។ នេះគឺជាតម្លៃសម្រាប់អ្វីដែលអ្នកប្រើរួចហើយ។ សូមចាត់ទុកនេះជាការមើលជាមុន រចនាសម្ព័ន្ធនីមួយៗមានជំពូករបស់ខ្លួន។

គ្មានជួរឈរណាឈ្នះគ្រប់កន្លែងទេ។ Array ល្អឥតខ្ចោះសម្រាប់ "ឲ្យធាតុទី 5 មកខ្ញុំ" និងសម្រាប់ដើរតាមលំដាប់។ Set ឬ Map ល្អឥតខ្ចោះសម្រាប់ "តើនេះនៅក្នុងនេះទេ?" និង "តើអ្វីទៅជាមួយ key នេះ?"។ ការជ្រើសរើសឲ្យបានល្អមានន័យថាសួរសំណួរបីអំពីបញ្ហារបស់អ្នក៖

1. តើប្រតិបត្តិការអ្វីដែលខ្ញុំនឹងធ្វើ ញឹកញាប់បំផុត៖ អានតាមទីតាំង ស្វែងរកតាមតម្លៃ បន្ថែម លុប ឬដើរកាត់ទាំងអស់តាមលំដាប់?
2. តើ លំដាប់ សំខាន់ទេ? (ចូលមុនចេញមុន? បានតម្រៀប?)
3. តើទិន្នន័យអាច ធំ ប៉ុនណា? សម្រាប់ 20 ធាតុ អ្វីៗក៏ដំណើរការ។ សម្រាប់ 20 លាន រូបរាងសំខាន់។

អ្នកអាចមើលតម្លៃនៃ "លុបចេញពីដើម" ដោយខ្លួនឯង។ កូដនេះលុបធាតុ 100,000 ម្តងមួយៗ ជាដំបូងពីចុង បន្ទាប់មកពីខាងមុខ៖

const fromEnd = Array.from({ length: 100_000 }, (_, i) => i);
let t = performance.now();
while (fromEnd.length > 0) fromEnd.pop();
console.log("pop:  ", (performance.now() - t).toFixed(1), "ms");

const fromFront = Array.from({ length: 100_000 }, (_, i) => i);
t = performance.now();
while (fromFront.length > 0) fromFront.shift();
console.log("shift:", (performance.now() - t).toFixed(1), "ms");

pop:   0.6 ms
shift: 672.8 ms

Array ដូចគ្នា ធាតុ 100,000 ដូចគ្នា ហើយការលុបពីខាងមុខចំណាយពេលយូរជាងប្រហែលមួយពាន់ដងនៅលើម៉ាស៊ីននេះ។ shift ត្រូវរំកិលរាល់ធាតុដែលនៅសល់ទៅឆ្វេងមួយកន្លែង ដូច្នេះវាមានតម្លៃ O(n) រាល់ពេល ហើយ loop នៃពួកវាគឺ O(n^2)។ ជំពូកទី 2 ពន្យល់ហេតុផល ហើយជំពូកទី 5 សាងសង់ queue ដែលចៀសវាងបញ្ហានេះ។

8. ពេលវេលាទល់នឹងអង្គចងចាំ

ការបង្កើនល្បឿនភាគច្រើនចំណាយអង្គចងចាំ។ Map លឿនក្នុងផ្នែកទី 1 ប្រើអង្គចងចាំបន្ថែមដើម្បីរក្សាអតិថិជនគ្រប់គ្នា។ Set ក្នុង benchmark រក្សាច្បាប់ចម្លងទីពីរនៃលេខមួយលាន។ ការដោះដូរនេះហៅថា ពេលវេលាទល់នឹងលំហ (time versus space) ហើយវាលេចឡើងគ្រប់ទីកន្លែង៖

ភាពស្មុគស្មាញនៃលំហ (Space complexity) ប្រើសញ្ញា Big-O ដូចគ្នាដើម្បីពណ៌នាអង្គចងចាំបន្ថែម។ Loop ដែលមាន counter ប្រើលំហ O(1)។ Set ដែលអាចរក្សាគ្រប់ធាតុ input ប្រើ O(n)។

ដូច្នេះចម្លើយស្មោះត្រង់ចំពោះ "តើមួយណាល្អបំផុត?" ស្ទើរតែជានិច្ចគឺ "វាអាស្រ័យលើអ្វីដែលខ្វះខាត"។ ទូរស័ព្ទដែលមានអង្គចងចាំតិចអាចចូលចិត្តកំណែយឺតជាង និងស្តើងជាង។ ម៉ាស៊ីនមេដែលឆ្លើយតបសំណើមួយលានក្នុងមួយនាទីស្ទើរតែប្រាកដជាចូលចិត្តកំណែលឿន។ ការដឹងពីតម្លៃអនុញ្ញាតឲ្យអ្នកជ្រើសរើសដោយចេតនា ជំនួសឲ្យដោយចៃដន្យ។

9. របៀបប្រើស៊េរីនេះ

រាល់ជំពូកធ្វើតាមចង្វាក់ដូចគ្នា ដូច្នេះអ្នកដឹងជានិច្ចថាអ្នកនៅត្រង់ណា៖

1. បញ្ហាពិត។ ហេតុអ្វីរចនាសម្ព័ន្ធមាន ហើយអ្នកជួបវានៅកន្លែងណា។
2. គំនិត។ ពន្យល់ជាមួយឧទាហរណ៍តូចៗ និងលទ្ធផលដែលអ្នកអាចដំណើរការបាន។
3. តារាងតម្លៃ។ Big-O នៃប្រតិបត្តិការនីមួយៗ។
4. បញ្ហាបែបសម្ភាសន៍។ សំណួរធម្មតា ដោះស្រាយជាជំហានៗ។
5. រូបមន្ត។ អ្នកបន្ថែម module និង test ទៅ algolab។
6. សាកល្បងដោយខ្លួនឯង។ លំហាត់ ខ្លះជាបែបសម្ភាសន៍។

គន្លឹះខ្លះដើម្បីទទួលបានអត្ថប្រយោជន៍ច្រើនបំផុតពីវា៖

• វាយកូដ។ កុំ paste។ ការវាយធ្វើឲ្យអ្នកយឺតគ្រប់គ្រាន់ដើម្បីកត់សម្គាល់ថាបន្ទាត់នីមួយៗធ្វើអ្វី។
• ទាយ បន្ទាប់មកដំណើរការ។ មុនដំណើរការឧទាហរណ៍ សរសេរចុះអ្វីដែលអ្នកគិតថាវានឹងបោះពុម្ព។ នៅពេលអ្នកខុស អ្នករៀនបានច្រើនបំផុត។
• គូរវា។ សម្រាប់ array, list, tree និង graph គំនូសព្រាងលឿនៗលើក្រដាសល្អជាងការសម្លឹងមើលកូដ។
• ដំណើរការ test ជាញឹកញាប់។ npm test បន្ទាប់ពីរាល់ការផ្លាស់ប្តូរចាប់កំហុសនៅពេលវានៅតូច។
• ធ្វើលំហាត់។ ការអានអំពីក្បួនដោះស្រាយ និងការអាចសរសេរវាពីឯកសារទទេ គឺជាជំនាញខុសគ្នាខ្លាំង។

គ្រោងមួយទៅពីរម៉ោងក្នុងមួយជំពូក។ លើកដំបូង ត្រូវមានគោលដៅយល់ជាជាងទន្ទេញ។ ភាពស្ទាត់ជំនាញពិតមកពីការជួបគំនិតដូចគ្នាក្នុងបញ្ហាផ្សេងៗគ្នាច្រើន ហើយស៊េរីនេះត្រូវបានសាងសង់ឡើងដើម្បីធ្វើរឿងនោះឲ្យបានពិតប្រាកដ។

10. រូបមន្ត៖ module bench

ដល់ពេលសរសេរ module ដំបូង។ បង្កើត src/bench.ts៖

// src/bench.ts

export interface Timing<T> {
  label: string;
  ms: number;
  result: T;
}

// Run fn once and report how long it took.
export function time<T>(fn: () => T, label = "task"): Timing<T> {
  const start = performance.now();
  const result = fn();
  const ms = performance.now() - start;
  return { label, ms, result };
}

// O(n): look at items one by one.
export function linearSearch<T>(items: T[], target: T): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

// O(n^2): compare every pair.
export function hasDuplicateSlow(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

// O(n): remember what we have seen in a Set.
export function hasDuplicateFast(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

time គឺ generic៖ <T> មានន័យថា "ប្រភេទអ្វីក៏ដោយដែល fn return field result មានប្រភេទដូចគ្នានោះ"។ linearSearch return index នៃការផ្គូផ្គងដំបូង ឬ -1 នៅពេលគោលដៅបាត់ ដែលជាអនុសញ្ញាដូចគ្នានឹង Array.prototype.indexOf។

ឥឡូវបន្ថែម test។ បង្កើត src/bench.test.ts៖

// src/bench.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import {
  time,
  linearSearch,
  hasDuplicateSlow,
  hasDuplicateFast,
} from "./bench.ts";

test("linearSearch finds the index or returns -1", () => {
  assert.equal(linearSearch([5, 7, 9], 9), 2);
  assert.equal(linearSearch([5, 7, 9], 4), -1);
});

test("both duplicate checkers agree", () => {
  const cases = [[], [1], [1, 2, 3], [1, 2, 1], [4, 4]];
  for (const c of cases) {
    assert.equal(hasDuplicateSlow(c), hasDuplicateFast(c));
  }
  assert.equal(hasDuplicateFast([1, 2, 1]), true);
});

test("time returns the result and a non-negative duration", () => {
  const t = time(() => 2 + 2, "add");
  assert.equal(t.result, 4);
  assert.equal(t.label, "add");
  assert.ok(t.ms >= 0);
});

ដំណើរការ test៖

npm test

អ្នកគួរឃើញ test ទាំងបីជាប់ (បន្ទាត់ចុងក្រោយនៃរបាយការណ៍បង្ហាញ # pass 3 និង # fail 0)។ ដំណើរការ type checker ផងដែរជាមួយ npm run typecheck។ វាមិនបោះពុម្ពអ្វីទេនៅពេលអ្វីៗល្អ។

ឥឡូវជំនួស demo.ts ដោយកំណែដែលប្រើ module៖

// demo.ts
import {
  time,
  linearSearch,
  hasDuplicateSlow,
  hasDuplicateFast,
} from "./src/bench.ts";

console.log("--- bench ---");
const arr = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const set = new Set(arr);
const last = arr[arr.length - 1];

console.log(linearSearch(arr, last)); // 999999
console.log(linearSearch(arr, 7));    // -1 (7 is odd, so it is missing)

const withArray = time(() => {
  for (let i = 0; i < 100; i++) arr.includes(last);
}, "includes x100");
const withSet = time(() => {
  for (let i = 0; i < 100; i++) set.has(last);
}, "set.has x100");

for (const r of [withArray, withSet]) {
  console.log(r.label.padEnd(16), r.ms.toFixed(3), "ms"); // varies
}
console.log("set faster than array:", withSet.ms < withArray.ms); // true

const small = Array.from({ length: 20_000 }, (_, i) => i);
const slow = time(() => hasDuplicateSlow(small), "slow dup check");
const fast = time(() => hasDuplicateFast(small), "fast dup check");
console.log(slow.label.padEnd(16), slow.ms.toFixed(1), "ms"); // about 75 ms
console.log(fast.label.padEnd(16), fast.ms.toFixed(2), "ms"); // about 1 ms
console.log(slow.result, fast.result); // false false

ដំណើរការ npx tsx demo.ts។ លទ្ធផលស្វែងរកទាំងពីរ បន្ទាត់ true និងបន្ទាត់ false false មានស្ថេរភាព។ លេខមីលីវិនាទីនឹងខុសគ្នាពីម៉ាស៊ីនមួយទៅម៉ាស៊ីនមួយ ប៉ុន្តែលំដាប់នឹងដូចគ្នា៖ Set និងឧបករណ៍ពិនិត្យស្ទួនដែលផ្អែកលើ Set លឿនជាងឆ្ងាយ។ Array នៃលេខផ្សេងគ្នា 20,000 របស់យើងមិនមានធាតុស្ទួនទេ ដូច្នេះឧបករណ៍ពិនិត្យទាំងពីរធ្វើការងារពេញលេញ ហើយ return false ទាំងពីរ។

11. សាកល្បងដោយខ្លួនឯង

1. រកមើល loop ដែលលាក់។ មួយណាខាងក្រោមជា O(n^2) ហើយហេតុអ្វី? (a) for (const x of a) if (b.includes(x)) count++; (b) for (const x of a) if (setB.has(x)) count++; (c) a.map(x => x * 2).filter(x => x > 10)។ សន្មត់ថា a និង b ទាំងពីរមាន n ធាតុ។
2. រកចំណុចស្មើគ្នា (break-even)។ ដោយប្រើ time ពី src/bench.ts ប្រៀបធៀប hasDuplicateSlow និង hasDuplicateFast លើ array នៃលេខផ្សេងគ្នា 100, 1,000 និង 10,000។ នៅទំហំប៉ុនណាដែលកំណែ Set ចាប់ផ្តើមឈ្នះយ៉ាងច្បាស់? តើ Set ធ្លាប់យឺតជាងទេ?
3. ជួសជុលទំព័រ orders។ សរសេរ attachNames និង attachNamesFast ពីផ្នែកទី 1 ជា function ពិតក្នុង src/orders.ts។ បង្កើតអតិថិជន 2,000 និងការបញ្ជាទិញ 20,000 ដោយ loop ហើយវាស់ពេលទាំងពីរ។ ពិនិត្យថាពួកវាផលិតលទ្ធផលស្មើគ្នាដោយ assert.deepEqual។
4. វាស់ shift។ ធ្វើតេស្ត pop ទល់នឹង shift ម្តងទៀតជាមួយ 10,000 ហើយបន្ទាប់មក 100,000 ធាតុ។ នៅពេលទំហំកើនឡើង 10 ដង តើ shift យឺតជាងប៉ុន្មានដង? តើវាត្រូវនឹង O(n^2) សម្រាប់ loop ទាំងមូលទេ?
5. បែបសម្ភាសន៍៖ តម្លៃដំបូងដែលស្ទួន។ ដោយមាន array នៃលេខ ចូល return តម្លៃដំបូងដែលលេចឡើងពីរដងនៅពេលអានពីឆ្វេងទៅស្តាំ ឬ undefined ប្រសិនបើគ្មានអ្វីស្ទួន។ សម្រាប់ [2, 5, 1, 2, 3, 5] ចម្លើយគឺ 2។ ជាដំបូងសរសេរកំណែ O(n^2) ដែលច្បាស់ បន្ទាប់មកកំណែ O(n) ហើយបញ្ជាក់អង្គចងចាំបន្ថែមដែលម្នាក់ៗប្រើ។
6. បែបសម្ភាសន៍៖ បានតម្រៀបឬអត់។ មាននរណាម្នាក់និយាយថា "ខ្ញុំនឹងតម្រៀបបញ្ជី បន្ទាប់មក binary search វា ពីព្រោះ binary search គឺ O(log n) ហើយនោះឈ្នះ O(n)។" ប្រសិនបើបញ្ជីត្រូវបានស្វែងរកតែម្តង តើពួកគេត្រូវទេ? ចុះបើវាត្រូវបានស្វែងរកដប់ពាន់ដង? ពន្យល់ជាពីរប្រយោគ ដោយប្រើតម្លៃនៃការតម្រៀប។

ឥឡូវអ្នកដឹងថាហេតុអ្វីស៊េរីនេះមាន៖ ការរៀបចំទិន្នន័យរបស់អ្នកកំណត់ថាកូដរបស់អ្នកដំណើរការលឿនប៉ុនណា ហើយ Big-O គឺជាភាសាសម្រាប់និយាយអំពីវា។ រចនាសម្ព័ន្ធប្រចាំថ្ងៃដំបូងគឺជារចនាសម្ព័ន្ធដែលអ្នកប្រើច្រើនបំផុត។ បន្ទាប់គឺ Array និង String ដែលយើងមើលរបៀបដែល array រស់នៅក្នុងអង្គចងចាំ ហេតុអ្វី shift យឺត និងបច្ចេកទេសបី (two pointers, sliding window និង prefix sums) ដែលដោះស្រាយបញ្ហាសម្ភាសន៍ជាច្រើន។