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: 
JRS:  In article <dchb03$rvj$1@xxxxxxxxxxxxxxxxx>, dated Sat, 30 Jul
2005 20:54:00, seen in news:comp.lang.javascript, fox
<spamtrap@xxxxxxxxxxxxx> posted :


Dr John Stockton wrote:

JRS:  In article <dccq76$22i$1@xxxxxxxxxxxxxxxxx>, dated Fri, 29 Jul
2005 03:43:07, seen in news:comp.lang.javascript, fox
<spamtrap@xxxxxxxxxxxxx> 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;

Not relevant -- no access to asm level in js.


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. 


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.

i doubt it matters much in JS...


If there is doubt whether it matters, 

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*.

it should be tested; I did so.

I think you're lying... I think you simply "reasoned" it -- JUST LIKE I DID 


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.

not relevant... you didn't "get it"... and you "conveniently" 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.


You miss the point. 

nice try...


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.


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*



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. 

see... now if you had tested it, this wouldn't even be a question.

That conversion takes time o(N)
whereas sorting will be >o(N).

*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)

Hence it is worth (slightly) converting
from String to Number for a sufficiently large number of dates, if my
result is typical.


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.


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.


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.



The rest of your response is best ignored.
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'




.

Relevant Pages

  • Re: Dotfuscator - major flaw in Microsoft dotNET?
    ... NET assembly and convert it back into source code such as .NET ... The idea of obfuscation is to make the goal of reverse ... value of the string used in reflection or dynamic class loading, ... With Dotfuscator Professional Edition, ...
    (microsoft.public.dotnet.general)
  • Re: "NUL" device is missing
    ... > required for a specified formating string. ... I spent quite a bit of time last night reviewing the source code for the ... It is encouraging to hear than an updated ANSI C standard does finally ...
    (microsoft.public.windowsxp.embedded)
  • Re: dynamicly build a list of strings?
    ... strlcpy guarantees null termination ... the string buffer with redundant NULs. ... count of characters and then manually terminate the string). ... The source code for this function was obtained from the ...
    (comp.lang.c)
  • Re: Array of strings
    ... > Afaik it's for widestring support. ... There is a lot of source code. ... reading beyond the terminating null character. ... If a string literal is used as a WideString or PWideChar, ...
    (comp.lang.pascal.delphi.misc)
  • Re: OT: Evil Tescos promotes incest!
    ... >> the source code is not easily accessible.... ... >> i've come across this sort of thing many previous times... ... >> the pic partially loads and then 'jams'.... ... >> situation....this one is not improving on reload.. ...
    (uk.politics.misc)
Loading