Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Fast by default: everyday algorithmic thinking ...

Fast by default: everyday algorithmic thinking for developers [RU]

Vladimir Agafonkin

October 06, 2018
Tweet

More Decks by Vladimir Agafonkin

Other Decks in Programming

Transcript

  1. 1. Найти узкую задачу 2. ⚡ Создать для нее самую

    быструю и простую в мире JavaScript-библиотеку 3. Перейти к пункту №1
  2. Leaflet, mapbox-gl-js, mapbox-gl-native, earcut, earcut.hpp, rbush, rbush-knn, kdbush, kdbush.hpp, geokdbush,

    flatbush, geoflatbush, concaveman, supercluster, supercluster.hpp, dobbyscan, delaunator, delaunator-rs, d3-delaunay, linematch, lineclip, pixelmatch, simplify-js, cheap-ruler, polylabel, tinyqueue, flatqueue, tile-cover, which-polygon, quickselect, simple-statistics, tiny-sdf, geojson-vt, potpack, geojson-vt-cpp, geobuf, pbf, tile- reduce, geojson.hpp, geometry.hpp, tile-decorator, mbtiles- extracts, webgl-wind, suncalc, flamebearer, simpleheat, binary-split, magic-string, polysnap, rollup, sourcemap-codec
  3. 1.delaunay: 150s 2.delaunay-fast: 117s 3.faster-delaunay: 5s 4.delaunator: 1s⚡ 5.delaunator-cpp: 0.9s

    6.delaunator-rs: 0.9s триангуляция 1 миллиона точек в JS
  4. В такой чудесный, светлый день Мне хочется писать стихами... Но,

    право, ведь порою лень Вы не желали обуздать и сами? Контрольная, смотрю, весьма сложна, И отвечать совсем уж неохота, Когда за окнами прекрасная весна, И о ассемблере не мыслиться чего-то...
  5. алгоритмическая сложность: (= понять, почему тормозит и что с этим

    делать) способ описать, как быстродействие меняется с размером данных
  6. O(n2) — тормозное говно for (let i = 0, n

    = array.length; i < n; i++) { for (let j = i + 1; j < n; j++) { sum += array[i] + array[j]; } }
  7. function foo(array) { for (const item of array) { array[array.indexOf(item)]

    = item + 10; } } O(n2) — тормозное говно
  8. function foo(array) { for (const item of array) { bar(array,

    item); } } function bar(array, item) { array[array.indexOf(item)] = item + 10; } O(n2) — тормозное говно
  9. O(n3) — невыносимо, выкинуть нафиг for (let i = 0,

    n = array.length; i < n; i++) { for (let j = i + 1; j < n; j++) { for (let k = j + 1; k < n; k++) { sum += array[i] + array[j]; } } }
  10. 1. O(1) — моментально 2. O(n) — подозрительно 3. O(n2)

    — тормозное говно 4. O(n3) — выкинуть нафиг
  11. 1. O(1) — 1 2. O(n) — 1000 3. O(n2)

    — 1,000,000 4. O(n3) — 1,000,000,000 (n = 1000)
  12. чорти б мене побрали!!! хай йому грець!! дідько! if (j

    < 0) { if (triangles.length === 0) triangles.push([i]); return; } for (let n = triangles.length, a = 0; a < n; ++a) { let sa = triangles[a]; if (sa[0] === j) { for (let b = a + 1; b < n; ++b) { let sb = triangles[b]; if (sb[sb.length - 1] === i) { triangles.splice(b, 1); triangles[a] = sa = sb.concat(sa); return; } } sa.unshift(i); return; } d3/d3-delaunay#23
  13. for (const b of items) { a.slice().concat(b).map(foo) .filter(bar).reduce(bla, 0); }

    выделить память и сразу выкинуть (4 раза)
  14. Rich-Harris/sourcemap-codec#71 const lines = input.split(';'); for (const line of lines)

    { const segments = line.split(','); for (const segment of segments) { const decoded = decode(segment); for (const i of decoded) { ... } } }
  15. Rich-Harris/sourcemap-codec#71 for (let i = 0; i < input.length; i++)

    { const c = input.charCodeAt(i); if (c === 44) { // "," ... } else if (c === 59) { // ";" ... в три раза быстрее
  16. 1. O(n) → O(log n) 2. O(n log n) →

    O(n) 3. O(n2) → O(n log n) 4. O(n3) — выкинуть алгоритмическая оптимизация:
  17. • hash map • hash set • binary search tree

    • priority heap • linked list • interval tree • grid • r-tree • quadtree • kd-tree структуры данных:
  18. { '1': 10, '2': 20, '3': 30 }; { '0':

    10, '1': 20, ‘2': 30 }; HashTable Array [10, 20, 30];
  19. istanbuljs/istanbul-lib-instrument#22 { '1': 10, '2': 20, '3': 30 }; {

    '0': 10, '1': 20, ‘2': 30 }; в 15 раз быстрее
  20. 1. думайте, как оно работает 2. не бойтесь лезть в

    чужой код + 3. не бойтесь изобретать велосипеды 4. участвуйте в open source ❤ 5. постоянно упрощайте 6. практикуйте оптимизацию , и вы научитесь писать код, который сразу работает быстро