ការដោះស្រាយបញ្ហាពីការសំភាសន៍របស់ Google នៅក្នុង JavaScript: 4 វិធីផ្សេងគ្នា

ពេល​ខ្ញុំ​កំពុង​សិក្សា​ការ​អនុវត្ត​ក្បួន​ដោះស្រាយ ខ្ញុំ​បាន​ជួប​រឿង​នេះ។ នេះ​ជា​វីដេអូ​នៃ​ការ​សម្ភាស​របស់ Google ។. វាមិនត្រឹមតែផ្តល់នូវគំនិតអំពីរបៀបដែលការសម្ភាសន៍ត្រូវបានធ្វើឡើងនៅសាជីវកម្មបច្ចេកវិជ្ជាធំៗប៉ុណ្ណោះទេ ប៉ុន្តែថែមទាំងអនុញ្ញាតឱ្យអ្នកយល់ពីរបៀបដែលបញ្ហាក្បួនដោះស្រាយត្រូវបានដោះស្រាយប្រកបដោយប្រសិទ្ធភាពតាមដែលអាចធ្វើទៅបាន។

អត្ថបទនេះគឺជាប្រភេទនៃការភ្ជាប់ជាមួយវីដេអូ។ នៅក្នុងនោះ ខ្ញុំផ្តល់យោបល់លើដំណោះស្រាយទាំងអស់ដែលបានបង្ហាញ បូករួមទាំងកំណែផ្ទាល់ខ្លួនរបស់ខ្ញុំនៃដំណោះស្រាយនៅក្នុង JavaScript ។ nuances នៃ algorithm នីមួយៗ ក៏ត្រូវបានពិភាក្សាផងដែរ។

យើងរំលឹក៖ សម្រាប់អ្នកអានទាំងអស់នៃ "Habr" - ការបញ្ចុះតម្លៃ 10 rubles នៅពេលចុះឈ្មោះក្នុងវគ្គសិក្សា Skillbox ណាមួយដោយប្រើលេខកូដផ្សព្វផ្សាយ "Habr" ។

Skillbox ណែនាំ៖ វគ្គសិក្សាជាក់ស្តែង "អ្នកអភិវឌ្ឍន៍ចល័ត PRO".

ការបង្កើតបញ្ហា

យើង​ត្រូវ​បាន​ផ្ដល់​អារេ​ដែល​បាន​បញ្ជា​ទិញ និង​តម្លៃ​ជាក់លាក់។ បន្ទាប់មកវាត្រូវបានស្នើឱ្យបង្កើតអនុគមន៍ដែលត្រឡប់ពិត ឬមិនពិត អាស្រ័យលើថាតើផលបូកនៃលេខទាំងពីរនៅក្នុងអារេអាចស្មើនឹងតម្លៃដែលបានផ្តល់ឱ្យ។

ម្យ៉ាងវិញទៀត តើមានចំនួនគត់ពីរនៅក្នុងអារេ x និង y ដែលនៅពេលបូកបញ្ចូលគ្នាស្មើនឹងតម្លៃដែលបានបញ្ជាក់ដែរឬទេ?

ឧទាហរណ៍ ក

ប្រសិនបើយើងផ្តល់អារេ [1, 2, 4, 9] ហើយតម្លៃគឺ 8 នោះមុខងារនឹងត្រឡប់មិនពិត ពីព្រោះគ្មានលេខពីរក្នុងអារេអាចបន្ថែមរហូតដល់ 8 ទេ។

ឧទាហរណ៍ ខ

ប៉ុន្តែប្រសិនបើវាជាអារេ [1, 2, 4, 4] ហើយតម្លៃគឺ 8 នោះមុខងារគួរតែត្រឡប់ពិតព្រោះ 4 + 4 = 8 ។

ដំណោះស្រាយទី 1: កម្លាំងសាហាវ

ភាពស្មុគស្មាញពេលវេលា៖ O(N²)។
ភាពស្មុគស្មាញនៃលំហ៖ O(1) ។

អត្ថន័យច្បាស់បំផុតគឺការប្រើរង្វិលជុំដែលដាក់ជាគូ។

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };
  return false;
};

