Solved

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

Posted on 2008-10-07
5
183 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 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
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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
TEMBEDDEDWB how can i change its user agent ? 8 99
Delphi android app hide keyboard 3 77
Get weeknumber and year from date 4 53
Automatic field translation delphi 10.2 6 39
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
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…
In an interesting question (https://www.experts-exchange.com/questions/29008360/) here at Experts Exchange, a member asked how to split a single image into multiple images. The primary usage for this is to place many photographs on a flatbed scanner…
Finding and deleting duplicate (picture) files can be a time consuming task. My wife and I, our three kids and their families all share one dilemma: Managing our pictures. Between desktops, laptops, phones, tablets, and cameras; over the last decade…

742 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