sorting dates

[Dr John Stockton]

Re: sorting dates

JRS: In article <dchb03$rvj$1@n ews.datasync.co m>, dated Sat, 30 Jul
2005 20:54:00, seen in news:comp.lang. javascript, fox
<spamtrap@fxmah oney.com> posted :[color=blue]
>
>
>Dr John Stockton wrote:[color=green]
>> JRS: In article <dccq76$22i$1@n ews.datasync.co m>, dated Fri, 29 Jul
>> 2005 03:43:07, seen in news:comp.lang. javascript, fox
>> <spamtrap@fxmah oney.com> posted :
>>[color=darkred]
>>>
>>>comparing strings no doubt takes longer than comparing numbers.[/color]
>>
>>
>> Perhaps so. But the comparison operator should be implemented at the
>> ASM level or similar;[/color]
>
>Not relevant -- no access to asm level in js.[/color]

ASM level or similar - which includes any efficiently-compiled high
level language - is what should do the work of executing javascript
operations. We have no direct access, agreed.
[color=blue][color=green]
>> so, for strings of the length in question, ISTM
>> reasonably likely that the overall time will be dominated by other parts
>> of the routine. If it matters, it should be tested.[/color]
>
>i doubt it matters much in JS...[/color]

If there is doubt whether it matters, it should be tested; I did so.
[color=blue][color=green]
>> With 8-character strings, using the quickest test loop I know, I find
>> the loop for comparison of equal 8-character Strings to be about 10%
>> slower than that for the corresponding Numbers, loop overhead being
>> about 20%. Other browsers are likely to differ.[/color]
>
>not relevant... you didn't "get it"... and you "convenient ly" cut off "I
>used to do it in C"! This can't be done in JS... you wasted your time
>"testing" this in JS... at the "engine level" of JS's sort routine is
>STILL the character by character comparison (I checked) and whether you
>chop the string in sections of 8 or not, you still have string data types.[/color]

You miss the point. One can convert an 8-character String to Number, if
the string be a string of decimal digit characters. Sort speed of
Strings will not depend on the exact identity of the characters in them;
so one can meaningfully compare the comparison speed of Strings like
"12345678" with that of Numbers like 12345678, each being adequately
representative of the general case.


For sorting a large number of dates, one should address the question of
whether it is worthwhile to convert the dates to/from a more efficiently
sortable form before/after sorting. That conversion takes time o(N)
whereas sorting will be >o(N). Hence it is worth (slightly) converting
from String to Number for a sufficiently large number of dates, if my
result is typical.

In sorting Date Objects, things are a little different; Date Objects
store dates as Number, but a non-default Sort is needed, so here there
is the added overhead of calling (>o(N) times) a simple sort function;
however, the conversions between Date Object and Number are simpler,
involving only administrative processing.


The rest of your response is best ignored.

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

[RobG]

Re: sorting dates

fox wrote:
[...][color=blue]
>
> So -- it's just about "lightweigh t solutions for lightweight browsers"
> -- right?
>
> Comply or Die worked against Netscape 4. So why not all the others? Now
> it's "let's mollycoddle all these poor minority browsers to give them a
> chance to survive?" Don't make me laugh.
>[/color]

That attitude is at once both ignorant and arrogant.

Your notion that Netscape 4 was driven from the face of the earth by
some invisible cohort of vigilante web developers is quite fantastic.
Did this same self-righteous mob also drive IE 4 into oblivion (which
occurred while Netscape 3 was still being used in meaningful numbers)?

If lack of standards compliance is a reason for any particular browser
to die, then IE would have been stillborn. It is the most
'mollycoddled' of all browsers, particularly in regard to CSS.

Hoist with your own petard?

[...]

Oh, and it is usual practice in this forum to trim quotes to that part
being replied to.


--
Rob

[Randy Webb]

Re: sorting dates

RobG said the following on 7/31/2005 10:04 PM:
[color=blue]
> fox wrote:
> [...]
>[color=green]
>>
>> So -- it's just about "lightweigh t solutions for lightweight browsers"
>> -- right?
>>
>> Comply or Die worked against Netscape 4. So why not all the others?
>> Now it's "let's mollycoddle all these poor minority browsers to give
>> them a chance to survive?" Don't make me laugh.
>>[/color]
>
> That attitude is at once both ignorant and arrogant.[/color]

About as ignorant and arrogant as your reply? Read on before you get
offended.
[color=blue]
> Your notion that Netscape 4 was driven from the face of the earth by
> some invisible cohort of vigilante web developers is quite fantastic.
> Did this same self-righteous mob also drive IE 4 into oblivion (which
> occurred while Netscape 3 was still being used in meaningful numbers)?[/color]

