Þegar ég var að kynna mér frammistöðu reiknirita rakst ég á þetta . Það gefur ekki aðeins hugmynd um hvernig viðtöl eru tekin hjá stórum tæknifyrirtækjum, heldur gerir það þér einnig kleift að skilja hvernig reiknirit vandamál eru leyst á eins skilvirkan hátt og mögulegt er.
Þessi grein er eins konar fylgifiskur myndbandsins. Þar gef ég athugasemdir við allar sýndar lausnir, auk mína eigin útgáfu af lausninni í JavaScript. Einnig er fjallað um blæbrigði hvers reiknirits.
Við minnum á: fyrir alla Habr lesendur - 10 rúblur afsláttur þegar þú skráir þig á hvaða Skillbox námskeið sem er með því að nota Habr kynningarkóðann.
Skillbox mælir með: Verklegt námskeið .
Samsetning vandans
Okkur er gefið skipað fylki og ákveðið gildi. Það er síðan beðið um að búa til fall sem skilar satt eða ósatt eftir því hvort summa einhverra tveggja talna í fylkinu getur jafngilt tilteknu gildi.
Með öðrum orðum, eru tvær heiltölur í fylkinu, x og y, sem þegar þær eru lagðar saman jafngilda tilgreindu gildi?
Dæmi A
Ef okkur er gefið fylki [1, 2, 4, 9] og gildið er 8, mun fallið skila false því engar tvær tölur í fylkinu geta lagt saman 8.
Dæmi B
En ef það er fylki [1, 2, 4, 4] og gildið er 8, ætti fallið að skila satt vegna þess að 4 + 4 = 8.
Lausn 1: grimmur kraftur
Tímaflæki: O(N²).
Flækjustig rýmis: O(1).
Augljósasta merkingin er að nota par af hreiðum lykkjum.
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;
};Þessi lausn er ekki skilvirk vegna þess að hún athugar allar mögulegar summu tveggja þátta í fylkinu og ber einnig saman hvert par af vísitölum tvisvar. (Til dæmis, þegar i = 1 og j = 2 er í raun það sama og að bera saman við i = 2 og j = 1, en í þessari lausn reynum við báða valkostina).
Vegna þess að lausnin okkar notar par af hreiðum fyrir lykkjur, er hún ferningslaga með O(N²) tímaflækju.
Lausn 2: Tvöfaldur leit
Tímaflæki: O(Nlog(N)).
Flækjustig rýmis: O(1).
Þar sem fylkin eru röðuð getum við leitað að lausn með tvíundarleit. Þetta er skilvirkasta reikniritið fyrir raðað fylki. Tvöfaldur leit sjálft hefur keyrslutíma O(log(N)). Hins vegar þarftu samt að nota for lykkju til að athuga hvern þátt gegn öllum öðrum gildum.
Svona gæti lausn litið út. Til að gera hlutina á hreinu notum við sérstaka aðgerð til að stjórna tvíundarleit. Og líka removeIndex() aðgerðin, sem skilar útgáfu fylkisins að frádreginni vísitölu.
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;
};Reikniritið byrjar á vísitölu [0]. Það býr síðan til útgáfu af fylkinu að undanskildum fyrstu vísitölunni og notar tvíundarleit til að sjá hvort hægt sé að bæta einhverju af gildunum sem eftir eru við fylkið til að framleiða þá summu sem óskað er eftir. Þessi aðgerð er framkvæmd einu sinni fyrir hvern þátt í fylkinu.
For-lykkjan sjálf mun hafa línulega tímaflækjuna O(N), en inni í for-lykkjunni gerum við tvíundarleit, sem gefur heildartímaflækjuna O(Nlog(N)). Þessi lausn er betri en sú fyrri, en enn má gera betur.
Lausn 3: Línulegur tími
Tímaflæki: O(N).
Flækjustig rýmis: O(1).
Nú munum við leysa vandamálið, muna að fylkið er raðað. Lausnin er að taka tvær tölur: eina í upphafi og eina í lokin. Ef niðurstaðan er frábrugðin þeirri sem krafist er skaltu breyta upphafs- og endapunktum.
Að lokum munum við annað hvort lenda í æskilegu gildi og skila satt, eða upphafs- og endapunktar munu renna saman og skila ósatt.
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;
};
Nú er allt í lagi, lausnin virðist vera ákjósanleg. En hver getur tryggt að fylkið hafi verið pantað?
Hvað þá?
Við fyrstu sýn hefðum við einfaldlega getað pantað fylkið fyrst og notað síðan lausnina hér að ofan. En hvaða áhrif mun þetta hafa á framkvæmdartímann?
Besta reikniritið er quicksort með tímaflækju O (Nlog (N)). Ef við notum það í bestu lausninni okkar mun það breyta frammistöðu sinni úr O(N) í O(Nlog(N)). Er hægt að finna línulega lausn með óraðaðri fylki?
4 Lausn
Tímaflæki: O(N).
Flækjustig rýmis: O(N).
Já, það er til línuleg lausn; til að gera þetta þurfum við að búa til nýtt fylki sem inniheldur lista yfir samsvörun sem við erum að leita að. Málið hér er meiri minnisnotkun: það er eina lausnin í blaðinu með flókið rými sem er meira en O(1).
Ef fyrsta gildi tiltekins fylkis er 1 og leitargildið er 8, getum við bætt gildinu 7 við "leitargildi" fylkið.
Síðan, þegar við vinnum úr hverjum þætti fylkisins, getum við athugað fjölda „leitargilda“ og séð hvort eitt þeirra sé jafnt gildi okkar. Ef já, skilaðu satt.
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;
};Grunnurinn að lausninni er for lykkja, sem, eins og við sáum hér að ofan, hefur línulegan tímaflækju upp á O(N).
Annar endurtekningarhluti fallsins okkar er Array.prototype.include(), JavaScript aðferð sem mun skila satt eða ósatt eftir því hvort fylkið inniheldur uppgefið gildi.
Til að reikna út hversu flókið tíma Array.prototype.includes() er, getum við skoðað fjölfyllinguna sem MDN býður upp á (og skrifað í JavaScript) eða notað aðferð í frumkóða JavaScript vél eins og 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;
}
});
}Hér er endurtekinn hluti Array.prototype.include() while lykkjan í skrefi 7 sem (næstum) fer yfir alla lengd tiltekins fylkis. Þetta þýðir að tímaflækjustig þess er líka línuleg. Jæja, þar sem það er alltaf einu skrefi á eftir aðalfylki okkar, þá er tímaflækjustigið O (N + (N - 1)). Með því að nota Big O Notation, einföldum við það í O(N) - vegna þess að það er N sem hefur mest áhrif þegar inntaksstærðin er aukin.
Varðandi staðbundið flókið, þarf viðbótarfylki þar sem lengdin endurspeglar upprunalega fylkið (mínus einn, já, en það er hægt að hunsa það), sem leiðir til O(N) staðbundins flækjustigs. Jæja, aukin minnisnotkun tryggir hámarks skilvirkni reikniritsins.
Ég vona að þér finnist greinin gagnleg sem viðbót við myndbandsviðtalið þitt. Það sýnir að hægt er að leysa einfalt vandamál á nokkra mismunandi vegu með mismunandi magni af auðlindum sem notuð eru (tími, minni).
Skillbox mælir með:
- Notað netnámskeið .
- Rafræn fræðsla .
- Hagnýtt eins árs nám .
Heimild: www.habr.com