searching an array

[jome]

hi, im in the process of making a booking system using delphi 3, but i do not know how to search an array. i would like to be able to search the array to see what dates have been booked, and which ones are available. if anyone could help with this it would be much appreciated.

ps. if anyone already has a simple booking system i would be very grateful if you could some how send it my way so that i could tamper with the code a bit. thanks.

 

[Glenn9999]

A lot of the answer is going to depend on what you're looking for specifically and whether this array is sorted or not.

Beyond that, what will work on any array is a simple iteration if you're wanting to canvas the whole array, like it sounds like you're doing, as opposed to trying to find out whether a specific date is booked or not.

for i := 1 to array_size do
  begin
    write(myrecord[i].date);
    if myrecord[i].booked = true then
       writeln('BOOKED':20)
    else
       writeln('NOT BOOKED':20);
  end;

 

[ChrisGSchultz]

G'day Les,

Although I haven't done this - I have looked into it in the past. I assume your data structure will include date-time, string and numeric types.

Arrays get very messy to search, and hard to maintain if things go wrong (eg your on leave and it breaks). I tend to use arrays of records as transient data, and keep the main data in a database on the system - to allow search/edit/adding of data.

So the other way to think about this is to use a database (eg Access via ADO, or mySQL and PHP if you'd like a web interface), with various keys such as date, person etc. Depending on complexity, you have a primary database of rooms or people, and add linked tables for the details, including dates when they are booked.

Searching then becomes a matter of writing some appropriate SQL - a lot easier than searching specific array records IMHO

If you do a Google search on Booking System Design (use the groups tab for forums like this one) you might get some more pointers. I found a pile of useful tips and links in the first page.

Good luck!

Cheers,
Chris

 

[Griffyn]

Depending on how often you refer to your array, you may want to convert your program to use a TList object (or TObjectList if you convert your array records to a class object).

Also - if you have a large number of elements in the array (say, more than 500) then I highly recommend you use a QuickFind algorithm.

First, sort your array (if you you're using a TList object then you can easily implement a sort routine). Then to find an element using the following algorithm.

Set two pointers (p1, p2) to the first and last elements in the array. Then repeat the following:

Set a third pointer (p3) to the element roughly (or exactly) midway between the two. If the variable in p3 your searching on is equal to what you want, then stop - you've found what you're looking for. Otherwise, if p3.variable is less than what you're searching for, set p1 to p3+1 and repeat the loop. Otherwise set p2 to p3-1 and repeat the loop.

Make sure you set up checks to make sure p2 is never less than p1. When it is, the search should return a failure.

This method of dividing the array into smaller and smaller halves is the most effective method of searching a large array.

 

[Glenn9999]

The method described above only works well when the array is pre-sorted. If you have to sort it, you would have to do 1000's of searches to simply break even time-wise.

So if you have to sort the array, better bet is to just search it sequentially.

 

[Zathras]

Probably the easiest way is to use TStringList objects. The .Find method is already using the binary search algorithm that Griffyn has outlined. (When the TStringList is sorted.)

But unless your hotel has more than 10,000 rooms, I don't think you will see much difference between linear and binary search times at the user interface. Which is what Glenn9999 has suggested.

In any event, TStringList with .Find (sorted) and .IndexOf (unsorted) search methods, provides all of the search power you should require.

Create TRoom objects (or some such name) and put them in a TObjectList and a TStringList at the same time. The TObjectList will take care of freeing all of the TRoom objects you created when you free the TObjectList, and the TStringList can hold pointers to the same objects while providing a lookup capability by storing the dates in the strings.

Of course, you don't need a separate TObjectList as long as you remember to free the TRoom objects yourself.

 

[Griffyn]

Hi Glenn9999 and Zathras.

Good advice there, however in regard to the break-even time of pre-sorting and searching, there are times when this ratio doesn't apply.

For example, if your program was required to do a search during a time-critical operation (say, as the user was typing) then it may be in the best interest of the user to do the sort at application launch as part of it's initialization routines, even if it took 15 seconds, users are more forgiving of time delays launching the application than they are waiting for it while it's running.

 

[Nordlund]

I noticed a thing Zathras wrote, but it's far away from the initial question...

Probably the easiest way is to use TStringList objects.

I often do multiple searches in unsorted lists which can take up to 4 minutes to perform. Very gigantic lists indeed.

I discovered a useful list called THashedStringList (unit Inifiles). This stringlist create a hash first time you search in it... The second search is done very fast...

Just a tip...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-"There is always another way to solve it, but I prefer my way.

 

[Glenn9999]

even if it took 15 seconds, users are more forgiving of time delays launching the application than they are waiting for it while it's running.

I found the opposite, really, in a case. One design we had, was something that indexed some data so it could be accessed almost instantaneously. The indexing routine, however, took about 5 seconds in testing and turned out to be unacceptable to the user, considering there would be much more data in production.

So we ended up going from "almost instantaneous" to 1 to 3 seconds...I guess users understand "waiting to find the record" a little better than "we're preindexing it all so you don't have to wait".

All depends on your user. But in general, you don't want to sort a table (or anything) unless you are doing 1000's of searches to pay back the time. Because on most systems, you really will get more of a hit doing the binary search (halfing index), unless you have a large number of records. And that number is really sufficiently large that a sequential search won't make much of a difference.

 

[Nordlund]

Yep, the quote is on the nail right.
We had similar problem earlier, but in this case it was ordinary queries to our support tables.

We did a rather nifty solution; Download all the background data and store them locally on the clients. Then we added a local trigger to check when the background data was changed. If it was changed, the client had to download it, otherwise it was loaded locally.

The loginprocess took a long time to perform, but with the active progresswindow made the users to forget time...

From this day, all complaions about delays where gone...


As I mentioned, the THashedStringList is very useful when you have to do multiple searches in the same stringlist and when the list cannot be sorted.

With multiple searchs, I mean about 300 searches. Don't ask why you have to do 300 searches from one stringlist...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-"There is always another way to solve it, but I prefer my way.