D
Dr John Stockton
JRS: In article <[email protected]>, dated Tue, 2
Aug 2005 03:00:29, seen in RobG
It would have saved me time if you had described what you were sorting,
and how. AFAICS :
Your date array appears to hold entries such as 13-Apr-05.
Your string sort first converts those to 2005-04-13 (the hyphens are a
waste of time, at least for a large array or if the output dates are to
be reformatted; and so is the 20) and then sorts. The sort itself is as
efficient as can be for strings.
Your object sort, however, will do o(>N) comparisons, each calling a
javascript compare function, which twice calls a conversion function,
each of which calls a RegExp replace which calls a function which
returns a string; the strings are subtracted, which entails conversions
to Number. Naturally it is a slow method.
An efficient Object sort would preprocess the date array into a Date
Object array, and use a comparison function that subtracts the Objects,
which is subtracting their internal milliseconds since UTC 1970.0. It
will be much quicker than yours.
A really efficient sort would preprocess the date array into an array of
<Date Object>.valueOf() and do the default sort on Numbers - if only
Javascript could sort Numbers!!
For large enough arrays, one might try new Date().valueOf().toString(36)
which generates an 8-character string for years 1973 to 2058. Note that
by changing the 20 to something bigger or by adding to valueOf() one can
handle a wider span of years; one more digit gets to 5188, another to
117829, another to NaN.
Or one could take Y M D, compress that as, say, (Y*12+M)*31+D, convert
that to a fixed-length string, and sort those.
So you've proved that a string method coded almost optimally is very
much better than a cumbersome implementation of sorting with Objects.
In sorting arrays which are large enough for speed to be a concern, the
prime aim must be to minimise the work done by the user-written
comparison function; and the greatest minimisation is not to have one at
all.
Random instants can be efficiently generated by something like
new Date(RanSpan(11000, 44000)*864e5)
Aug 2005 03:00:29, seen in RobG
Seems worth testing- below is a small example that tests method A using
custom objects and replace function, method B uses string operations and
sort. Random date strings are generated - not all dates are valid and
the range is not extensive, but neither factor affects the results.
The string method runs about 60 times faster, so if speed does matter,
you'd need a good reason to prefer the other.
It would have saved me time if you had described what you were sorting,
and how. AFAICS :
Your date array appears to hold entries such as 13-Apr-05.
Your string sort first converts those to 2005-04-13 (the hyphens are a
waste of time, at least for a large array or if the output dates are to
be reformatted; and so is the 20) and then sorts. The sort itself is as
efficient as can be for strings.
Your object sort, however, will do o(>N) comparisons, each calling a
javascript compare function, which twice calls a conversion function,
each of which calls a RegExp replace which calls a function which
returns a string; the strings are subtracted, which entails conversions
to Number. Naturally it is a slow method.
An efficient Object sort would preprocess the date array into a Date
Object array, and use a comparison function that subtracts the Objects,
which is subtracting their internal milliseconds since UTC 1970.0. It
will be much quicker than yours.
A really efficient sort would preprocess the date array into an array of
<Date Object>.valueOf() and do the default sort on Numbers - if only
Javascript could sort Numbers!!
For large enough arrays, one might try new Date().valueOf().toString(36)
which generates an 8-character string for years 1973 to 2058. Note that
by changing the 20 to something bigger or by adding to valueOf() one can
handle a wider span of years; one more digit gets to 5188, another to
117829, another to NaN.
Or one could take Y M D, compress that as, say, (Y*12+M)*31+D, convert
that to a fixed-length string, and sort those.
So you've proved that a string method coded almost optimally is very
much better than a cumbersome implementation of sorting with Objects.
In sorting arrays which are large enough for speed to be a concern, the
prime aim must be to minimise the work done by the user-written
comparison function; and the greatest minimisation is not to have one at
all.
Random instants can be efficiently generated by something like
new Date(RanSpan(11000, 44000)*864e5)