Data Structure help required.

[babai28]

Hi there,

I have a situtation, I am on my way to build an alarm application which will run in the background and will intimate the user for an event which he had set before. Exactly what a scheduler or alarm clock does.
I will explain the design in short here. I maintain the tasks set by the user in a list of "Task" class. With every tick of the timer I initiate a background thread that will poll the task list to check if there are any tasks for the present time stamp. If yes it will raise an event which does the work of intimating the user by playing a music and displaying a form.
The, back ground thread is needed so that the main thread does not have to wait for the scanning of the list.
So far so good. The application is working well. But I know at heart that the List is not a good thing to use in this case as the application will terribly fail if the list is too long. may be the user will be intimated 2-3 mins after the time he may had set his alarm to.
I request for suggestions about which data structure to use here, if not list. I know there are some very fast list like structures (Like something used by the word suggesting thread of the MS Word, as it can pick up words from huge ocean of words.). However I dont know what they are and how to use them. If you suggest a design change, I whole heartedly shall agree. I know it is not a very good design.
Sincerely looking for your suggestions.

Regards,
Sid

[tlhintoq]

A couple ideas that might help:
Sort your tasks by time. Now you don't have to search all of them. As soon as you check a task that in the future you know that every task beyond it is also in the future, so stop searching.
Keep a marker variable set to the index of the last used task. Now you don't bother checkng tasks that have already been run today.
At this point your search is only from 'marker' to 'future' instead of the entire list.

[GaryTexmo]

If you want something truly efficient, you'll likely have to write your own storage and search. Try a google on search algorithms, there are a lot, and you'll need to pick the one that's best for you.

You also have the option of built-in structures to help you. You're using a List... I'm not sure what the code behind your search and retrieve is, but it's likely linear. My suggestion would be to try a HashTable as they have very fast retrieval mechanisms.

However, you'll still have to keep track of the data intelligently. As Thlintoq said, you can safely ignore anything that's past what you're looking for. The hash table might help you group things... like, tasks that are all for a specific day (or half a day) could be stored in the same hash location, so when you search you just pick up the items that are reasonably close to what you're looking for. Then you would do a linear search on that particular group.

A pseudo-code example of what I'm trying to say...

struct TaskStorageObject
{
  string key;
  List<Task> taskList;
}

HashTable taskStorage = new HashTable();

main method
{
  ...
  Task myTask = new Task(<DateTime object for occurance>, <whatever>);
  InsertTask(taskStorage, myTask);
}

InsertTask(HashTable taskStorage, Task taskToInsert)
{
  string key = taskToInsert.TaskTime.Date.ToString(); // ie, "21-10-2009"
  TaskStorageObject taskSet = taskStorage[key];
  if (taskSet != null)
  {
    taskSet.taskList.Add(taskToInsert);
  }
  else
  {
    // create a task storage object, put your task in it, and put it in the hash table
  }
}

Retrieval would be done in a similar way... you'd have a DateTime for what you're looking for so you'd get the TaskSet for the day and then perform a linear search on that to find the particular task.

You can break it down however you like though, I'm just trying to throw out suggestions. Between this and what Thlintoq wrote, hopefully you've got a few ideas now :)

(Does this seem reasonable or make sense?)

[babai28]

Data Structure help Required

Thanks tlhintoq and Thank You Gary for your ideas. I think I have got the idea.
manipulating the List/Hashtable with every alarm event is the need.
Also this will save me from initiating the background thread for every timer tick.

Regards,
Sid