ដំណោះស្រាយនេះមិនមានប្រសិទ្ធភាពទេព្រោះវាពិនិត្យមើលរាល់ផលបូកដែលអាចធ្វើបាននៃធាតុពីរនៅក្នុងអារេ ហើយថែមទាំងប្រៀបធៀបរាល់គូនៃសន្ទស្សន៍ពីរដងផងដែរ។ (ឧទាហរណ៍ នៅពេលដែល i = 1 និង j = 2 ពិតជាដូចគ្នានឹងការប្រៀបធៀបជាមួយ i = 2 និង j = 1 ប៉ុន្តែនៅក្នុងដំណោះស្រាយនេះ យើងសាកល្បងជម្រើសទាំងពីរ)។

ដោយសារតែដំណោះស្រាយរបស់យើងប្រើគូនៃ nested សម្រាប់រង្វិលជុំ, វាគឺបួនជ្រុងជាមួយនឹងភាពស្មុគស្មាញពេលវេលា O (N²) ។

ដំណោះស្រាយទី 2: ការស្វែងរកប្រព័ន្ធគោលពីរ

ភាពស្មុគស្មាញនៃពេលវេលា៖ O(Nlog(N)) ។
ភាពស្មុគស្មាញនៃលំហ៖ O(1).

ដោយសារអារេត្រូវបានតម្រៀប យើងអាចស្វែងរកដំណោះស្រាយដោយប្រើការស្វែងរកប្រព័ន្ធគោលពីរ។ នេះគឺជាក្បួនដោះស្រាយដ៏មានប្រសិទ្ធភាពបំផុតសម្រាប់អារេដែលបានបញ្ជាទិញ។ ការស្វែងរកប្រព័ន្ធគោលពីរមានពេលវេលាដំណើរការ O(log(N))។ ទោះយ៉ាងណាក៏ដោយ អ្នកនៅតែត្រូវប្រើ a for loop ដើម្បីពិនិត្យមើលធាតុនីមួយៗធៀបនឹងតម្លៃផ្សេងទៀតទាំងអស់។

នេះជាអ្វីដែលដំណោះស្រាយអាចមើលទៅ។ ដើម្បីធ្វើឱ្យអ្វីៗមានភាពច្បាស់លាស់ យើងប្រើមុខងារដាច់ដោយឡែក ដើម្បីគ្រប់គ្រងការស្វែងរកប្រព័ន្ធគោលពីរ។ ហើយ​ក៏​មុខងារ removeIndex() ដែល​ត្រឡប់​កំណែ​នៃ​អារេ​ដក​លិបិក្រម​ដែល​បាន​ផ្តល់។

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  };
  return false;
};
 
const removeIndex = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
 
const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2); 
  while (start < end) {
    if (val < arr[pivot]) {
      end = pivot - 1;
    } else if (val > arr[pivot]) {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  };
  return false;
};

ក្បួនដោះស្រាយចាប់ផ្តើមពីសន្ទស្សន៍ [0] ។ បន្ទាប់មកវាបង្កើតកំណែនៃអារេដែលមិនរាប់បញ្ចូលលិបិក្រមដំបូង ហើយប្រើការស្វែងរកប្រព័ន្ធគោលពីរ ដើម្បីមើលថាតើតម្លៃណាមួយដែលនៅសល់អាចត្រូវបានបន្ថែមទៅអារេដើម្បីបង្កើតផលបូកដែលចង់បាន។ សកម្មភាពនេះត្រូវបានអនុវត្តម្តងសម្រាប់ធាតុនីមួយៗនៅក្នុងអារេ។

សម្រាប់រង្វិលជុំខ្លួនវានឹងមានភាពស្មុគស្មាញពេលវេលាលីនេអ៊ែរនៃ O(N) ប៉ុន្តែនៅខាងក្នុងសម្រាប់រង្វិលជុំយើងធ្វើការស្វែងរកប្រព័ន្ធគោលពីរ ដែលផ្តល់នូវភាពស្មុគស្មាញពេលវេលាសរុបនៃ O(Nlog(N))។ ដំណោះស្រាយនេះគឺល្អជាងកំណែមុន ប៉ុន្តែនៅតែមានកន្លែងសម្រាប់កែលម្អ

ដំណោះស្រាយទី 3: ពេលវេលាលីនេអ៊ែរ

ភាពស្មុគស្មាញនៃពេលវេលា៖ O(N) ។
ភាពស្មុគស្មាញនៃលំហ៖ O(1) ។

