Help with mergeing data algorithm

Discuss all aspects of programming here.

Moderator: The Mod Squad

Help with mergeing data algorithm

Postby cangove » Mon Jul 17, 2006 10:41 pm

Ok been racking my brain for an "intelligent" solution to my problem set. I think that I may have frie my brain and msising something obvious. So onward with the asking.

I have a set of time based data. Each piece of data ahs a start time and an end time. The incomming data can overlap, and is not aligned with each other in any way. What I need to do is take this data, and create new set of values, broken down into overlaping bits (adding the values for voerlap, althoguh eventually I may have to average them as well). For example if given:

start end value
0 100 100
25 50 200
50 75 300

I would get
0 25 100
25 50 300
50 75 600
75 100 400

In the simple case above its pretty easy to do by hand. But it gets more difficult as the size of data gets bigger and the overlaps weirder. All of the solutions I come up with are exponential which will not work as I may be dealing with 1million+ data points here. Any ideas on an algorithm?
Shuttle SN45G, AMD AthlonXP 3000+, 2x512MB Crucial DDR333, 80GB WD HD, Sony DRU-720A DVRW, MSI Radeon 9800 Pro 128MB, Dell 24" widescreen LCD
cangove
Green Belt
Green Belt
 
Posts: 223
Joined: Tue Jun 04, 2002 2:51 pm

Postby evasive » Fri Aug 11, 2006 4:43 am

you will have to assign each chunk an activity pointer and and a value pointer. You then add all pointer values times active/non-active.

Not sure how to code it because programming language not given but I think that's the way to go...
We hate rut, but we fear change.
********************************
System error, strike any user to continue...
evasive
Mobo-fu Master
Mobo-fu Master
 
Posts: 37389
Joined: Sun May 06, 2001 12:01 am
Location: Netherlands

Postby rilorilo » Wed May 30, 2007 5:04 am

Assuming your data has been put into a linked list with the following structure, it would go something like this:

data.start = 0
data.end = 100
data.value = 100
data.next = [next data entry]

code:
Code: Select all
if (data is not sorted)
{ sort(data by start) }

nextdata = data;
while (date.next is NOT NULL) // search the entire linked list
{
 nextdata = datanext.next;
 if (data.end <= nextdata.start)
 {
   data = data.next
   nextdata = data
 }
 else if (data.start = nextdata.start)
 {
   if (data.end >= nextdata.end)
   {
      break data up and insert into sorted linked list
   }
   else
   {
     break data up and insert into sorted linked list
   }
  }
  else if (data.start < nextdata.start)
  {
   if (data.end >= nextdata.end)
   {
      break data up and insert into sorted linked list
   }
   else
   {
     break data up and insert into sorted linked list
   }
 }
}



O(break data up and insert into sorted linked list) = O(log(n))
O(while loop) = O(n(n-1)+(n-1)(n-2) ...) ~ O(n(n+1)n) = O(n^3)
So you have a running time close to O(n^3 * log(n)) for the big loop, and the sort function can be done in like n log n time thus being slower than n^3 * log(n).
rilorilo
Initiate
Initiate
 
Posts: 23
Joined: Fri May 11, 2007 12:57 pm
Location: Denmark


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest

cron