0

The initial task was to find very quickly, free time for resources, let say - hotel rooms, services availability. I came with following model:

Let say we have 24h in 1 day, and 365(366) days in a year. 1) We have a sequence of bits

timetable=0001011....000, length(timetable) = 24*365 = 8760 0 is busy 1 is free.

So if we need to merge two timetables output is: 1 && 1 = 1 free and free give free, 1 && 0 or 0 && 0 = 0, busy and free or busy and busy give busy.

2) We have array of sequences:

arr = [timetable1, timetable2, timetable3....N]; N < 1,000,000

representing free/busy intervals for a timetable of some resources (hotel room, or any service counting in hours).

The task is the following:

We need to find free time in the following interval (i,j). i<>j, 0

-i,j can represent days interval in year, so we can reduce the initial long array by the rule above. Example, (120, 125) -i,j can represent hours interval in year, so we can use same array as above.

The total should be around 50-100 ms.

My algorithm is the following: 1) input is a sequence of bit 11111...1111 2) make bitwise "and" (&) with each timetable.

Bitwise operations are really fast, so I think this should be an optimal solution. Does anyone think that can be done better?

  • You want to merge up to a million timetables? I would think you'd need a way to filter that down (like an index) before you did the merge. Example: for each timetable could track "longest available slot" - that way if you need 6-week slot you can easily filter out any timetable that doesn't have any 6-day slots. – Robert Paulsen Mar 12 at 14:35
  • You want to merge up to a million timetables? - Yes. To get free items. – Alexandr Mar 12 at 14:39
2

'Better' is a word that has only meaning in relation to a cost-function (some function to map quality to a comparable entity like a number).

If we know nothing about the distribution of 'occupied' and 'available' hours, the one bit per hour idea guarantees a fixed amount of needed memory, no matter how the distribution of 'occupied' and 'available' is.

I could imagine, that in most hotels, the guest stay in most cases for much longer than 1 hour. If your data is of this kind, where occupied periods most over spread over a lot of hours, it might be also efficient to store the 'occupied'-intervals instead of a bit per hour.

You are right on all common systems, bit-operations are really fast, also (depending on the size of a long) you compare 64 bits at once.

But checks get tricky, if you search for intervals crossing long-boundaries. So be sure you considered all cases.

To make this simpler, let a long be 8 bits:

possible intervals to check:

... 00000000 xxxxxxxx xxxxxxx xxxxxxx 000000 .. interval starts and ends at a long-boundary

... 000xxxxx xxxxxxxx .... interval starts in the middle of a long

... xxxxxxxx xxxx0000 .... interval ends in the middle of a long

... 00xxxxx0 ... interval stards and ends within the same long

In the last 3 cases you must ensure correct masking of the relevant bits for your check

| improve this answer | |
  • 1) values will be stored in shorter format. But the conversion will be in format of bits. 2) interval check I want to simplify but not using long, just array and sub-array of bits. – Alexandr Mar 12 at 15:01
  • @Alexandr: Be careful depending on your programming language an array of bits might need much more memory than you expect (e.g. in java a boolean needs, depending on the VM up to 64 bit (see here: docs.oracle.com/javase/specs/jvms/se7/html/… )). – MrSmith42 Mar 12 at 15:24
  • @Alexandr also using a LONG[] can speedup the check up to 64 time, because you compare 64 bits with one instreuction. – MrSmith42 Mar 12 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.