ឥឡូវនេះយើងនឹងដោះស្រាយបញ្ហាដោយចងចាំថាអារេត្រូវបានតម្រៀប។ ដំណោះស្រាយគឺត្រូវយកលេខពីរ៖ មួយនៅដើម និងមួយនៅចុងបញ្ចប់។ ប្រសិនបើលទ្ធផលខុសពីតម្រូវការចាំបាច់ បន្ទាប់មកប្តូរចំណុចចាប់ផ្តើម និងបញ្ចប់។

នៅទីបំផុត យើងនឹងជួបតម្លៃដែលចង់បាន ហើយត្រឡប់ពិត ឬចំណុចចាប់ផ្តើម និងចុងបញ្ចប់នឹងបញ្ចូលគ្នា ហើយត្រឡប់មិនពិត។

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};

ឥឡូវនេះអ្វីគ្រប់យ៉ាងគឺល្អ ដំណោះស្រាយហាក់ដូចជាល្អប្រសើរបំផុត។ ប៉ុន្តែតើអ្នកណាអាចធានាថាអារេត្រូវបានបញ្ជា?

ចុះយ៉ាងណាវិញ?

នៅក្រឡេកមើលដំបូង យើងអាចបញ្ជាទិញអារេជាមុនសិន ហើយបន្ទាប់មកប្រើដំណោះស្រាយខាងលើ។ ប៉ុន្តែ តើ​វា​នឹង​ប៉ះពាល់​ដល់​ពេល​ប្រតិបត្តិ​យ៉ាង​ណា?

ក្បួនដោះស្រាយដ៏ល្អបំផុតគឺតម្រៀបរហ័សជាមួយនឹងភាពស្មុគស្មាញពេលវេលា O (Nlog (N)) ។ ប្រសិនបើយើងប្រើវានៅក្នុងដំណោះស្រាយដ៏ល្អបំផុតរបស់យើង វានឹងផ្លាស់ប្តូរដំណើរការរបស់វាពី O(N) ទៅ O(Nlog(N))។ តើវាអាចទៅរួចទេក្នុងការស្វែងរកដំណោះស្រាយលីនេអ៊ែរជាមួយនឹងអារេដែលមិនមានលំដាប់?

4 ដំណោះស្រាយ។

ភាពស្មុគស្មាញនៃពេលវេលា៖ O(N) ។
ភាពស្មុគស្មាញនៃលំហ៖ O(N) ។

បាទ មានដំណោះស្រាយលីនេអ៊ែរ ដើម្បីធ្វើដូច្នេះ យើងត្រូវបង្កើតអារេថ្មីដែលមានបញ្ជីនៃការប្រកួតដែលយើងកំពុងស្វែងរក។ ការដោះដូរនៅទីនេះគឺការប្រើប្រាស់អង្គចងចាំកាន់តែច្រើន៖ វាជាដំណោះស្រាយតែមួយគត់នៅក្នុងក្រដាសដែលមានភាពស្មុគស្មាញក្នុងលំហធំជាង O(1)។

ប្រសិនបើតម្លៃដំបូងនៃអារេដែលបានផ្តល់ឱ្យគឺ 1 ហើយតម្លៃស្វែងរកគឺ 8 យើងអាចបន្ថែមតម្លៃ 7 ទៅអារេ "តម្លៃស្វែងរក" ។

បន្ទាប់មក នៅពេលយើងដំណើរការធាតុនីមួយៗនៃអារេ យើងអាចពិនិត្យមើលអារេនៃ "តម្លៃស្វែងរក" ហើយមើលថាតើមួយក្នុងចំណោមពួកវាស្មើនឹងតម្លៃរបស់យើងឬអត់។ បើបាទ/ចាស ត្រឡប់ពិត។

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

មូលដ្ឋាននៃដំណោះស្រាយគឺសម្រាប់រង្វិលជុំ ដែលដូចដែលយើងបានឃើញខាងលើ មានភាពស្មុគស្មាញនៃពេលវេលាលីនេអ៊ែរនៃ O(N)។

ផ្នែកដដែលៗទីពីរនៃមុខងាររបស់យើងគឺ Array.prototype.include() ដែលជាវិធីសាស្ត្រ JavaScript ដែលនឹងត្រឡប់ពិត ឬមិនពិត អាស្រ័យលើថាតើអារេមានតម្លៃដែលបានផ្តល់ឱ្យ។