Netscape 4 was indeed driven into oblivion, but not just by developers.
It started with developers not supporting it, and then Netscape
realizing that the document.layers collection was a stupid idea from the
start and scrapping it in favor of modern practices. Ever tried to
address a nested layer (oh, say 3 deep) in NN4?
[color=blue]
> If lack of standards compliance is a reason for any particular browser
> to die, then IE would have been stillborn.[/color]

That could also be said about other browsers, but I agree that IE is
about as far from being standards compliant as Firefox is. To find out,
test the code Richard posted:

var a = []
a[4251456798] = 'a';
a.reverse();

yeah, Firefox follows the ECMA quasi-standard, eh?

Every browser has it's flaws, some have more than others and Netscape 4
was the epitome of a flawed browser in it's approach and it's DOM.
[color=blue]
> It is the most 'mollycoddled' of all browsers, particularly in regard to CSS.[/color]

While that may be true, that is an argument for ciwas, not clj.

<--snipped parts I didn't reply to-->

--
Randy
comp.lang.javas cript FAQ - http://jibbering.com/faq & newsgroup weekly

[RobG]

Re: sorting dates

Randy Webb wrote:[color=blue]
> RobG said the following on 7/31/2005 10:04 PM:
>[color=green]
>> fox wrote:
>> [...]
>>[color=darkred]
>>>
>>> So -- it's just about "lightweigh t solutions for lightweight
>>> browsers" -- right?
>>>
>>> Comply or Die worked against Netscape 4. So why not all the others?
>>> Now it's "let's mollycoddle all these poor minority browsers to give
>>> them a chance to survive?" Don't make me laugh.
>>>[/color]
>>
>> That attitude is at once both ignorant and arrogant.[/color]
>
>
> About as ignorant and arrogant as your reply? Read on before you get
> offended.[/color]

I'm not offended, just annoyed that I replied at all. I agree with
all you say (above and [snipped] below). :-x

[...]

--
Rob

[RobG]

Re: sorting dates

Dr John Stockton wrote:
[...][color=blue]
>[color=green][color=darkred]
>>>so, for strings of the length in question, ISTM
>>>reasonably likely that the overall time will be dominated by other parts
>>>of the routine. If it matters, it should be tested.[/color]
>>
>>i doubt it matters much in JS...[/color]
>
>
> If there is doubt whether it matters, it should be tested; I did so.
>[/color]

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.


<script type="text/javascript">
/* used to convert string months to digits */
var mos={ Jan:"01", Feb:"02", Mar:"03", Apr:"04", May:"05", Jun:"06",
Jul:"07", Aug:"08", Sep:"09", Oct:"10", Nov:"11", Dec:"12" };

/* used to generate month strings */
var moA = [ 'Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun',
'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec' ];

var oracleDatesArra y = [];

/* support functions, do not contribute to time */
function genDates ( a, n ) {
for ( var i=0; i<n; i++ ) {
a[i] =
addZ( RanSpan( 1, 31) ) + '-'
+ moA[ RanSpan( 0, 11 ) ] + '-'
+ addZ( RanSpan( 0, 5 ) );
}
}
function addZ( x ) {
return ( x<10 )? '0' + x : '' + x;
}
// Random functions from
// http://www.merlyn.demon.co.uk/js-randm.htm#FnB
function Random(N) {
return (N * (Math.random() % 1)) | 0;
}
function RanSpan(MinV, MaxV) {
return MinV + Random(MaxV - MinV + 1);
}

/* Object method using replace with function argument */
String.prototyp e.oracleDateVal ue = function() {
return this.replace(/(\d+)-(\w+)-(\d+)/,
function(s, p1, p2, p3) {
return "20" + p3 + mos[p2] + p1;
});
}

function oracleDateCompa re(a,b) {
return a.oracleDateVal ue() - b.oracleDateVal ue();
}

/* plain string method */
function sortOdates( a ){
var aB, b = [];
var i = a.length
do {
aB = a[--i].split('-');
b[i] = '20' + aB[2] + '-' + mos[aB[1]] + '-' + aB[0];
} while ( i )
return b.sort();
}

// Generate random dates array
genDates( oracleDatesArra y, 1000 );

// Do string method
var bS = new Date();
sortOdates( oracleDatesArra y );
var bF = new Date();

// Do object method
var aS = new Date();
oracleDatesArra y.sort( oracleDateCompa re );
var aF = new Date();

