nicolas nicolas - 9 days ago 6
C Question

hashing of an integer vector for fast querying

I represent a monomial with a 3x2 vector. For example,

x y z : ( (variable id, exponent of variable) )

: ( (1,1) , (2, 1) , (3,1) )

x^2 z^2 : ( (1,2) , (3,2) , (null, null) )


The total number of distinct variable is one million, but a monomial contains at most three distinct variables.

I want to do query like


  1. Is
    x
    in the monomial
    y^2 z^2
    ?

  2. Is the power of
    y
    greater than
    3
    in
    y^2 z^2
    ?



Is there a hash function that will answer those question in O(1)?

Or should I just loop over the 3x2 vector?

I ask because I maintain a hash table with 5 millions of such monomial.
So, by default, I must use a hashing structure to do a search.
Maybe there is an hashing scheme that can also answer the two questions above.

Related question: best codebook for manipulation of monomials

Answer

I think you have to loop over the 3x2 vector.

And one could argue that looping over the vector is an O(1) operation. Why? Because the number of entries in the vector is exactly 3, which is a small constant number. To put it another way, the loop count is independent of the big numbers:

  • n which is the number of variables, and
  • m which is the number of monomials.

It doesn't matter how big (or small) m and n are, looping over the vector always takes the same amount of time, so it's technically an O(1) operation.