Dotnetperls
-
@TheCPUWizard said:
One of my favorite questions to ask, is "Given a choice between an O(n) implementation and an O(logN) implementation, which would you select"? The common answer is "O(logN) bcause it will be faster for larger sets". Unfortunately this does not answer the question. The only possible answer, given just the above information, is "There is insufficient information avilable to answer the question".
Indeed, because it could be 1ms * N for the implementation of the O(N) algorithm vs 3 years * log(N) for the implementation of the O(log(N)) algorithm, in which case the latter only performs better with over ~2.710241e12 elements, or over 85 years of run time. Most likely you'd use the O(N) algorithm in this case (or at the very least, re-evaluate the programmer who wrote the O(log(N)) algorithm's implementation).
-
@Ilya Ehrenburg said:
I don't think runtime range checks will entirely destroy the speedup for the cached values, but it would make the cases where something like this makes sense even rarer (if there are any situations at all where it makes sense).
So I tried it in Delphi. I made 3 different kinds of cache:
- A Buffer with C-Strings, each 4 bytes long.
- A Buffer with ShortStrings (Pascal Strings), each 4 bytes long.
- An array of Strings
I was expecting the buffers to be significantly faster, because they skip run-time range checks.
The actual results were rather interesting. The array was for times as fast than all the other methods (including direct IntToStr conversion, which was only slightly slower than the buffers).
I quickly figured the reason for this: Delphi strings are weird. I realized when I was trying to build the buffers, that the data at the location the string should be at is simply 3 bytes which don't have anything to do with the string's contents. Afaik it's some redirection to an internal memory management where somewhere the real strings are held. So the problem was that after reading from the buffers, the strings had to be converted into "real" strings... which pretty much killed speed.
Luckily, Delphi has this option to only use Pascal strings. I turned that on. Ahem. Well, now, the C-String Buffer method is the only one to be ~0.4 times faster than the direct calculation, the other two (including the array, which was A LOT faster before!) are slightly slower.
Turning on / off run time range checks appears to have no influence on the speeds.
EXPLAIN, INTERNETS!
- A Buffer with C-Strings, each 4 bytes long.
-
-
-
@derula said:
@blakeyrat said:
Filed under: EXPLAIN MOVIE! EXPLAIN!, Been watching Nostalgia Critic?
Of course!
You forgot: "Chuck NOOOORRRRRRIIIIIISSSSSS!!!"
And, of course, "Chuck NOOOORRRRIIIISSSS RIDING A SHARK AT LEAST AS BIG AS JAWS!!!"
-
@blakeyrat said:
@derula said:
@blakeyrat said:
Filed under: EXPLAIN MOVIE! EXPLAIN!, Been watching Nostalgia Critic?
Of course!
You forgot: "Chuck NOOOORRRRRRIIIIIISSSSSS!!!"
And, of course, "Chuck NOOOORRRRIIIISSSS RIDING A SHARK AT LEAST AS BIG AS JAWS!!!"
I also forgot Santa Christ.
-
Did reading his watching make you badly want to watch Theodore Rex? ... or... or was that just me?
-
@Xyro said:
[ . . . ] the day page boundaries become relevant to a coder of a high-level language is the the day that coder changes languages writes a device driver.
FTFY...
-
-
@The_Assimilator said:
@derula said:
EXPLAIN, INTERNETS!
The problem is that you're fucking well using Delphi.
Well, duh!
