Не учите алгоритмы

Про то как нужны и не нужны алгоритмы :)

Transcript

1. Алгоритмы не нужны
2. Вы работаете в предсказуемой среде Полностью доверяете своему фреймворку Решаете стандартные задачи У вас опытные коллеги Вы не планируете менять работу : ) 2 Вам не нужны алгоритмы, если
3. 3 А вот если планируете…
5. Сложно! 5 f(n) = O(g(n)) ⟺ ∃c > 0,∃n0 > 0 : ∀n ≥ n0 , f(n) ≤ c ⋅ g(n)
6. 6 const arr = Array.from({ length: N }, Math.random); for (let i = 0; i < 100 ; i++) { arr.forEach(/* */); } arr.forEach((el) => { arr.forEach((el) => { // do something }); })
7. 7 Сложные буковки!
8. O(1) vs O(N) 8 const arrPush = [] performance.mark('Push start') for (let i = 0; i < 100000; i++) { arrPush.push(i) } performance.mark('Push end') const arrShift = [] performance.mark('Shift start') for (let i = 0; i < 100000; i++) { arrShift.unshift(i) } performance.mark('Shift end') performance.measure('Push', 'Push start', 'Push end') performance.measure('Shift', 'Shift start', 'Shift end') const measurements = performance.getEntriesByType('measure') console.log(measurements)
9. 9 [ PerformanceMeasure { name: 'Push', entryType: 'measure', startTime: 20.885624885559082, duration: 2.670459747314453, detail: null }, PerformanceMeasure { name: 'Shift', entryType: 'measure', startTime: 23.56599998474121, duration: 773.3739595413208, detail: null } ]
10. А что там внутри? 10 const soSimple = [1, 2, 3] DebugPrint: 0x3c004b17fcd9: [JSArray] - map: 0x023286f839f9 <Map(PACKED_SMI_ELEMENTS)> [FastProperties] - prototype: 0x0b6c6b086019 <JSArray[0]> - elements: 0x2396be814d09 <FixedArray[3]> [PACKED_SMI_ELEMENTS (COW)] - length: 3 - properties: 0x235648b01329 <FixedArray[0]> - All own properties (excluding elements): { 0x235648b055f1: [String] in ReadOnlySpace: #length: 0x279323676921 <AccessorInfo> (const accessor descriptor), location: descriptor } - elements: 0x2396be814d09 <FixedArray[3]> { 0: 1 1: 2 2: 3 } 0x23286f839f9: [Map] - type: JS_ARRAY_TYPE - instance size: 32 - inobject properties: 0 - elements kind: PACKED_SMI_ELEMENTS - unused property fields: 0 - enum length: invalid - back pointer: 0x235648b015b9 <undefined> - prototype_validity cell: 0x279323676e61 <Cell value= 1> - instance descriptors #1: 0x052461651721 <DescriptorArray[1]> - transitions #1: 0x1e68d114e549 <TransitionArray[4]>Transition array #1: 0x235648b06609 <Symbol: (elements_transition_symbol)>: (transition to HOLEY_SMI_ELEMENTS) -> 0x023286f839b1 <Map(HOLEY_SMI_ELEMENTS)> - prototype: 0x0b6c6b086019 <JSArray[0]> - constructor: 0x05246167f0e1 <JSFunction Array (sfi = 0x37a9b5f74179)> - dependent code: 0x235648b01251 <Other heap object (WEAK_ARRAY_LIST_TYPE)> - construction counter: 0
11. 11 DebugPrint: 0x3c004b17fcd9: [JSArray] - map: 0x023286f839f9 <Map(PACKED_SMI_ELEMENTS)> [FastProperties] - elements: 0x2396be814d09 <FixedArray[3]> { 0: 1 1: 2 2: 3 }
12. Push, push, push, push 12 soSimple.push(42) - elements: 0x0953b5c09aa9 <FixedArray[22]> { 0: 1 1: 2 2: 3 3: 42 4-21: 0x235648b01689 <the_hole> }
13. 13 const arrPush = [] for (let i = 0; i < 10000; i++) { arrPush.push(i) } for (let i = 0; i < 21; i++) { performance.mark(`Push start - ${i}`) arrPush.push(i) performance.mark(`Push end - ${i}`) performance.measure(`Push - ${i}`, `Push start - ${i}`, `Push end - ${i}`) } console.log(arrPush.reduce((acc, curr) => acc + curr, 0)); console.log(performance.getEntriesByType('measure').map(mark => mark.duration * 1000)); Ловим память
14. 14 3.1671524047851562, 14.208793640136719, 4.291534423828125, 4.332542419433594, 2.1677017211914062, 3.5829544067382812, 1.8749237060546875, 1.041412353515625, 1.2083053588867188, 1.9178390502929688, 1.7080307006835938, 8.208274841308594, 0.9584426879882812, 1.7499923706054688, 1.62506103515625, 0.8754730224609375, 18.459320068359375, 1.0404586791992188
15. Push: O(1) amortized 15 Cреднее время на операцию за серию операций O(1)
16. 16 soSimple[42 << 42] = '😈' DebugPrint: 0x13c6bcb97629: [JSArray] in OldSpace - map: 0x2ca7931d2b91 <Map(DICTIONARY_ELEMENTS)> [FastProperties] - prototype: 0x0b6c6b086019 <JSArray[0]> - elements: 0x23c24e6250d1 <NumberDictionary[28]> [DICTIONARY_ELEMENTS] - length: 43009 - properties: 0x235648b01329 <FixedArray[0]> - All own properties (excluding elements): { 0x235648b055f1: [String] in ReadOnlySpace: Массив не массив
17. 17 const reshape = () => searchResults.reduce((acc, node) => ({ ...acc, [node.id]: node}), {}); const reshapeFast = () => searchResults.reduce((acc, node) => { acc[node.id] = node; return acc; }, {}); Копируйте аккуратно
18. 18 doka.guide/tools/trivial - memory - model/ doka.guide/tools/algorithm - complexity/
19. Структуры данных не нужны! 19 Feature/Data Structure Feature/Data Structure
20. Техники и структуры данных Array • Sliding window • Two pointers • Binary search (sorted) • Sort (complexity?) Hash map (count / sort) Priority queue (binary heap) Graph: Tree / Trie • BFS • DFS Linked list • Fast & slow pointers DP (top down / bottom up) 20
21. Динамическое программирование 21 https: / / leetcode.com/problems/paint - house - iii/description/
22. Есть m домов, каждый нужно покрасить в один из n цветов, Некоторые дома покрашены прошлым летом. Их не надо красить. neighborhood (группа) это последовательность домов которые стоят рядом и покрашены в одинаковый цвет. Дан массив houses, m x n матрица cost и целое число target: • houses[i] : цвет i - го дома или 0 если дом не покрашен • cost[i][j] : цена покраски i - го дома в цвет j + 1. Посчитайте минимальную цену покраски, при условии что должно быть точно target neighborhoods (групп), если покрасить невозможно – верните -1
23. 23 const minCost = (houses, cost, m, n, target) => { const dp = (houseNumber, prevHouseColor, remainingTarget) => { // … } const result = dp(0, -1, target); return result >= Infinity ? -1 : result; } 23
24. 24 if (houseNumber === m) { return remainingTarget == 0 ? 0 : Infinity; }
25. 25 let minCost = Infinity; const oldColor = houses[houseNumber]; if (oldColor === 0) { // House is not painted yet. for (let i = 1; i <= n; i++) { const nextTarget = prevHouseColor !== i ? remainingTarget - 1 : remainingTarget; const priceForColor = cost[houseNumber][i - 1] + dp(houseNumber + 1, i, nextTarget); minCost = Math.min(minCost, priceForColor); } } else { // House is already painted. const isSameColor = prevHouseColor === oldColor; const oldPrice = dp(houseNumber + 1, oldColor, isSameColor ? remainingTarget : remainingTarget - 1); minCost = Math.min(minCost, oldPrice); } return minCost; 25
26. 26 const minCost = (houses, cost, m, n, target) => { const dp = (houseNumber, prevHouseColor, remainingTarget) => { // we've reached the final house if (houseNumber === m) { return remainingTarget == 0 ? 0 : Infinity; } let minCost = Infinity; const oldColor = houses[houseNumber]; if (oldColor === 0) { // House is not painted yet. for (let i = 1; i <= n; i++) { const nextTarget = prevHouseColor !== i ? remainingTarget - 1 : remainingTarget; const priceForColor = cost[houseNumber][i - 1] + dp(houseNumber + 1, i, nextTarget); minCost = Math.min(minCost, priceForColor); } } else { // House is already painted. const isSameColor = prevHouseColor === oldColor; const oldPrice = dp(houseNumber + 1, oldColor, isSameColor ? remainingTarget : remainingTarget - 1); minCost = Math.min(minCost, oldPrice); } return minCost; } const result = dp(0, -1, target); return result >= Infinity ? -1 : result; } 26
27. 27 const minCost = (houses, cost, m, n, target) => { const memo = {}; const dp = (houseNumber, prevHouseColor, remainingTarget) => { const key = `${houseNumber}-${prevHouseColor}-${remainingTarget}`; // Check if the result for the current state is already computed if (memo[key] !== undefined) { return memo[key]; } // … memo[key] = minCost; return minCost; } // .. }
28. Алгоритмы не нужны, но полезны :) Особенно если вы хотите: Понимать инструменты, которые используете Программировать что - то на графическом (дочитайте книжку) Процессить большое количество данных Мучить вашу CMS Выбирать любую работу : ) Решать любые задачи 28
29. Мы в Доке считаем, что алгоритмы — полезная штука, поэтому планируем развивать раздел, где будем рассказывать про них просто и понятно. 29
30. Спасибо : ) doka.guide @pgurtovaya