Need help with fast implementation

try like this, its the best I can do...

int i,j, daysOff = 0;
for (i=0; i  daysOff=0; 
  for (j=i; j      if (array[j]) ++DaysOff; 
  if (count < n1) 
    return false;
}
return true;
 

int i,j, daysOff = 0; for (int i=0; i<DaysInMonth; ++i){ daysOff=0; for (int j=i; j<i+8; ++j) if (array[j]) ++DaysOff; if (count < n1) return false; } return true;

Thanks. Basicly the same approach though

Im not sure exactly what im hoping for here, but with these forums you''ll never know .

That might be a good candidate for some inline-assembly action

Assembly isnt my force (to put it nicely). But inline it already is . Thanks for the suggestion.

Look up sparse matrices. They''re used in business simulations that may have correlation matrices spanning 10000x10000, but may only contain 500 values (0.5% population).

The fundamental idea is not to store all the data, but rather only to store the data you''re interested in. While the logical construct to your mind may be an array/vector, but a map or hash table may be a more appropriate way to store. Say we index per user id, have a days_off structure like so:

struct days_off
{
  //.. other necessary data
  vector days_taken;
}; 

For each day off an employee takes, simply push_back(&off_date) on the vector and then assess whether the number of days between the first and n1^th off day is less than 8, between the first and n2^nd is less than 14, and so on (any of the above is a violation, or whatever).

You get the picture.

I''m sorry, I forgot to say exactly how to store the data:

#include <map>
//.
typdef map<emp_id, days_off> DaysOffMap;
DaysOffMap employeeDaysOff;
// to add a new record:
emp_id id;
id = GetNewID(...);   // hypothetical function
days_off do;
InitDaysOff(id, &do); // ditto
DaysOffMap[id] = do;  // this creates a new record if one doesn''t exist
 

Oluseyi, Thank you

Exactly what i was looking for. I cant believe i didnt think of that myself .

I figured since RAM isnt an issue that i might as well store all the data. Never thought that another data structure might give me advantages.

Now the only question is if i have time to rewrite my code

Glad to have been of service.

Btw, even though on industrial server-class machines RAM may not be an immediate issue, it''s always a good idea to write your apps to be as lean as possible since it makes for longer life and extensibility to larger datasets.

Good luck with the program.

I''m a bit tired & have been drinking (drik stor øl og vodka med coke [my Danish isn''t very good ])... but:

If I understand your problem, you''re doing 8 times as much work as you should be since the inner array is checking 8 days for every day in the month.

A much quicker approach would be to see how many consecutive days there have been...:

count = 0; for (day=0; day<daysInMonth; ++day) { if (array[day]) { // day is taken off so increase counter ++count; } else { // day isn''t taken off so reset counter // the counter represents how many consecutive // days have been had off count = 0; } if (count < n1) return false; }

For an array of days, for most tests you should only need to read each array element ONCE - if necessary, have multiple counts. For a lot of operations, it''s memory accesses you want to avoid. Simple counters will be optimised by the compiler. Theres not much it can do about memory accesses!.

Re-writing it in assembly would be a bad and naive choice IMO, optimising compilers do a perfectly good job of code like this.

A novice assembly programmer hand-coding everything in assembler is an almost guarantees code which will be slower than what the optimising compiler would do!.
I''ve known how to program assembly language for over 10 years and consider myself pretty competent at it - however 98% of the code I write (professionally and at home) is C or C++. Any dip into assembly language (exept on specialist co-processors on consoles) is always led by the output of a profiler such as VTune.

Hand tuned assembly may if you''re very good and lucky get you a 1.5 to 2 times speed increase. Rethinking the algorithm and data structures (see above) tends to get more like a 10 to 5000 times speed increase. Look at all algorithms long before you consider any assembly.

--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com

oops a tad late in posting that but still relevent... - I should have updated my browser view

--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com

*Hides in shame*

Thanks S1CA, This will probably be my approach, since, as i said, time is running out.

Damn, shouldve asked long ago .

Edit: Ack, S1CA that approach, as you point out, will only count consecutive days off. Ive no garantee that this will be the case (actually i know it wont).

Thanks anyways.

Edited by - NewDeal on November 25, 2001 7:24:00 PM