feat: use more performant implementations for calculating mean, mad,a… · tinylibs/tinybench@8da741e
1+import { describe, expect, it } from 'vitest'
2+3+import { absoluteDeviationMedian, Samples, type SortedSamples } from '../src/utils'
4+import { toSortedSamples } from './utils'
5+6+// Helper: calculate median of a sorted array
7+const medianFn = (samples: SortedSamples): number => {
8+const len = samples.length
9+const mid = len >> 1
10+return len & 1
11+ ? samples[mid]! // eslint-disable-line @typescript-eslint/no-non-null-assertion
12+ : (samples[mid - 1]! + samples[mid]!) / 2 // eslint-disable-line @typescript-eslint/no-non-null-assertion
13+}
14+15+// Reference implementation: median of absolute deviations
16+const absoluteDeviationMedianTrivial = (samples: SortedSamples): number => {
17+const median = medianFn(samples)
18+const deviations = samples.map(v => Math.abs(v - median)) as Samples
19+return medianFn(toSortedSamples(deviations))
20+}
21+22+describe('absoluteDeviationMedian()', () => {
23+it('Simple odd length', () => {
24+const samples = toSortedSamples([1, 2, 3, 4, 5, 6, 7, 8, 9])
25+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
26+})
27+28+it('Simple even length', () => {
29+const samples = toSortedSamples([1, 2, 3, 4, 5, 6, 7, 8])
30+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
31+})
32+33+it('With outliers', () => {
34+const samples = toSortedSamples([1, 2, 3, 100, 200])
35+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
36+})
37+38+it('All same', () => {
39+const samples = toSortedSamples([5, 5, 5, 5, 5])
40+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
41+})
42+43+it('Two elements', () => {
44+const samples = toSortedSamples([1, 9])
45+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
46+})
47+48+it('Single element', () => {
49+const samples = toSortedSamples([42])
50+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
51+})
52+53+it('Symmetric', () => {
54+const samples = toSortedSamples([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
55+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
56+})
57+58+it('Large spread', () => {
59+const samples = toSortedSamples([1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100])
60+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
61+})
62+63+it('Duplicates at start', () => {
64+const samples = toSortedSamples([1, 1, 1, 5, 10, 15, 20])
65+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
66+})
67+68+it('Duplicates at end', () => {
69+const samples = toSortedSamples([1, 5, 10, 15, 20, 20, 20])
70+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
71+})
72+73+it('Duplicates around median', () => {
74+const samples = toSortedSamples([1, 2, 5, 5, 5, 8, 9])
75+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
76+})
77+78+it('Many duplicates', () => {
79+const samples = toSortedSamples([1, 2, 2, 3, 3, 3, 4, 4, 5])
80+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
81+})
82+83+it('Alternating duplicates', () => {
84+const samples = toSortedSamples([1, 1, 2, 2, 3, 3, 4, 4, 5, 5])
85+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
86+})
87+88+it('Almost all same with outlier', () => {
89+const samples = toSortedSamples([5, 5, 5, 5, 5, 5, 5, 100])
90+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
91+})
92+93+it('Two values repeated', () => {
94+const samples = toSortedSamples([1, 1, 1, 1, 9, 9, 9, 9])
95+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
96+})
97+98+it('Complex duplicates', () => {
99+const samples = toSortedSamples([1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7])
100+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(absoluteDeviationMedianTrivial(samples))
101+})
102+103+it('fuzzing test', () => {
104+const rounds = 1000
105+const len = 10
106+107+for (let j = 0; j < rounds; ++j) {
108+const samplesArray: Samples = new Array(len) as unknown as Samples
109+for (let i = 0; i < len; i++) {
110+samplesArray[i] = (Math.random() * 10)
111+}
112+113+const samples = toSortedSamples(samplesArray)
114+expect(absoluteDeviationMedian(samples, medianFn(samples))).toBe(
115+absoluteDeviationMedianTrivial(samples)
116+)
117+}
118+})
119+})