Does anybody know a fast algorithm for this?

Discussion in 'C Programming' started by Luna Moon, Aug 25, 2007.

  1. Luna Moon

    Luna Moon Guest

    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!
     
    Luna Moon, Aug 25, 2007
    #1
    1. Advertising

  2. 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.
     
    Gianni Mariani, Aug 25, 2007
    #2
    1. Advertising

  3. Luna Moon

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Aug 25, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Umut Tezduyar
    Replies:
    4
    Views:
    365
    Scott M.
    Sep 29, 2005
  2. Guest
    Replies:
    1
    Views:
    802
    Guest
    Sep 29, 2003
  3. Markus
    Replies:
    5
    Views:
    564
    Roedy Green
    Nov 29, 2005
  4. Replies:
    1
    Views:
    401
  5. Luna Moon
    Replies:
    2
    Views:
    305
    Kai-Uwe Bux
    Aug 25, 2007
Loading...

Share This Page