alert(
'Object time: ' + (aF-aS)
+ '\nString time: ' + (bF-bS)
);

</script>


--
Rob

[Dr John Stockton]

Re: sorting dates

JRS: In article <hlBHe.110$Tg4. 4106@news.optus .net.au>, dated Tue, 2
Aug 2005 03:00:29, seen in news:comp.lang. javascript, RobG
<rgqld@iinet.ne t.auau> posted :[color=blue]
>
>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.[/color]


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(11 000, 44000)*864e5)

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

[fox]

Re: sorting dates

The reason I am so late in responding is that I had many years of source
code to go through in order to accurately verify the origin of my idea
so that there could be no questions. I also had to do a good deal of
research on many topics as a "refresher" since nitpicking seems to be
the order of the day.

Dr John Stockton wrote:[color=blue]
> JRS: In article <dchb03$rvj$1@n ews.datasync.co m>, dated Sat, 30 Jul
> 2005 20:54:00, seen in news:comp.lang. javascript, fox
> <spamtrap@fxmah oney.com> posted :
>[color=green]
>>
>>Dr John Stockton wrote:
>>[color=darkred]
>>>JRS: In article <dccq76$22i$1@n ews.datasync.co m>, dated Fri, 29 Jul
>>>2005 03:43:07, seen in news:comp.lang. javascript, fox
>>><spamtrap@fx mahoney.com> posted :
>>>
>>>
>>>>comparing strings no doubt takes longer than comparing numbers.
>>>
>>>
>>>Perhaps so. But the comparison operator should be implemented at the
>>>ASM level or similar;[/color]
>>
>>Not relevant -- no access to asm level in js.[/color]
>
>
> ASM level or similar - which includes any efficiently-compiled high
> level language - is what should do the work of executing javascript
> operations. We have no direct access, agreed.
>
>[color=green][color=darkred]
>>>so, for strings of the length in question, ISTM
>>>reasonably likely that the overall time will be dominated by other parts
>>>of the routine. If it matters, it should be tested.[/color]
>>
>>i doubt it matters much in JS...[/color]
>
>
> If there is doubt whether it matters,[/color]

if there is a doubt -- chances are very good it doesn't matter. from a
UI point of view (something you know very little about) a few
microseconds here and there are *negligible*.
[color=blue]
> it should be tested; I did so.[/color]

I think you're lying... I think you simply "reasoned" it -- JUST LIKE I DID[color=blue]
>
>[color=green][color=darkred]
>>>With 8-character strings, using the quickest test loop I know, I find
>>>the loop for comparison of equal 8-character Strings to be about 10%
>>>slower than that for the corresponding Numbers, loop overhead being
>>>about 20%. Other browsers are likely to differ.[/color]
>>
>>not relevant... you didn't "get it"... and you "convenient ly" cut off "I
>>used to do it in C"! This can't be done in JS... you wasted your time
>>"testing" this in JS... at the "engine level" of JS's sort routine is
>>STILL the character by character comparison (I checked) and whether you
>>chop the string in sections of 8 or not, you still have string data types.[/color]
>
>
> You miss the point.[/color]

nice try...

[color=blue]
> One can convert an 8-character String to Number, if
> the string be a string of decimal digit characters. Sort speed of
> Strings will not depend on the exact identity of the characters in them;
> so one can meaningfully compare the comparison speed of Strings like
> "12345678" with that of Numbers like 12345678, each being adequately
> representative of the general case.[/color]

clever trick paraphrasing my illustration and giving it back to me as if
it were your idea...

I can verify that specific JavaScript source code of mine that uses
packed date format goes back to feb 98 (and C source back to 95)... and
at that, it was the file modification date of the "final version." The
file was available for public access as of feb 98 and is verifiable that
it was availabe in 1998 via Google groups (a ref. to qdate in July of 98
and the source code and an explanation of the routines, and showing
specifically the "packed 32-bit integer with the following format:
yyyymmdd" in Nov 98) ["true packing"]

Whatever else you think of this nine year old code, don't pretend to
tell me like I don't know it backwards and forwards. it's *insulting*
[color=blue]
>
>
> For sorting a large number of dates, one should address the question of
> whether it is worthwhile to convert the dates to/from a more efficiently
> sortable form before/after sorting.[/color]

see... now if you had tested it, this wouldn't even be a question.
[color=blue]
> That conversion takes time o(N)
> whereas sorting will be >o(N).[/color]

*VERY IMPRESSIVE* quoting the "books" on sort efficiency... however
inaccurately: that's supposed to be a capital O ("complexity ") [ the
notation is even *referred* to as "big-o"]

