[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: appointment data structure
From:       Kurt Granroth <granroth () kde ! org>
Date:       1998-08-19 0:55:49
[Download RAW message or body]

Just my take on matters...

To answer the question "which structure should I use," I think you first
need to answer "what is more likely to happen?"  Right now, *every* time
you access a given day, you need to parse through the entire list of
recurrences to see if it matches.  As you found out, this can be a fairly
intensive procedure if the list is large.

The basic problem is that you are using a very expensive action on a very
common action (I am assuming that you will access appointments very
frequently).  It would be interesting to see just how many data entries
(counting searching for the appt and looking for recurrences) are accessed
EACH TIME you try an view an appointment.  I'm guessing that there is a
lot.

A way around this, of course, would be to "pre-calculate" all recurrences.
This would take a pretty expensive one-time hit... but after that, accessing
each appointment would only take accessing ONE data entry -- the appointment
itself.

You raise a valid concern that ALL appointments will need to be recalculated
when one is deleted... but how often does this happen?  If, say, a user
will commonly delete a recurrence once a MONTH or so, then this added
time might very well be worth it if is speeds us DAILY, frequent accesses.

One possible way to mitigate this is to still have a separate list for
recurrences.  When a new recurrence was added, it would be inserted into
the proper places into the "main" appointments and also inserted into
the list.  When it came time to delete the recurrence, the information 
on *where* it is is stored in the list so deleting it should be in N
time.

The "no end date" restriction is a little tougher.  You are right that
it is hard to represent in a date hash.  A workaround would be to have
the recurrence "fill in" only to the last made appointment or some
arbitrary later date (a year?) -- whichever is later.  Once a session
(or day or so), KOrganizer could iterate through the recurrences and 
see that it continues for a least that arbitrary length of time.  The
only sticky point would be when users tried to view a date PAST then.
But how common is this?  Do people randomly look at, say, the first
Wednesday of June of next year?  Probably not.  In the few cases where
people may want to view a date in the future AND expect their recurrences
to appear, it might be possible to generate it on the fly.

Now this last instance might seem to bring us back to where we were at
the beginning... but not really.  In the current case, we are doing an
expensive action very frequently.  In the above case, this action would
be performed only rarely (unless there was an atypical user).

But I'm starting to ramble....

Just my $0.02
Kurt Granroth

On Tue, Aug 18, 1998 at 08:55:29AM -0400, Preston Brown wrote:
> Hello intrepid KDE developers:
> 
> I was sitting last night at my computer, trying to think if I couldn't
> have a better data structure for storing appointment information in
> KOrganizer.
> 
> Right now, I have a dictionary (hash) based on day/month/year (date), and
> inside that hash are buckets (qlists) of all appointments on that
> particular date.
> 
> I maintain a SEPARATE list of appointments that recur, they do not get
> inserted into this primary data structure.  That's for two reasons:
> 
>  * some recurring appointments have no end date.  Hard to represent in the
>    first datastructure, right? :)
> 
>  * if a recurring appointment was deleted/changed, all "pre-calculated"
>    instances of the appointment would need to be deleted/changed as well,
>    instead of this one entry in the recurrence list.
> 
> Therefore, when I look up appointments on a given day, I go to the qdict
> of qlists, and grab the qlist, and then do a dynamic calculation on each
> appointment in the recurrence list to see if it should be added to the
> list of appointments for the day.  Then I return this conglomerate list.
> 
> This is starting to seem inflexible for a number of reasons:
> 
> 1. if there are a lot of recurring appointments, things can get slow (I
> mean a *LOT*, but I am trying to have this program scale well)
> 
> 2. You can't easily step through appointments in a linear fashion with the
> current data structures (i.e. a next appointment, previous appointment
> button)
> 
> 3. other misc issues.
> 
> So I guess what I am asking is: does anyone have an idea for what they
> think would be a better way?  Remember, you have to take into account the
> issues I have mentioned above.
> 
> The ideal way has:
> 
> 1. fast linear access
> 2. fast search access
> 3. quick insertions and deletes
> 
> ---
>   Preston Brown          
>   Red Hat Software, Inc. 
>   pbrown@redhat.com      
> 
> 

-- 
Kurt Granroth
granroth@kde.org
http://www.pobox.com/~kurt_granroth

[prev in list] [next in list] [prev in thread] [next in thread]