pairwise comparison

Discussion in 'C Programming' started by gianluca, Aug 8, 2008.

  1. gianluca

    gianluca Guest

    Hy list
    I have to build a function for pairwise comparation of matrix
    elements. The most logical approach is with several for(;;) but my
    matrix is very large (5000 x 5000) elements (is a raster geographical
    map) and required a huge machine resource. Is there a more efficient
    algorithm for my pourpuse.
    Thanks

    Gianluca
     
    gianluca, Aug 8, 2008
    #1
    1. Advertising

  2. In article <>,
    gianluca <> wrote:

    >I have to build a function for pairwise comparation of matrix
    >elements. The most logical approach is with several for(;;) but my
    >matrix is very large (5000 x 5000) elements (is a raster geographical
    >map) and required a huge machine resource. Is there a more efficient
    >algorithm for my pourpuse.


    Is your matrix sparse or dense? Are all elements to be compared to
    all other elements?

    If all elements are to be compared to all other elements, then
    you can probably achieve significant speed-ups by processing
    the data in "blocks", paying attention to the amount of data that
    will fit into your processor's cache, and paying attention to
    cache line conflicts. Unfortunately there is no portable C method of
    determining processor cache or cache-line information (cache is
    a hardware detail that doesn't affect the semantics of C), so
    you will have to make your routine somewhat system dependant, at
    least to the point of determining those parameters (but then
    you could have a block-processing routine that did its best within
    the supplied parameters.)

    Note: when you have a choice in the matter, ensure that your output
    matrix does not have cache line conflicts with your input matrix.
    Some compilers, given the appropriate system-specific options, will
    automatically put in padding to promote good cache performance.

    Block and cache aware routines will usually be more complex, and will
    usually not *obviously* be more efficient. If you have to do 25 million
    comparisons then you have to do 25 million comparisons, and efficiency
    gains are made by working with the hardware efficiency limitations and
    with working with processor instruction pipelines and other
    system and hardware specific techniques.
    --
    "And that's the way it is." -- Walter Cronkite
     
    Walter Roberson, Aug 8, 2008
    #2
    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. LV

    .Net Comparison

    LV, Aug 27, 2003, in forum: ASP .Net
    Replies:
    4
    Views:
    1,407
    William Ryan
    Aug 31, 2003
  2. koperenkogel

    Remove elements pairwise from vector

    koperenkogel, Mar 31, 2005, in forum: C++
    Replies:
    11
    Views:
    642
    steflhermitte
    Apr 11, 2005
  3. Alan
    Replies:
    7
    Views:
    434
  4. Alan
    Replies:
    1
    Views:
    416
    Victor Bazarov
    Jun 4, 2007
  5. Deepu
    Replies:
    1
    Views:
    244
    ccc31807
    Feb 7, 2011
Loading...

Share This Page