Finally, Rosemary mentioned optimisation, which, of course, in some contexts means saving minutes or hours of coding time, and in others means saving milliseconds or seconds of run time.
My guess is that the latter kind of optimisation doesn’t arise all that much as a priority for light personal scripting on Drafts, but if:
- lists were really long and disordered, or
- one or more of the accessor functions (like
houseNumber
, even
etc) were expensive (involved significant processing to obtain a property, every time two values were compared in a sort, or
- the action was used very frequently by many, then …
The main point to notice is that any given item in a list may be involved in multiple comparisons during a sort, and if a property accessor function like houseNumber
does involves some work to derive, then it it would be good to rearrange things so that each property is obtained only once per item per sort key.
A classic way to do that is a decorate-sort-undecorate pattern, bundled below in the generic and reusable sortOn function, which in this case seems to run c. 15-20% faster than the method above, i.e. probably not really worth it here, but in case it’s of any interest to anyone, here is how it works.
(PS in this case, because both sort keys use the houseNumber function, a hand-written version of the decorate-sort-undecorate process, in which houseNumber is called once only for each item), and the result reused for the even key, might speed it up another 5-10% beyond sortOn at a first guess, so still not worth it for the extra coding time )
(Javascript is very fast anyway …)
(() => {
'use strict';
/* 1. Generating a random list of streets and numbers, and then
2. SORTING:
Streets A-Z by name,
houses first by evenness of number, (EVEN THEN ODD)
and then by numeric (rather than string) order of number. (0-9)
*/
const main = () => {
// SAMPLE TEST DATA
const strList = randomStreetList();
const
rgxNum = /(^\d+)/,
houseNumber = s => {
const m = rgxNum.exec(s);
return Boolean(m) ? parseInt(m[1], 10) : 0;
};
return strList.split('\n\n')
.map(strLines => {
const xs = strLines.split('\n');
return xs[0] + '\n' +
sortOn(
mappendComparing_(
[
// DESCENDING (EVENS BEFORE ODDS)
[x => even(houseNumber(x)), false],
// ASCENDING
[houseNumber, true]
]
),
xs.slice(1)
).join('\n');
})
.sort() // If we want to sort the streets by name as well
.join('\n\n');
};
// RANDOM TEST DATA
const randomStreetList = () => ['alpha', 'beta', 'gamma', 'delta',
'epsilon', 'zeta', 'eta', 'theta', 'iota', 'kappa',
'lambda', 'mu'
].map(
x => {
const intFrom = randomRInt(1, 10000);
return x.charAt(0).toUpperCase() +
x.slice(1) + ' Street\n' +
enumFromTo(intFrom, intFrom + randomRInt(5, 10))
.map(
n => n.toString() + (Boolean(randomRInt(0, 1)) ? (
' notes...'
) : '')
)
.join('\n');
}
).join('\n\n');
// GENERIC FUNCTIONS --------------------------------------
// Tuple (,) :: a -> b -> (a, b)
const Tuple = (a, b) => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// compare :: a -> a -> Ordering
const compare = (a, b) => a < b ? -1 : (a > b ? 1 : 0);
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
n >= m ? (
iterateUntil(x => x >= n, x => 1 + x, m)
) : [];
// even :: Int -> Bool
const even = n => n % 2 === 0;
// flatten :: NestedList a -> [a]
const flatten = t =>
Array.isArray(t) ? (
[].concat.apply([], t.map(flatten))
) : t;
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
let vs = [x],
h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
// mappendComparing_ :: [((a -> b), Bool)] -> (a -> a -> Ordering)
const mappendComparing_ = fboolPairs =>
(x, y) => fboolPairs.reduce(
(ordr, fb) => {
const f = fb[0];
return ordr !== 0 ? (
ordr
) : fb[1] ? (
compare(f(x), f(y))
) : compare(f(y), f(x));
}, 0
);
// randomRInt :: Int -> Int -> Int
const randomRInt = (low, high) =>
low + Math.floor(
(Math.random() * ((high - low) + 1))
);
// sortBy :: (a -> a -> Ordering) -> [a] -> [a]
const sortBy = (f, xs) =>
xs.slice()
.sort(f);
// Sort a list by comparing the results of a key function applied to each
// element. sortOn f is equivalent to sortBy (comparing f), but has the
// performance advantage of only evaluating f once for each element in
// the input list. This is called the decorate-sort-undecorate paradigm,
// or Schwartzian transform.
// Elements are arranged from from lowest to highest.
// sortOn :: Ord b => (a -> b) -> [a] -> [a]
// sortOn :: Ord b => [((a -> b), Bool)] -> [a] -> [a]
const sortOn = (f, xs) => {
// Functions and matching bools derived from argument f
// which may be a single key function, or a list of key functions
// each of which may or may not be followed by a direction bool.
const fsbs = unzip(
flatten([f])
.reduceRight((a, x) =>
typeof x === 'boolean' ? {
asc: x,
fbs: a.fbs
} : {
asc: true,
fbs: [
[x, a.asc]
].concat(a.fbs)
}, {
asc: true,
fbs: []
})
.fbs
),
[fs, bs] = [fsbs[0], fsbs[1]],
iLast = fs.length;
// decorate-sort-undecorate
return sortBy(mappendComparing_(
// functions that access pre-calculated values
// by position in the decorated ('Schwartzian')
// version of xs
zip(fs.map((_, i) => x => x[i]), bs)
), xs.map( // xs decorated with precalculated values
x => fs.reduceRight(
(a, g) => [g(x)].concat(a), [
x
])))
.map(x => x[iLast]); // undecorated version of data, post sort.
};
// unzip :: [(a,b)] -> ([a],[b])
const unzip = xys =>
xys.reduce(
(a, x) => Tuple.apply(null, [0, 1].map(
i => a[i].concat(x[i])
)),
Tuple([], [])
);
// zip :: [a] -> [b] -> [(a, b)]
const zip = (xs, ys) =>
xs.slice(0, Math.min(xs.length, ys.length))
.map((x, i) => Tuple(x, ys[i]));
// MAIN ---------------------------------------------------
const strSorted = main();
return strSorted;
})();