Skip to content

Commit faf3b5a

Browse files
kgrytekgryte
committed
Add utility to perform a single-pass map-reduce operation on an array
1 parent b16ce81 commit faf3b5a

13 files changed

Lines changed: 2143 additions & 0 deletions

File tree

‎lib/node_modules/@stdlib/utils/map-reduce/README.md‎

Lines changed: 246 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,246 @@
1+
<!--
2+
3+
@license Apache-2.0
4+
5+
Copyright (c) 2022 The Stdlib Authors.
6+
7+
Licensed under the Apache License, Version 2.0 (the "License");
8+
you may not use this file except in compliance with the License.
9+
You may obtain a copy of the License at
10+
11+
http://www.apache.org/licenses/LICENSE-2.0
12+
13+
Unless required by applicable law or agreed to in writing, software
14+
distributed under the License is distributed on an "AS IS" BASIS,
15+
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16+
See the License for the specific language governing permissions and
17+
limitations under the License.
18+
19+
-->
20+
21+
# mapReduce
22+
23+
> Perform a single-pass map-reduce operation against each element in an array and return the accumulated result.
24+
25+
<!-- Section to include introductory text. Make sure to keep an empty line after the intro `section` element and another before the `/section` close. -->
26+
27+
<section class="intro">
28+
29+
</section>
30+
31+
<!-- /.intro -->
32+
33+
<!-- Package usage documentation. -->
34+
35+
<section class="usage">
36+
37+
## Usage
38+
39+
```javascript
40+
var mapReduce = require( '@stdlib/utils/map-reduce' );
41+
```
42+
43+
#### mapReduce( arr, initial, mapper, reducer\[, thisArg ] )
44+
45+
Performs a map-reduce operation against each element in an array and returns the accumulated result.
46+
47+
```javascript
48+
function square( value ) {
49+
return value * value;
50+
}
51+
52+
function sum( accumulator, value ) {
53+
return accumulator + value;
54+
}
55+
56+
var arr = [ 1, 2, 3, 4 ];
57+
58+
var out = mapReduce( arr, 0, square, sum );
59+
// returns 30
60+
```
61+
62+
The function accepts both array-like objects and [`ndarray`][@stdlib/ndarray/ctor]-like objects.
63+
64+
```javascript
65+
var array = require( '@stdlib/ndarray/array' );
66+
67+
function square( value ) {
68+
return value * value;
69+
}
70+
71+
function sum( accumulator, value ) {
72+
return accumulator + value;
73+
}
74+
75+
var opts = {
76+
'dtype': 'generic'
77+
};
78+
var arr = array( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ], opts );
79+
80+
var out = mapReduce( arr, 0, square, sum );
81+
// returns 91
82+
```
83+
84+
The mapping function is provided the following arguments:
85+
86+
- **value**: array element.
87+
- **index**: element index.
88+
- **arr**: input array.
89+
90+
The reducing function is provided the following arguments:
91+
92+
- **accumulator**: accumulated value.
93+
- **value**: result of applying the mapping function to the current array element.
94+
- **index**: element index.
95+
- **arr**: input array.
96+
97+
To set the `this` context when invoking the reducing function, provide a `thisArg`.
98+
99+
<!-- eslint-disable no-invalid-this -->
100+
101+
```javascript
102+
function square( value ) {
103+
return value * value;
104+
}
105+
106+
function sum( accumulator, value ) {
107+
this.count += 1;
108+
return accumulator + value;
109+
}
110+
111+
var arr = [ 1, 2, 3, 4 ];
112+
113+
var ctx = {
114+
'count': 0
115+
};
116+
117+
var out = mapReduce( arr, 0, square, sum, ctx );
118+
// returns 30
119+
120+
var mean = out / ctx.count;
121+
// returns 7.5
122+
```
123+
124+
</section>
125+
126+
<!-- /.usage -->
127+
128+
<!-- Package usage notes. Make sure to keep an empty line after the `section` element and another before the `/section` close. -->
129+
130+
<section class="notes">
131+
132+
## Notes
133+
134+
- The function supports array-like objects exposing getters and setters for array element access (e.g., [`Complex64Array`][@stdlib/array/complex64], [`Complex128Array`][@stdlib/array/complex128], etc).
135+
136+
```javascript
137+
var Complex64Array = require( '@stdlib/array/complex64' );
138+
var Complex64 = require( '@stdlib/complex/float32' );
139+
var cceil = require( '@stdlib/math/base/special/cceil' );
140+
var realf = require( '@stdlib/complex/realf' );
141+
var imagf = require( '@stdlib/complex/imagf' );
142+
143+
function sum( acc, z ) {
144+
var re1 = realf( acc );
145+
var im1 = imagf( acc );
146+
var re2 = realf( z );
147+
var im2 = imagf( z );
148+
return new Complex64( re1+re2, im1+im2 );
149+
}
150+
151+
var x = new Complex64Array( [ 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5 ] );
152+
153+
var v = mapReduce( x, new Complex64( 0.0, 0.0 ), cceil, sum );
154+
// returns <Complex64>
155+
156+
var re = realf( v );
157+
// returns 20.0
158+
159+
var im = imagf( v );
160+
// returns 24.0
161+
```
162+
163+
- For [`ndarray`][@stdlib/ndarray/ctor]-like objects, the function performs a single-pass map-reduce operation over the entire input [`ndarray`][@stdlib/ndarray/ctor] (i.e., higher-order [`ndarray`][@stdlib/ndarray/ctor] dimensions are flattened to a single-dimension).
164+
165+
- When applying a function to [`ndarray`][@stdlib/ndarray/ctor]-like objects, performance will be best for [`ndarray`][@stdlib/ndarray/ctor]-like objects which are single-segment contiguous.
166+
167+
</section>
168+
169+
<!-- /.notes -->
170+
171+
<!-- Package usage examples. -->
172+
173+
<section class="examples">
174+
175+
## Examples
176+
177+
<!-- eslint no-undef: "error" -->
178+
179+
```javascript
180+
var filledarrayBy = require( '@stdlib/array/filled-by' );
181+
var discreteUniform = require( '@stdlib/random/base/discrete-uniform' ).factory;
182+
var naryFunction = require( '@stdlib/utils/nary-function' );
183+
var add = require( '@stdlib/math/base/ops/add' );
184+
var abs = require( '@stdlib/math/base/special/abs' );
185+
var array = require( '@stdlib/ndarray/array' );
186+
var mapReduce = require( '@stdlib/utils/map-reduce' );
187+
188+
function fill( i ) {
189+
var rand = discreteUniform( -10*(i+1), 10*(i+1) );
190+
return filledarrayBy( 10, 'generic', rand );
191+
}
192+
193+
// Create a two-dimensional ndarray (i.e., a matrix):
194+
var x = array( filledarrayBy( 10, 'generic', fill ), {
195+
'dtype': 'generic',
196+
'flatten': true
197+
});
198+
199+
// Create an explicit unary function:
200+
var f1 = naryFunction( abs, 1 );
201+
202+
// Create an explicit binary function:
203+
var f2 = naryFunction( add, 2 );
204+
205+
// Compute the sum of absolute values:
206+
var out = mapReduce( x, 0, f1, f2 );
207+
208+
console.log( 'x:' );
209+
console.log( x.data );
210+
211+
console.log( 'sum: %d', out );
212+
```
213+
214+
</section>
215+
216+
<!-- /.examples -->
217+
218+
<!-- Section to include cited references. If references are included, add a horizontal rule *before* the section. Make sure to keep an empty line after the `section` element and another before the `/section` close. -->
219+
220+
<section class="references">
221+
222+
</section>
223+
224+
<!-- /.references -->
225+
226+
<!-- Section for related `stdlib` packages. Do not manually edit this section, as it is automatically populated. -->
227+
228+
<section class="related">
229+
230+
</section>
231+
232+
<!-- /.related -->
233+
234+
<!-- Section for all links. Make sure to keep an empty line after the `section` element and another before the `/section` close. -->
235+
236+
<section class="links">
237+
238+
[@stdlib/ndarray/ctor]: https://github.com/stdlib-js/stdlib
239+
240+
[@stdlib/array/complex64]: https://github.com/stdlib-js/stdlib
241+
242+
[@stdlib/array/complex128]: https://github.com/stdlib-js/stdlib
243+
244+
</section>
245+
246+
<!-- /.links -->

