Reputation
6,829
Next privilege 10,000 Rep.
Access moderator tools
Badges
18 36
Newest
 Nice Answer
Impact
~291k people reached

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.
Jun
7
comment Which arguments pass by value and which pass by reference in Java?
The implicit references are a characteristic of objects, not of parameter passing. For example object variables are implicitly "by-reference" too. Another way to explain it is that Java objects have reference semantics, whereas (most?/all?) other types have value semantics.
May
4
comment Style question: To use overloaded version or not?
@Deduplicator - You're correct - It looks like I've taken the "Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace." from C++ and "All identifiers that begin with an underscore are always reserved for use as identifiers with file scope in both the ordinary and tag name spaces." from C and forgotten that they don't apply to smaller scopes (such as within a class/struct). Comment deleted.
May
4
comment Why does C provide language 'bindings' where C++ falls short?
@Basile - Especially when you're talking about a language like Haskell, making bindings for C libraries is painful too. For example Haskell bindings to GTK 3 lagged behind the C library by a couple of years IIRC, and now we apparently have GTK 4 just around the corner. One big problem is that APIs from one language can't simply be mechanically translated if you want a good API for the other language.
May
2
comment Is it possible to speed up a hash table by using binary search trees for separate chaining?
Good point - e.g. for a constant-sized hash table with unbounded data, the asymptotic performance of the hash table is the same as the asymptotic performance of the collision handling - the hash table only changes the constant factors.
May
2
comment Is it possible to speed up a hash table by using binary search trees for separate chaining?
In asymptotic terms, using a binary tree for collision handling doesn't change expected performance of a hash table provided that the hash table already did the usual tricks to achieve amortized O(1) performance anyway. Resizing the hashtable to ensure good performance means that the expected items per bucket (the size of binary trees) is expected to be small too, so you end up with the same expected amortized O(1) either way. Even for worst case - without any balancing constraint specified, worst case performance for a binary tree is that it ends up behaving like a linked list anyway.
May
2
answered Is it possible to speed up a hash table by using binary search trees for separate chaining?
May
2
comment Haskell types for functions
My first thought is that this can be solved (but not in Haskell) with an infinite type so that adding/removing layers of application still leaves the same infinite type - kind of the same as saying infinity + 1 = infinity. I think that would mean either a = a -> (a -> (a -> (...))) or a = (((...) -> a) -> a) -> a - not sure which ATM.
May
1
revised Finding the first index in which the element and the index are the same
Corrected broken overlapping-range check (I hope)
May
1
revised Finding the first index in which the element and the index are the same
added 791 characters in body
May
1
answered Finding the first index in which the element and the index are the same
May
1
comment Finding the first index in which the element and the index are the same
Note - I haven't got a counterexample and I'm not claiming it's wrong, I'm just curious about the proof.
May
1
comment Finding the first index in which the element and the index are the same
The line if i==[i]: isn't looking at the list I at all - [i] is a new list containing that one element. I think you meant if i==I[i]:. BTW - that's an interesting problem - I mistook it for binary search for a bit. I can see that you can recursively eliminate ranges where there's no overlap between the index range and the value range (as indicated by the first/last elements) but I'd like to see the proof that sufficient ranges can be eliminated early to allow an O(log n) solution.
Mar
17
revised What algorithm can be used to determine order given incomplete information?
added 281 characters in body