Skip to content

Instantly share code, notes, and snippets.

@scarf005
Created July 25, 2024 06:15
Show Gist options
  • Save scarf005/b362daf0e1303b653f1f765794b3ffe1 to your computer and use it in GitHub Desktop.
Save scarf005/b362daf0e1303b653f1f765794b3ffe1 to your computer and use it in GitHub Desktop.
O(1) vs O(N)
$  deno bench set_bench.ts
Check file:///Users/nemo/repo/deno-playground/set_bench.ts
cpu: Apple M1 Pro
runtime: deno 1.45.2 (aarch64-apple-darwin)

file:///Users/nemo/repo/deno-playground/set_bench.ts
benchmark             time (avg)        iter/s             (min … max)       p75       p99      p995
---------------------------------------------------------------------- -----------------------------

group 10
Set.has()              4.37 ns/iter 228,885,832.9    (4.31 ns … 11.37 ns) 4.33 ns 5.18 ns 8.69 ns
Array.includes()          9 ns/iter 111,078,805.6    (8.85 ns … 17.23 ns) 9.01 ns 9.83 ns 10.05 ns

summary
  Array.includes()
   2.06x slower than Set.has()

group 100
Set.has()              4.26 ns/iter 234,537,451.6     (4.21 ns … 13.8 ns) 4.24 ns 4.7 ns 4.94 ns
Array.includes()       7.97 ns/iter 125,407,064.8    (7.92 ns … 10.27 ns) 7.95 ns 8.71 ns 8.85 ns

summary
  Array.includes()
   1.87x slower than Set.has()

group 1000
Set.has()              4.26 ns/iter 234,938,828.9    (4.22 ns … 11.68 ns) 4.24 ns 4.62 ns 5 ns
Array.includes()     234.98 ns/iter   4,255,754.3 (233.97 ns … 242.09 ns) 235.1 ns 241.68 ns 242.04 ns

summary
  Array.includes()
   55.2x slower than Set.has()

group 10000
Set.has()              4.27 ns/iter 234,259,585.6     (4.2 ns … 21.78 ns) 4.23 ns 4.86 ns 5.23 ns
Array.includes()       2.07 µs/iter     482,401.7     (2.06 µs … 2.12 µs) 2.08 µs 2.12 µs 2.12 µs

summary
  Array.includes()
   485.61x slower than Set.has()

group 100000
Set.has()              4.25 ns/iter 235,430,947.2      (4.2 ns … 6.74 ns) 4.23 ns 4.82 ns 5.02 ns
Array.includes()       34.7 µs/iter      28,815.1   (34.46 µs … 60.42 µs) 34.58 µs 38.92 µs 41.75 µs

summary
  Array.includes()
   8170.4x slower than Set.has()

group 1000000
Set.has()              4.37 ns/iter 228,655,547.2     (4.33 ns … 7.93 ns) 4.36 ns 4.72 ns 5.1 ns
Array.includes()     556.06 µs/iter       1,798.4 (552.42 µs … 606.88 µs) 555.33 µs 578.38 µs 587.21 µs

summary
  Array.includes()
   127146.89x slower than Set.has()
for (const N of [10, 100, 1_000, 10_000, 100_000, 1_000_000]) {
const randomValue = Math.floor(Math.random() * N)
const array = [...Array(N).keys()]
const set = new Set([...Array(N).keys()])
Deno.bench("Set.has()", { group: `${N}` }, () => {
set.has(randomValue)
})
Deno.bench("Array.includes()", { group: `${N}`, baseline: true }, () => {
array.includes(randomValue)
})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment