Solved

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

Posted on 2008-10-07
5
178 Views
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.
0
Comment
Question by:DMTrump
  • 3
5 Comments
 
LVL 6

Accepted Solution

by:
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!


0
 
LVL 6

Expert Comment

by:JosephGlosz
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.
0
 
LVL 36

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
0
 
LVL 6

Expert Comment

by:JosephGlosz
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:

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

var
  Colors: array of TColorRec;

begin
  SetLength(Colors,174);
  Colors[0].Value := $000000;
  Colors[0].Name := 'Black';

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

  etc...

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.


0
 

Author Closing Comment

by:DMTrump
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.

Thanks
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

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…
Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This tutorial demonstrates a quick way of adding group price to multiple Magento products.

708 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

12 Experts available now in Live!

Get 1:1 Help Now