APM: Sparse arrays

[Brian Michalk]

Well, the data is a profile of pavement collected from a laser.  An individual trace can be up to 30 meters long at eight samples per millimeter.  The number of points in a trace varies.  I have approximately 5,000 such traces.
I have to filter the data to get meaningful information out of it.  The culprit algorithm in question needs to determine which part of the pavement is actually touching the tire.

Due to finite element analysis, I know that approximately 5% of the tire patch contact area actually touches the tire.  It is this 5% that I'm extracting.  My filtering window is 50 millimeters long, or 400 points.  I prime a stack, pushing and popping elements into the window, and analyze for each individual point in the window (stack)  When I find the datum representing 5% contact area, I pop the last element and subtract the current datum value.  Next, I unshift the next point in the trace into the stack and repeat all over again.

This algorithm works, and produces repeatable results.  However, the computational power to use this brute force method is too much.  I need to convert the data into a histogram, and then start at the high end of the histogram, iterating over the indices until I've found 5% of the sample population.

Using a hash and sorting the keys does provide a performance increase.  However, an array is essentially already sorted, and would be ideal if I knew what the indices were when I do a foreach over it.  I thought about using another array to keep track of the indices, and that's probably what I'll do.  I was just wondering if there was a better method of doing it.

Someone keeps telling me that theres always another way to do it in Perl.

This code is not meant to be portable, and if I have to break into the guts to find pointers, addresses and break all sorts of encapsulation, then I'll do that.
  -----Original Message-----
  From: ezra pagel [mailto:ezra at jdba.org]
  Sent: Thursday, July 10, 2003 9:50 AM
  To: Brian Michalk
  Cc: austin-pm at pm.org
  Subject: Re: APM: Sparse arrays


  # $numberOfElements = scalar @ary;
  # $lastArrayIndex = $#ary;

  foreach $idx (0..$#ary) {
    $element = $ary[$idx];
    print "$element is at index $idx in \$ary\n";
  }

  tell us a little more about your data and your hardware environment, and maybe we can help w/ performance. it shouldn't take days to iterate an array; i guess it's possible that you've got massive swap space and you're seeing nothing but i/o thrashing, but that's not likely either.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/pipermail/austin/attachments/20030710/95e6ac36/attachment.htm