Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language? - Algorithms Discussion Boards

Create continuous path from multiple segments

Member 115731191-Apr-15 3:38

1-Apr-15 3:38

I have an array of several segments of a path with known start / end point. Direction of each segment is not known. It can be from start to end point or vice versa.
Each segment object is something like this:

Connection: {
 PointA = p1
 PointB = p2
 pointA_is_connected = true (false for the first or last segment)
 pointB_is_connected = true (false for the first or last segment)
}

I want to create a path from one end to another in one direction with all segments that can be connected to each other. All the segments in an array are segments of a ONE path.
Here is an image of what I have (in red) and what I want to have (in green)
What's the best way to achieve this?
http://pgtehran.euphrat.es/pic.png[^]

Re: Create continuous path from multiple segments

Frankie-C2-Apr-15 1:27

Frankie-C

2-Apr-15 1:27

You need to define a property that have to be 'comparable' and from wich result you can decide which segment choose.
I.e. defining coordinates for each starting and ending point of each segment you can choose an arbirtary small circle and search for those segments that are closer to your endpoint. The closest will be 'connected', then you will repeat the search with the opposite end of last connected segment until there are no more segments available.

Re: Create continuous path from multiple segments

Member 115731192-Apr-15 6:47

Member 11573119

2-Apr-15 6:47

Thanks,
Start and end point does have coordinates property.
Why choose an arbitrary small circle for checking? why don't check if the next point is exactly same as the start/end point of the current segment?

Re: Create continuous path from multiple segments

Frankie-C2-Apr-15 7:29

Frankie-C

2-Apr-15 7:29

To allow for small coordinates errors, especially if they are floating point or come from float calc. In that case the comparison could fail for very small differences.

When dealing with floats the best test for comparison is:

C++

if (fabs(float1-float2) < epsilon)

in this case we say that the comparison is satisfied if the absolute value difference between the two floats is less than the approximation (epsilon).
BTW you can do as you like... Laugh | :laugh:

Re: Create continuous path from multiple segments

Member 115731192-Apr-15 7:34

Member 11573119

2-Apr-15 7:34

Good point, Thanks.

Re: Create continuous path from multiple segments

Patrice T28-Jun-15 16:58

Patrice T

28-Jun-15 16:58

This a classical Graph traversal family problem.
You need to give a "cost" to each segments in order to do so kind of optimization.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

ECDSA FOR A NOOB

Reversedme28-Mar-15 5:16

Reversedme

28-Mar-15 5:16

Now i'm very much what you guys would call a total amateur
when it comes to math algorithms and any form of cryptography but i was just wondering if elliptic curve private keys usually rely on static values for all encrypted binaries being signed and verified
can a atacker not recover K if DA shares the same public and private exponent?

Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

prime_tang23-Mar-15 23:40

prime_tang

23-Mar-15 23:40

The following code is a basic algorithm for hamming distance calculation, but due to the design of my application, it requires many times to use this algorithm, in order to improve application efficiency, I want to improve the efficiency of this algorithm, is there any appropriate methods? Assembly language possible?

C++

unsigned dist(const unsigned char *vec1, const unsigned char *vec2, unsigned dim)
{
    const unsigned char popCountTable[] =
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
    unsigned dist_ = 0;
    for (unsigned i = 0; i != dim; ++i)
    {
        dist_ += popCountTable[vec1[i] ^ vec2[i]];
    }
    return dist_;
}

Re: Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

harold aptroot24-Mar-15 1:16

harold aptroot

24-Mar-15 1:16

Yes, well it depends which assembly language.
The most obvious thing is to use __popcnt64[^] to do 8 times as many popcnts in a cycle. Haswell can sustain 2 reads, a xor, a popcnt, an add and a fused sub/branch pair (hopefully the compiler will rewrite the loop logic) all together once per cycle, so that's pretty good.
You can also try the pshufb trick[^], the benchmark there shows it's a bit better. That takes more effort to make it really fast, doing as much vertical work as possible before doing a horizontal reduction and so on. May work better with AVX2, hard to say in advance.

Re: Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

Patrice T30-Jun-15 14:41

Patrice T

30-Jun-15 14:41

Optimizations of the hamming program will depend of informations about which values are allowed in the vectors, the size used to store the values, vector size.

Possible optimisations will heavily depe,d on theses values.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

UNION FIND

Pratik Naik16-Mar-15 10:26

Pratik Naik

16-Mar-15 10:26

