Re: sorting dates

JRS: In article <hlBHe.110$Tg4.4106@xxxxxxxxxxxxxxxxx>, dated Tue, 2
Aug 2005 03:00:29, seen in news:comp.lang.javascript, RobG
<rgqld@xxxxxxxxxxxxxx> posted :
>
>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)

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
.

Relevant Pages

  • sort 1-D array of doubles for Olaf Schmidt
    ... A few weeks Olaf Schmidt posted a VB6 routine to sort a 1-D array of strings very fast indeed. ... fastest way to change case of string. ... Dim i As Long, j As Long, Lo As Long, Hi As Long, StPtr As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: Collection Structure
    ... property StringID you want ... where inarr is the String array and outarr is an array of longs containing ... needs to sort the input array keeping track of the original position (I use ...
    (microsoft.public.vb.com)
  • Re: About word frequency
    ... Use the split function to turn the string into an array. ... Sort the array. ... For each sLine in aList ...
    (microsoft.public.scripting.vbscript)
  • Re: VB6 LISTBOX problem
    ... Have a look at the code below, can you do a sort that is faster ... There are of course all sorts of ways of sorting stuff, especially stuf that is "linked together" as in your UDTs, but to prove the following code sorts it in exactly the same way that your own original code does so, by concatenating all three items of each element into a composite string exactly as you are already doing, but instead of dumping those composite strings into a ListBox it dumps them into a VB string array. ... Private Type SAFEARRAY1D ... Dim StPtr As Long, VAs String, pVAs Long ...
    (microsoft.public.vb.general.discussion)
  • RE: Quick method to sort a list of strings?
    ... 'split string into an array around so each line is a seperate item ... the cell may represent the number of purchases by ... I do not have all the these comments stored in an array ... separate entities and sort them in alpha-numeric order? ...
    (microsoft.public.excel.programming)