The Mother Board

Motherboards.org forums. Free tech support, motherboard ID, and more.
It is currently Tue Oct 16, 2018 1:08 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Mon Jul 17, 2006 10:41 pm 
Offline
Green Belt
Green Belt

Joined: Tue Jun 04, 2002 2:51 pm
Posts: 223
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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Fri Aug 11, 2006 4:43 am 
Offline
Mobo-fu Master
Mobo-fu Master

Joined: Sun May 06, 2001 12:01 am
Posts: 37464
Location: Netherlands
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...


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed May 30, 2007 5:04 am 
Offline
Initiate
Initiate

Joined: Fri May 11, 2007 12:57 pm
Posts: 23
Location: Denmark
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:
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).


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group