if JS uses Quick Sort (which I believe it does - but it is very
difficult digging around the source code at mozilla and i have not been
able to verify through other sources, *to this point* -- no info on
JScript either)... it has a worst case efficiency of O(n^2)

Avg time for a quick sort is: O(n*ln(n)); so yeah... that would be >O(n)
[color=blue]
> Hence it is worth (slightly) converting
> from String to Number for a sufficiently large number of dates, if my
> result is typical.[/color]


I thought you were a "die-hard" IE4 user... only mozilla/gecko has this
advantage (and, as much as i *hate* to say it: mozilla doesn't count for
much in the real world).

if we had BOTH read ECMA-262, we would have seen that the first thing
the sort algorithm does is "call toString" on both a and b... converting
to number to have js convert it to string is a waste of time.
[color=blue]
>
> In sorting Date Objects, things are a little different; Date Objects
> store dates as Number, but a non-default Sort is needed, so here there
> is the added overhead of calling (>o(N) times) a simple sort function;
> however, the conversions between Date Object and Number are simpler,
> involving only administrative processing.[/color]

Sorting Date Objects is even MORE surprising...


This was my test:

(unbiased -- no "type" conversions during sort)

10000 random "yyyymmdd"
10000 random yyyymmdd (Number)
10000 random Date

since benchmarking random data sorts in Javascript is subject to a good
bit of variation, i'll state an "average" rounded result indicative of
each sort test:

IE6

"yyyymmdd" no compare function 90ms cmp: a < b 6300ms
yyyymmdd no compare function 140ms cmp: a - b 7400ms
Date ---------------------------- cmp: a - b 22500ms
Date ---------------------------- cmp: getTime 32000ms


Firefox

"yyyymmdd" no compare function 60ms cmp: a < b 450ms
yyyymmdd no compare function 1440ms cmp: a - b 350ms
Date ---------------------------- cmp: a - b 3100ms
Date ---------------------------- cmp: getTime 4900ms

800MHz P4 win2k


Defies logic... doesn't it?!? Numbers vs Strings, that is...

[*
cmp: a < b means: return a < b ? -1 : 1
cmp: a - b means: return a-b;
cmp: getTime means: return a.getTime() - b.getTime()
*]

**after about 1000 elements, quicksort's efficiency rapidly decays,
according to sources I was able to find "on such short notice"**

I also tried prototyping a sort routine and the abbreviated date string
(iso basic) into the Date object -- results tended to be even worse than
just sorting the Date objects outlined above.

But as it turns out, my original routine converting oracle database
dates into "yyyymmdd" was the MOST efficient way to go, as far as
anything that has been discussed in this thread... keeping the
yyyy-mm-dd format will cost a couple of extra microseconds per pass.
[color=blue]
>
>
> The rest of your response is best ignored.
>[/color]
then I can add anything I want for posterity here... heh...

charlatan... carpetbagger (US def.)...


.... until you bring your incessantly self-referred js code up to
reasonably modern standards, you are just being mean to the beginners...
after this thread i seriously wonder if you are even capable -- do you
really know or remember what all those single-letter variable names
stand for anymore? (many have no relationship to their function.) Did
you not understand the algorithms when you copied them from the old
BASIC texts? not even Knuth codes like that anymore. Wirth was/is an
advocate for *clearly readable* source code. Pascal was designed to
"read like english." when *you* invoke his name, you insult *him* AND
the language.

also, what's the deal with Math.floor(Math .random() % 1)? (i saw that
robG diligently copied it from your site...bet that flattered you.) i
vaguely remember something about that bug from years and years ago. i
can no longer find any valid current reference to anything like this
save for people copying your code. from somebody so obsessed with
efficiency, this seems a little unusual.

you should also revisit your "Deal":

1) you cannot distribute the same set to each recipient
2) you cannot isolate subsets from within
the function creating the set or its order
3) save for a very few solitaires, the entire set is rarely dealt

it's really only a shuffle...


clean your own house before you criticize others'

[Martin Bialasinski]

Re: sorting dates

fox <spamtrap@fxmah oney.com> wrote:
[color=blue]
> mozilla doesn't count for much in the real world).[/color]

Well, depends on the world in question. The opposite of your "never seen it
at a customer" is e.g.

<URL:http://www.adtech.de/NewsPresse/framepresse.php ?lang_id=de&nod e=4&current=193 >
or
<URL:http://www.xitimonitor .com/etudes/equipement10.as p>

Bye,
Martin