5 ms·

You should not be using n for the number of bits and n for the size of the input. It may take longer to multiply 128 bit data structures than 64 bit data struc

You should not be using n for the number of bits and n for the size of the input. It may take longer to multiply 128 bit data structures than 64 bit data structures, but it is constant with respect to the size of the hash table.

jacquesm 17y ago
> but it is constant with respect to the size of the hash table. Exactly. That is the whole key to complexity analysis. Otherwise you end up drowning in details without getting more meaningful answers. You're analyzing the hash table algorithm, not the hashing algorithm used to produce the keys.
lemire 17y ago
My post specifically refers to vectorization where you may use the fact that you can multiply 4 pairs of 16-bit integers in the time it takes to multiply a pair of 64-bit integers. So, you could operate four 16-bit hash tables in the time it takes to operate a 64-bit hash table. That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)
- nostrademons 17y ago
  "That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)" You're assuming that people are not aware that multiplication is not always a constant-time operation. That assumption generally doesn't hold among people with any sort of academic CS background. Multiplication algorithms - and the fact that they were typically O(N) in number of bits - were covered in my intro machine architectures course. In practice, there are many, many other things that can negatively impact hash table performance in a much bigger way. Like cache misses - one cache miss costs far more than an integer multiplication. Or interpreter overhead from using, say, Ruby instead of C (bad example, since Ruby's hashtables are implemented in C, but the general point holds). Or the difference between -O0 and -O3. Or how early versions of Java Hashtables would often devolve into linked lists because the hash function only looked at the first 8 characters of a string.
  - lemire 17y ago
    I am not sure optimization, cache misses, and interpreter overhead would obviously impact the computational complexity. "You're assuming that people are not aware that multiplication is not always a constant-time operation." I made no such assumption. But I suggest people consider the case of vectorization where, all of a sudden, it may matter quite a bit.
    - stcredzero 17y ago
      You're making a point about where we take cognitive shortcuts. Short version: don't assume the classroom example assumptions always hold in the real world.
ggchappell 17y ago
> You should not be using n for the number of bits and n for the size of the input. I don't see that I ever did use it for a number of bits. I said, to have n numbers with distinct values, you need O(log n) bits in each number. n is not a number of bits.

jacquesm 17y ago

> but it is constant with respect to the size of the hash table. Exactly. That is the whole key to complexity analysis. Otherwise you end up drowning in details without getting more meaningful answers. You're analyzing the hash table algorithm, not the hashing algorithm used to produce the keys.

lemire 17y ago

My post specifically refers to vectorization where you may use the fact that you can multiply 4 pairs of 16-bit integers in the time it takes to multiply a pair of 64-bit integers. So, you could operate four 16-bit hash tables in the time it takes to operate a 64-bit hash table. That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)

nostrademons 17y ago
"That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)" You're assuming that people are not aware that multiplication is not always a constant-time operation. That assumption generally doesn't hold among people with any sort of academic CS background. Multiplication algorithms - and the fact that they were typically O(N) in number of bits - were covered in my intro machine architectures course. In practice, there are many, many other things that can negatively impact hash table performance in a much bigger way. Like cache misses - one cache miss costs far more than an integer multiplication. Or interpreter overhead from using, say, Ruby instead of C (bad example, since Ruby's hashtables are implemented in C, but the general point holds). Or the difference between -O0 and -O3. Or how early versions of Java Hashtables would often devolve into linked lists because the hash function only looked at the first 8 characters of a string.
- lemire 17y ago
  I am not sure optimization, cache misses, and interpreter overhead would obviously impact the computational complexity. "You're assuming that people are not aware that multiplication is not always a constant-time operation." I made no such assumption. But I suggest people consider the case of vectorization where, all of a sudden, it may matter quite a bit.
  - stcredzero 17y ago
    You're making a point about where we take cognitive shortcuts. Short version: don't assume the classroom example assumptions always hold in the real world.

ggchappell 17y ago

> You should not be using n for the number of bits and n for the size of the input. I don't see that I ever did use it for a number of bits. I said, to have n numbers with distinct values, you need O(log n) bits in each number. n is not a number of bits.