Re: Efficient Vector Comparison

cri@xxxxxxxx (Richard Harter) writes:

On Thu, 28 Jun 2007 16:48:49 +0800, Yao Qi <qiyaoltc@xxxxxxxxx> wrote:


In our program, we will compare every two vectors. In current
implementation, we compare every element of that vector until we get
the
comparison result. It is not any more efficient way to do this?

b.t.w the length of vector is variable.

Your description is inadequate. Here are questions you need to answer.

1. What kind of comparison result do you need? Is a equal/not equal
result
satisfactory, or do you need a less than/equal/greater than result based
on
some ordering, or do you need to know the first element at which the two
vectors differ, or what?

equal/not equal is not enough for me.
I need a less than/equal/greater than/uncomparable result.
I do not need to know the first different element.

For example,
v1 = (1, 1, 0), v2 = (1, 1, 0, 0), v3 = (2, 0, 1) , v4 = (1, 2, 0)

v2 is equal to v1.
v4 is greater than v1.
v3 and v1 is not comparable.


2. When you say "we will compare every two vectors" what do you
actually
mean by that? Does that mean that you have a set of vectors and that
you
will do a comparison on every pair from the set? If not, what do you
mean?

Yeah, I have a list of vectors, and we have to compare every two of them.

There are a number of methods for managing and classifying set of data
elements (vectors in your case) such as hash tables and patricia trees.
They might be relevant or might not. There is no way of knowing from
your
description.

We tried to use hash table, but we could not figure out how to write a
hash function in this case. I could have a try on Patricia tree.

Thanks for your reply, and sorry for my unclear description.

Best Regards

--
Yao Qi <qiyaoltc@xxxxxxxxx> GNU/Linux Developer
http://duewayqi.googlepages.com/

Change your thoughts and you change your world.
.

Relevant Pages

  • Re: Suggestions for double-hashing scheme
    ... >> secondary hash function to 1/4 of the table size, ... > Hsieh is considered a laughing stock in many circles, ... Thats more typedefs than in all of bstrlib already. ... (Compare this to Bstrlib, whose influence ...
    (comp.programming)
  • Re: Detecting Brute-Force and Dictionary attacks
    ... usually modern systems doesn't compare the password you ... password attempt with the saved hash of your current password. ... It is my personal opinion that evaluating the passwords so closely, such as mentioned in the previous email to Greg's, would open yourself up to a far more complicated world than you might be thinking. ... In the past, when I've had people attempting to attack my systems, the easiest way to tell is the number of login attempts against the frequency of the attempts. ...
    (Focus-Linux)
  • Re: How good are checksums?
    ... >checksum and compare file lengths. ... >duplicate very low. ... I use a fast Adlerian checksum. ... Your problem is similar to what to do with hash table collisions. ...
    (comp.lang.java.programmer)
  • Re: Byte to byte compare, duplicate file finder/killer
    ... cryptographically strong hash, simply because the CRC ... By using a secure hash instead of CRC, the actual byte-to-byte compare ... checksum (files with identical CRCs or checksums are trivial to ...
    (comp.programming)
  • Re: How do I can check a password Hash in WSE 2.0
    ... The SHA-1 hash of the password is sent in the SOAP message. ... WSE calls the AuthenticateToken method of the class deriving ... > private string HashPassword (string nnonce, DateTime nfecha, string ... and then compare your computed hash against the supplied one. ...
    (microsoft.public.dotnet.framework.aspnet.security)