Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Does anybody know a fast algorithm for this?

Reply
Thread Tools

Does anybody know a fast algorithm for this?

 
 
Luna Moon
Guest
Posts: n/a
 
      08-25-2007
In a 2D array of double(floating point) numbers,

ideally it should have an ordering on two dimensions:

for left to right, the numbers should increase,

from bottom to up, the numbers should increase,

if in the middle of some row and some column, there are valleys and
peaks, which means that the ordering is violated,

I want to detect these violations and set the peaks or valleys to some
predefined constants, say -1.

my question is:

how to do that efficiently in C/C++, also also Matlab?

Basically, the question is how to detect peaks and valleys which
violate the ordering and set them to an alert number, say -1. This is
like "highlighting" ...

Thanks!

 
Reply With Quote
 
 
 
 
Gianni Mariani
Guest
Posts: n/a
 
      08-25-2007
Luna Moon wrote:
> In a 2D array of double(floating point) numbers,
>
> ideally it should have an ordering on two dimensions:
>
> for left to right, the numbers should increase,
>
> from bottom to up, the numbers should increase,
>
> if in the middle of some row and some column, there are valleys and
> peaks, which means that the ordering is violated,
>
> I want to detect these violations and set the peaks or valleys to some
> predefined constants, say -1.
>
> my question is:
>
> how to do that efficiently in C/C++, also also Matlab?
>
> Basically, the question is how to detect peaks and valleys which
> violate the ordering and set them to an alert number, say -1. This is
> like "highlighting" ...



Does the 2D array fit into the primary cache ? If it does, then a
brainless for loop for each array will work fine. If however it does
not fit into cache you would benefit greatly if you tiled your algorithm
(i.e. did the analysis in tiles). Doing it in tiles allows you to
multi-thread the code so you can run analysis of multiple tiles
simultaneously.
 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      08-25-2007
Luna Moon wrote:

> In a 2D array of double(floating point) numbers,
>
> ideally it should have an ordering on two dimensions:
>
> for left to right, the numbers should increase,
>
> from bottom to up, the numbers should increase,
>
> if in the middle of some row and some column, there are valleys and
> peaks, which means that the ordering is violated,
>
> I want to detect these violations and set the peaks or valleys to some
> predefined constants, say -1.
>
> my question is:
>
> how to do that efficiently in C/C++, also also Matlab?

[snip]

I don't think that this is really language dependent.

Note that not a single entry is in violation of the order but a pair of
adjacent (horizontally or vertically) entries (this raises the question,
where you want to put the -1).

The entries form a pattern like this:

x--x--x--x
| | | |
x--x--x--x
| | | |
x--x--x--x

You can assign values to the entries so that there is exactly one violating
edge and you can even make it so that this edge can be anywhere. For this
reasin, just verifying that no violations happen requires inspection of all
horizontal and vertical edges in the pattern. The number of edges is
approximately twice the number of entries in the matrix. Therefore, no
algorithm can have better than linear (in the number of matrix entries)
runtime in the worst case. Thus, I would go with the simple, straight
forward implementation.


Best

Kai-Uwe Bux
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Does anybody know a fast algorithm for this? Luna Moon C++ 2 08-25-2007 03:54 PM
<location> element does not seem to work - Does anybody know how to solve this. alexvodovoz@yahoo.com ASP .Net 1 05-25-2007 01:12 AM
Does anybody know a simple way to show linenumbers in a JTextArea? Markus Java 5 11-29-2005 05:41 PM
Does anybody know where should I submit my control? Umut Tezduyar ASP .Net 4 09-29-2005 03:05 AM
Does anybody know the JJ2000 Project? Java 1 09-29-2003 09:04 AM



Advertisments