በጃቫስክሪፕት የጎግል ቃለ መጠይቅ ችግር መፍታት፡ 4 የተለያዩ መንገዶች

የአልጎሪዝም አፈጻጸምን ሳጠና ይህን አጋጥሞኝ ነበር። ይህ የጎግል አስመሳይ ቃለ መጠይቅ ቪዲዮ ነው።. በትልልቅ የቴክኖሎጂ ኮርፖሬሽኖች ውስጥ ቃለ-መጠይቆች እንዴት እንደሚካሄዱ ሀሳብን ብቻ ሳይሆን የአልጎሪዝም ችግሮች በተቻለ መጠን በብቃት እንዴት እንደሚፈቱ እንዲገነዘቡ ያስችልዎታል።

ይህ ጽሑፍ ከቪዲዮው ጋር አብሮ የሚሄድ አይነት ነው። በእሱ ውስጥ በሁሉም የሚታዩ መፍትሄዎች ላይ አስተያየቶችን አቀርባለሁ, በተጨማሪም የራሴን የመፍትሄው እትም በጃቫ ስክሪፕት. የእያንዳንዱ አልጎሪዝም ልዩነቶችም ተብራርተዋል.

እኛ እናስታውስዎታለን- ለሁሉም የ "ሀብር" አንባቢዎች - የ "Habr" የማስተዋወቂያ ኮድን በመጠቀም በማንኛውም የ Skillbox ኮርስ ውስጥ ሲመዘገቡ የ 10 ሩብልስ ቅናሽ.

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 ጋር ሲነጻጸር ተመሳሳይ ነው, ነገር ግን በዚህ መፍትሄ ሁለቱንም አማራጮች እንሞክራለን).

ምክንያቱም የእኛ መፍትሔ ለ loops ጥንድ ጎጆዎችን ስለሚጠቀም፣ ከ O(N²) የጊዜ ውስብስብነት ጋር ኳድራቲክ ነው።

መፍትሄ 2: ሁለትዮሽ ፍለጋ

የጊዜ ውስብስብነት፡ O(Nlog(N))።
የቦታ ውስብስብነት፡ O(1).

ድርድሮች ስለታዘዙ፣ ሁለትዮሽ ፍለጋን በመጠቀም መፍትሄ መፈለግ እንችላለን። ይህ ለታዘዙ ድርድሮች በጣም ቀልጣፋው ስልተ ቀመር ነው። የሁለትዮሽ ፍለጋ ራሱ የO(ሎግ(N)) ጊዜ አለው። ሆኖም ግን፣ አሁንም እያንዳንዱን ንጥረ ነገር ከሌሎች እሴቶች ጋር ለመፈተሽ ለ loop መጠቀም ያስፈልግዎታል።

መፍትሄው ምን እንደሚመስል እነሆ። ነገሮችን ግልጽ ለማድረግ፣ ሁለትዮሽ ፍለጋን ለመቆጣጠር የተለየ ተግባር እንጠቀማለን። እና እንዲሁም የማስወገድ ኢንዴክስ() ተግባር፣ ከተሰጠው ኢንዴክስ ሲቀነስ የድርድርውን እትም ይመልሳል።

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] ይጀምራል። ከዚያም የመጀመሪያውን ኢንዴክስ ሳይጨምር የድርድር ሥሪት ይፈጥራል እና የተፈለገውን ድምር ለማምረት ቀሪዎቹ እሴቶች ወደ ድርድር መጨመር ይቻል እንደሆነ ለማየት ሁለትዮሽ ፍለጋን ይጠቀማል። ይህ እርምጃ በድርድር ውስጥ ላለው እያንዳንዱ አካል አንድ ጊዜ ይከናወናል።