Determine the incorrect statement below concerning the Union-Find data structure we
discussed in class (with union by rank and path-compression).
1. The union operation sometimes may not increase the height of
the resultant tree
2. The union operation can at most increase the height of
the resultant tree by one
3. The union operation always increases the height of
the resultant tree by one
4. The find operation sometimes may not increase the degree of
the root of
the resultant tree
5. The find operation requires two traversals f
rom node to root

Please let me know the answers for this Big Grin | :-D

Re: UNION FIND

Richard Andrew x6416-Mar-15 10:43

Richard Andrew x64

16-Mar-15 10:43

Nobody is going to do your homework for you.

The difficult we do right away...
...the impossible takes slightly longer.

Re: UNION FIND

Pratik Naik16-Mar-15 10:46

Pratik Naik

16-Mar-15 10:46

its not a home wrk its just i got confused with those terms andnotable to find an ans Big Grin | :-D

Re: UNION FIND

F-ES Sitecore16-Mar-15 23:55

F-ES Sitecore

16-Mar-15 23:55

I know this "isn't your homework" but we don't know what the Union-Find structure is as we weren't in the "class" where this was "discussed". If this was your homework I'd suggest getting additional help from your tutor if you need things explained, or arrange a study group with fellow students. But as this isn't your homework and we don't have access to the information needed to find a solution, there is nothing we can do to help.

SPOJ DIVCON PROBLEM

Member 114896771-Mar-15 10:54

Member 11489677

1-Mar-15 10:54

I'm having trouble with the SPOJ problem below. While I'm new to C# I feel like I understand the concepts and am simply having trouble transferring it into code. More than anything the structure of the code is what I can't seem to picture in my head. To my understanding I need to find Brenda's optimal line first and then find out how best for Ann to react.

I'm at the point where I think I need less of a hint and more of a semi-solution so I can figure out where the gap in my understand is. Any help at all would be appreciated.

http://www.spoj.com/problems/DIVCON/

Re: SPOJ DIVCON PROBLEM

Richard MacCutchan1-Mar-15 22:47

Richard MacCutchan

1-Mar-15 22:47

Sorry, but no one is going to go to some other site to study a problem on your behalf.

Looking for someone to help create an algorithm.

Member 1146989221-Feb-15 19:27

Member 11469892

21-Feb-15 19:27

We have a project in which I am the head creator and we are in need of an algorithm. The algorithm must consist of multiple variables that will conclude the best possible option(s) based off of information collected by the user (if more details are needed please ask and I may be able to answer them based on the question). Can anyone help in creating the algorithm or direct us to someone who can help? Any guidance would be appreciated, thank you.

Re: Looking for someone to help create an algorithm.

Richard MacCutchan21-Feb-15 21:28

Richard MacCutchan

21-Feb-15 21:28

Sorry, wrong place, see http://www.codeproject.com/Messages/2966804/How-to-get-an-answer-to-your-question.aspx[^].

Re: Looking for someone to help create an algorithm.

Kornfeld Eliyahu Peter21-Feb-15 22:33

Kornfeld Eliyahu Peter

21-Feb-15 22:33

How do you expect us to ask you questions for details (not to say giving any answers) if you do not provide any details to start with...
What 'variables', what 'best possible option', what information collected', what 'user'?

Skipper: We'll fix it.
Alex: Fix it? How you gonna fix this?
Skipper: Grit, spit and a whole lotta duct tape.

Re: Looking for someone to help create an algorithm.

Member 1146989222-Feb-15 6:16

Member 11469892

22-Feb-15 6:16

I realize it was very general. I was more looking for someone who might be able to help with this and I can go into more details with that individual. I can explain a little more. We are working with some basketball coaches and part of the project is asking the question, how can a coach mathematically determine the best athlete for the program by the statistics each athlete provides while calculating what the coach needs to help their program? Also we would like to calculate the distance from the athlete to the program to give the probability of which player would be the best choice. I hope this provides a little more insight on the project.

Re: Looking for someone to help create an algorithm.

Richard MacCutchan22-Feb-15 7:19

Richard MacCutchan

22-Feb-15 7:19

Member 11469892 wrote:
I was more looking for someone who might be able to help with this

If you are trying to recruit a developer to write code for you then you are on the wrong site. Take another look at the link I posted in my previous response, which explains how to formulate a valid question.

Re: Looking for someone to help create an algorithm.

Member 1146989222-Feb-15 8:15

Member 11469892

22-Feb-15 8:15

Richard, could you be so kind and direct me to where I can find what I am looking for, rather then just a question? This is my first attempt and I don't want to be wasting anyone's time. I would appreciate your help, thank you.

Re: Looking for someone to help create an algorithm.

Richard MacCutchan22-Feb-15 22:01

Richard MacCutchan

22-Feb-15 22:01