Reputation
7,089
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
20 41
Newest
 Announcer
Impact
~427k people reached

Feb
25
awarded  Announcer
Jan
20
comment If a number is too big does it spill over to the next memory location?
If you need really huge numbers, it is possible to have a number representation that increases how much memory it uses to fit large numbers. The processor itself can't do this, and it's not a feature of the C language, but a library can implement it - a common C library is the GNU Multiple Precision arithmetic library. The library has to manage memory to store the numbers which has a performance cost on top of the arithmetic. A lot of languages have this kind of thing built in (which doesn't avoid the costs).
Jan
8
revised How to design a function that takes a date and gives out a number between 1-6, always the same for all dates
added 441 characters in body
Jan
8
answered How to design a function that takes a date and gives out a number between 1-6, always the same for all dates
Dec
23
comment Does low latency code sometimes have to be “ugly”?
@Brandon - in fairness, (1) what compilers optimize well now they may not have optimized well years ago, (2) the manual optimization that worked well with old machines and compilers may be counterproductive now. Basically, when some pattern keeps recurring, you're not going to measure the same pair of things every single time - that's obvious redundant work for development-time optimization - but unless performance is a major everyday focus for you, you probably won't notice when things change so those old lessons no longer apply.
Dec
23
awarded  Nice Answer
Nov
28
awarded  Yearling
Nov
18
awarded  Popular Question
Nov
6
comment How to determine if there's something wrong with my code or a bug in the library
You can search their bug tracker to see if the bug is already reported. To do that, you often need to do some investigation first anyway - your symptom is often quite different to the underlying cause. In difficult cases, the only way to figure out if a bug is yours or not is to track down the actual cause - get the source for everything you can and go wherever the investigation takes you in that code. But generally speaking, if you're not confident in your ability and you're using stable-version libraries, you're pretty safe assuming the problem is in your code.
Oct
24
awarded  Custodian
Oct
24
reviewed Approve Does an interpreter produce machine code?
Oct
12
awarded  Guru
Aug
7
awarded  Popular Question
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - also, if you compute the hash for every string on construction irrespective of whether you intend to search for it, constructing a string can easily become O(n^2) - that's budgeting for all the substrings you hash but never use those hashes, e.g. if you build your string by repeated concatenation of a single character. Of course you could claim building the string itself is O(n^2), but could easily be wrong - in C++ for example you'd get O(n) because memory is grown when needed by constant factors, not by adding a constant amount, so each iteration amortized O(1).
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - computing a string is not necessarily linear in the string length. Concatenating a constant number of additional characters is O(1), for example, providing there's enough space to grow the string - very common in C++, and particularly relevant when dealing with some amortization scheme. For some simple hash computations you could compute the new hash from the old one in O(1) time, but this is a special case. You don't just assume a special case - if you're discussing a special case that should be stated up front.
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - If you're talking about interned strings, that isn't magic, it needs an implementation. Lets assume the string "Hello" is already in that interned string table. When you compute "He"+"llo" the way you get the same interned instance of "Hello" is by looking it up in the table. If the table is a hash table, first you compute the hash of "Hello", then you find the entry in the hash table. No point getting the hash from the table - you already had to compute that to find it.
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - no, when you compute or input a new string you don't know the hash for that string until you pay the cost of computing it. That string may have already been inserted into the hash table, but you don't know that without finding it in the hash table - so to get the hash from the table you need to search so you need to already know the hash first.
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - how do you precompute the hash for a string you don't know yet? That's why hash precomputation is relatively rare. Hash caching means you only hash each string once, but even that's pointless if each search is for a newly input/derived string anyway. Either way, sure a different algorithm has different costs, but your algorithm isn't what anyone was discussing - the original point about the cost of hash computation was in the answer which I didn't write - and it still has nothing to do with whether hash functions are cryptographic strength or not.
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - that means you probably get lots of hash collisions even with a very small number of strings, and above 512 keys every single new key is a collision. And that means the asymptotic performance degrades to the performance of the collision handling - usually O(n) where n is the number of keys.
Jul
19
comment Do real-world algorithms that greatly outperform in the class below exist?
@Kevin - I just read all those comments I wrote 4 years ago and I don't see anything to do with cryptographic hashing. Hashing a whole string is O(n) because there are n characters to hash - the string length varies. If you only hash a constant part of the string, sure that would be a problem for a cryptographic hash, but it's also potentially a problem for a hashtable. Codism suggested a hash calculated as s[0]+s[s.length-1] - for 8-bit characters that's a grand total of 512 unique keys (and a non-flat distribution) even ignoring the fact some characters are more common than others.