‎lib/node_modules/@stdlib/utils/map-reduce/benchmark/benchmark.array.js‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
/**
2+
* @license Apache-2.0
3+
*
4+
* Copyright (c) 2022 The Stdlib Authors.
5+
*
6+
* Licensed under the Apache License, Version 2.0 (the "License");
7+
* you may not use this file except in compliance with the License.
8+
* You may obtain a copy of the License at
9+
*
10+
* http://www.apache.org/licenses/LICENSE-2.0
11+
*
12+
* Unless required by applicable law or agreed to in writing, software
13+
* distributed under the License is distributed on an "AS IS" BASIS,
14+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15+
* See the License for the specific language governing permissions and
16+
* limitations under the License.
17+
*/
18+
19+
'use strict';
20+
21+
// MODULES //
22+
23+
var bench = require( '@stdlib/bench' );
24+
var pow = require( '@stdlib/math/base/special/pow' );
25+
var isnan = require( '@stdlib/math/base/assert/is-nan' );
26+
var filled = require( '@stdlib/array/base/filled' );
27+
var add = require( '@stdlib/math/base/ops/add' );
28+
var abs = require( '@stdlib/math/base/special/abs' );
29+
var pkg = require( './../package.json' ).name;
30+
var mapReduce = require( './../lib' );
31+
32+
33+
// FUNCTIONS //
34+
35+
/**
36+
* Creates a benchmark function.
37+
*
38+
* @private
39+
* @param {PositiveInteger} len - array length
40+
* @returns {Function} benchmark function
41+
*/
42+
function createBenchmark( len ) {
43+
var x = filled( -3.0, len );
44+
return benchmark;
45+
46+
/**
47+
* Benchmark function.
48+
*
49+
* @private
50+
* @param {Benchmark} b - benchmark instance
51+
*/
52+
function benchmark( b ) {
53+
var out;
54+
var i;
55+
56+
b.tic();
57+
for ( i = 0; i < b.iterations; i++ ) {
58+
out = mapReduce( x, 0.0, abs, add );
59+
if ( isnan( out ) ) {
60+
b.fail( 'should not return NaN' );
61+
}
62+
}
63+
b.toc();
64+
if ( isnan( out ) ) {
65+
b.fail( 'should not return NaN' );
66+
}
67+
b.pass( 'benchmark finished' );
68+
b.end();
69+
}
70+
}
71+
72+
73+
// MAIN //
74+
75+
/**
76+
* Main execution sequence.
77+
*
78+
* @private
79+
*/
80+
function main() {
81+
var len;
82+
var min;
83+
var max;
84+
var f;
85+
var i;
86+
87+
min = 1; // 10^min
88+
max = 6; // 10^max
89+
90+
for ( i = min; i <= max; i++ ) {
91+
len = pow( 10, i );
92+
93+
f = createBenchmark( len );
94+
bench( pkg+'::array:len='+len, f );
95+
}
96+
}
97+
98+
main();

0 commit comments

Comments
 (0)