ដើម្បីស្វែងយល់ពីភាពស្មុគស្មាញនៃពេលវេលារបស់ Array.prototype.includes() យើងអាចមើល polyfill ដែលផ្តល់ដោយ MDN (និងសរសេរជា JavaScript) ឬប្រើវិធីសាស្រ្តក្នុងកូដប្រភពនៃ JavaScript engine ដូចជា Google V8 (C++)។

// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
  Object.defineProperty(Array.prototype, 'includes', {
    value: function(valueToFind, fromIndex) {
 
      if (this == null) {
        throw new TypeError('"this" is null or not defined');
      }
 
      // 1. Let O be ? ToObject(this value).
      var o = Object(this);
 
      // 2. Let len be ? ToLength(? Get(O, "length")).
      var len = o.length >>> 0;
 
      // 3. If len is 0, return false.
      if (len === 0) {
        return false;
      }
 
      // 4. Let n be ? ToInteger(fromIndex).
      //    (If fromIndex is undefined, this step produces the value 0.)
      var n = fromIndex | 0;
 
      // 5. If n ≥ 0, then
      //  a. Let k be n.
      // 6. Else n < 0,
      //  a. Let k be len + n.
      //  b. If k < 0, let k be 0.
      var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
 
      function sameValueZero(x, y) {
        return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
      }
 
      // 7. Repeat, while k < len
      while (k < len) {
        // a. Let elementK be the result of ? Get(O, ! ToString(k)).
        // b. If SameValueZero(valueToFind, elementK) is true, return true.
        if (sameValueZero(o[k], valueToFind)) {
          return true;
        }
        // c. Increase k by 1.
        k++;
      }
 
      // 8. Return false
      return false;
    }
  });
}

នៅទីនេះផ្នែកដដែលៗនៃ Array.prototype.include() គឺជា while loop នៅក្នុងជំហានទី 7 ដែល (ស្ទើរតែ) ឆ្លងកាត់ប្រវែងទាំងមូលនៃអារេដែលបានផ្តល់ឱ្យ។ នេះមានន័យថាភាពស្មុគស្មាញនៃពេលវេលារបស់វាក៏ជាលីនេអ៊ែរផងដែរ។ ជាការប្រសើរណាស់ ដោយសារវាតែងតែជាជំហានមួយនៅពីក្រោយអារេចម្បងរបស់យើង ភាពស្មុគស្មាញនៃពេលវេលាគឺ O (N + (N - 1)) ។ ដោយប្រើ Big O Notation យើងសម្រួលវាទៅជា O(N) - ព្រោះវាជា N ដែលមានឥទ្ធិពលខ្លាំងបំផុតនៅពេលបង្កើនទំហំបញ្ចូល។

ទាក់ទងនឹងភាពស្មុគស្មាញផ្នែកលំហ អារេបន្ថែមគឺត្រូវការជាចាំបាច់ដែលប្រវែងរបស់វាឆ្លុះបញ្ចាំងពីអារេដើម (ដកមួយ បាទ/ចាស ប៉ុន្តែវាអាចត្រូវបានគេមិនអើពើ) ដែលបណ្តាលឱ្យមានភាពស្មុគស្មាញផ្នែកលំហ O(N)។ ជាការប្រសើរណាស់ ការបង្កើនការប្រើប្រាស់អង្គចងចាំធានានូវប្រសិទ្ធភាពអតិបរមានៃក្បួនដោះស្រាយ។

ខ្ញុំសង្ឃឹមថាអ្នករកឃើញអត្ថបទមានប្រយោជន៍ ជាការបន្ថែមចំពោះការសម្ភាសន៍វីដេអូរបស់អ្នក។ វាបង្ហាញថាបញ្ហាសាមញ្ញមួយអាចត្រូវបានដោះស្រាយតាមវិធីផ្សេងៗគ្នាជាមួយនឹងបរិមាណផ្សេងគ្នានៃធនធានដែលបានប្រើ (ពេលវេលា ការចងចាំ) ។

Skillbox ណែនាំ៖

• បានអនុវត្តវគ្គសិក្សាតាមអ៊ីនធឺណិត "អ្នកវិភាគទិន្នន័យ Python".
• វគ្គសិក្សាតាមអ៊ីនធឺណិត "អ្នកអភិវឌ្ឍន៍មុខជំនាញ".
• វគ្គសិក្សាជាក់ស្តែងឆ្នាំ "អ្នកអភិវឌ្ឍន៍ PHP ពី 0 ដល់ PRO".

ប្រភព: www.habr.com