B
blmblm
[ snip ]
UPDATE: I just re-read the previous threads and realized that
your code actually calls SequentialSearch in the method that's
supposed to be timing BinarySearch. Once I fix that ....
[ snip ]
Both programs (yours and mine) now consistently report sequential
search to be faster than binary search. Weird, but not as weird as
the two being different in that regard ....
[ snip ]
Oh, I asked about that. One apparently can not pass a function
pointer parameter as in C. The ways that were posted involved lookup
every time AFIACS and I judged that it might swamp what I was
measuring (checking if a character were in a set). So, to my chagrin,
I had to go with cut-and-paste.
Without experimenting to find out, of course ....
It seems to me that virtual method invocations are so common in
Java that they would be well-optimized. But if you want to claim
that the code you eventually hope to produce won't have one, well,
yeah, that's true, so maybe it matters. Then again, wouldn't a
similar argument apply to C with function pointers? Maybe not.
I don't seem to be able to think this through as carefully as
I'd like.
Anyway, I was curious, so I ran your code and my revision [1], and
the results were -- surprising [2]. I noticed, by the way, that
all three of your parse methods make a call to SequentialSearch,
assigning the result to a variable that apparently isn't used.
Thinking that *might* be a mistake, I also tried your code and my
revision with that possibly-extra call removed.
UPDATE: I just re-read the previous threads and realized that
your code actually calls SequentialSearch in the method that's
supposed to be timing BinarySearch. Once I fix that ....
[1] Message-ID: <[email protected]>
[2] I tried this on several different systems, all Fedora Linux
running Java 1.6.0_21 but different hardware and different releases
of Fedora.
[ snip ]
Your code was fairly (but not 100%!) consistent in showing
treeset-based search to be fastest, followed by binary search and
then sequential search, though sometimes the difference between
sequential and binary was small. My code was -- well, this is where
it's surprising. On most of the systems where I tried it, treeset
search was fastest, but sequential search was faster than binary
search; on one system, however, the order was as for your code.
Your code was pretty consistently faster than mine, though usually
not by a lot (less than 1%).
Both programs (yours and mine) now consistently report sequential
search to be faster than binary search. Weird, but not as weird as
the two being different in that regard ....
[ snip ]