የ loop ራሱ የO(N) የመስመር ጊዜ ውስብስብነት ይኖረዋል፣ ነገር ግን በ loop ውስጥ ሁለትዮሽ ፍለጋ እናደርጋለን፣ ይህም አጠቃላይ የ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)) ፈጣን ድርድር ነው። በእኛ ምርጥ መፍትሄ ከተጠቀምንበት አፈፃፀሙን ከኦ(N) ወደ ኦ(Nlog(N)) ይቀይራል። ካልታዘዘ ድርድር ጋር መስመራዊ መፍትሄ ማግኘት ይቻላል?

የ 4 መፍትሄ

የጊዜ ውስብስብነት፡ O(N)።
የቦታ ውስብስብነት፡ O(N)

አዎ፣ መስመራዊ መፍትሄ አለ፤ ይህንን ለማድረግ የምንፈልገውን የተዛማጆች ዝርዝር የያዘ አዲስ አደራደር መፍጠር አለብን። እዚህ ያለው የንግድ ልውውጥ የበለጠ የማህደረ ትውስታ አጠቃቀም ነው፡ ከኦ(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;
};

የመፍትሄው መሰረት ለ loop ነው, እሱም ከላይ እንዳየነው, የ O (N) የመስመር ጊዜ ውስብስብነት አለው.

ሁለተኛው የተግባራችን ተደጋጋሚ ክፍል Array.prototype.include() ነው፣ የጃቫ ስክሪፕት ዘዴ ድርድር የተሰጠውን እሴት እንደያዘው ላይ በመመስረት እውነት ወይም ሀሰት የሚመለስ ነው።

የ Array.prototype.includes()ን የጊዜ ውስብስብነት ለማወቅ በኤምዲኤን የቀረበውን (እና በጃቫስክሪፕት የተጻፈውን) ፖሊፊል ማየት እንችላለን ወይም በጃቫ ስክሪፕት ሞተር ምንጭ ኮድ እንደ 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() ተደጋጋሚ ክፍል በደረጃ 7 ላይ ያለው የጊዜ ዑደት ነው (ከሞላ ጎደል) የተሰጠውን ድርድር ሙሉውን ርዝመት የሚያልፍ። ይህ ማለት የጊዜ ውስብስብነቱም መስመራዊ ነው። ደህና፣ ሁልጊዜ ከዋናው ድርደራችን አንድ እርምጃ በኋላ ስለሆነ፣ የጊዜ ውስብስብነቱ O (N + (N - 1)) ነው። ቢግ ኦ ኖቴሽን በመጠቀም፣ ወደ O(N) እናቀላለን - ምክንያቱም የግብአት መጠኑን ሲጨምር ትልቁ ተጽእኖ ያለው N ነው።

የቦታ ውስብስብነትን በተመለከተ፣ ርዝመቱ የመጀመሪያውን ድርድር የሚያንጸባርቅ ተጨማሪ ድርድር ያስፈልጋል (አንድ ሲቀነስ አዎ፣ ግን ችላ ሊባል ይችላል) ይህም የ O(N) የቦታ ውስብስብነት ያስከትላል። ደህና ፣ የማህደረ ትውስታ አጠቃቀም ከፍተኛውን የአልጎሪዝም ውጤታማነት ያረጋግጣል።

ጽሑፉ ለቪዲዮ ቃለ መጠይቁ እንደ ማሟያ ጠቃሚ ሆኖ እንዳገኙት ተስፋ አደርጋለሁ። ቀላል ችግር በተለያዩ መንገዶች በተለያየ መጠን ጥቅም ላይ የዋለ (ጊዜ, ማህደረ ትውስታ) በመጠቀም መፍታት እንደሚቻል ያሳያል.

Skillbox ይመክራል፡

• በመስመር ላይ ኮርስ ተተግብሯል "Python ውሂብ ተንታኝ".
• የመስመር ላይ ኮርስ "የሙያ ግንባር ገንቢ".
• ተግባራዊ ዓመት ኮርስ "PHP ገንቢ ከ 0 ወደ PRO".

ምንጭ: hab.com