What's the best way to access a string associated with non-contigouous number?

Posted on 2008-10-07
Last Modified: 2012-05-05
What is the optimum way (least processor intensive) to retrieve the string that is associated with one of a set (array) of non-contiguous integer values?

The situation is this:  I'm implenting a color-of-screenpixel function in one of my applications and I want to display the html hex value <unless> it matches one of the set of named HTML colors.  There are 147 of them as of now - for example here are the first 16 in the list:  (Note this is snipped from a web page and I've not "delphized" the numeric values yet.)
AliceBlue       #F0F8FF
AntiqueWhite       #FAEBD7
Aqua       #00FFFF
Aquamarine       #7FFFD4
Azure       #F0FFFF
Beige       #F5F5DC
Bisque       #FFE4C4
Black       #000000
BlanchedAlmond       #FFEBCD
Blue       #0000FF
BlueViolet       #8A2BE2
Brown       #A52A2A
BurlyWood       #DEB887
CadetBlue       #5F9EA0
Chartreuse       #7FFF00
Chocolate       #D2691E
etc. etc.
I could put them into a structure of Int for the hex value, string for the name and loop through the structure array and look for the interger value match.  But maybe there's a better, faster way.  This function will be inside of a fast timer and get hit everytime the cursor position changes.
Question by:DMTrump
  • 3

Accepted Solution

JosephGlosz earned 500 total points
ID: 22666271
This is a classic database lookup problem. If you just put that list into an array, you might end up having to do 147 integer comparison when the target is IN the array. Or, on average, some 75 comparisons each time you do find a match. When there is no match, you'd have to check 147 integers to know there isn't a match. And that seems very slow.

Instead, make that list an ordered array. And do a simple binary search. On the first comparison, you can narrow the search to the top or bottom half of the list. On the second comparison, half of THAT list, and so on.   Sometimes you'll get lucky and hit it before you have to get to the final two and sometimes you won't.

But you'll always have no more than 7 or 8 comparisons to make.

An alternate but similar way would be to classify those 147 values into 16 "buckets" labeled 0 thru F.   Each bucket would be a dynamic array that holds all the values that start with that 0 thru F value.

On average, each bucket would hold 7 or 8 values.  Given the first hex value of the target integer, you could just search sequentially through that one bucket's values, and make no more than 7 or 8 comparisons before you know the answer.

Or you could combine the two methods and do the binary search inside each bucket and end up never having to do more than 4 or so comparisons.

Since the binary search is recursive, this should be easy to program up!


Expert Comment

ID: 22666279
To follow up on this, when I said make that list an "ordered array" I meant to have the list be sorted in order of that hex value.  From smallest integer to largest. You can do this programmatically, once, or since it's a fixed list, just create it in sorted order manually.
LVL 37

Expert Comment

by:Geert Gruwez
ID: 22666778
your list is ordered by alphabet, the numbers aren't ordered
switching the ordering should be a piece of cake
if you want to maintain the original list, make a copy of it, with the original indexes and sort by color
then use the original index found on the original list to find the color name

Expert Comment

ID: 22666874
Huh? No, the list as given by DMTrump is ordered by the English name of the color. We want to order it by the  integer itself in order to compare those with the integer of the color that's under the cursor.  We don't need to make any copy of the original list. Just have a single array of records, sorted by the integer color, as I stated earlier. We don't care that the English names are not alphabetized. They'll automatically be associated with the integer color by virtue of being part of the same record.  For example:

  TColorRec = record
     Value:   integer;   // or Int64
     Name: string;

  Colors: array of TColorRec;

  Colors[0].Value := $000000;
  Colors[0].Name := 'Black';

  Colors[1].Value := $0000FF;
  Colors[1].Name := 'Aqua';


you can hard code these like above, or read them in from a text file, or make a constant array, etc.  In the example above, I manually ordered the array in the correct order, given the 16 example values given in the original question.


Author Closing Comment

ID: 31504095
Great answer - and well thought out.  I knew that was an alternative, but was hoping there might be something I didn't know about Delphi/Pascal that would make it easier to do on the fly.

However, I've decided NOT to do it on the fly.  The user will be moving a cursor around on the screen and I show a "magnified" zone of 25 pixels constantly updated - but when the proper color is found (the 2,2 - center of the 5by5 box) it can be locked in" (picked)  THEN I'll check to see if it matches one of the named HTML colors and display that, otherwise just show the hex integer value.


Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Delphi with SQL Natvie Client 15 86
Best Firemonkey component pack 1 88
Delphi: Connect to running MS Outlook 4 50
How to build JSON File in Delphi 6 3 17
This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
Migrating to Microsoft Office 365 is becoming increasingly popular for organizations both large and small. If you have made the leap to Microsoft’s cloud platform, you know that you will need to create a corporate email signature for your Office 365…
Learn how to create flexible layouts using relative units in CSS.  New relative units added in CSS3 include vw(viewports width), vh(viewports height), vmin(minimum of viewports height and width), and vmax (maximum of viewports height and width).

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now