Lookup Table or Hash Table 
Author Message
 Lookup Table or Hash Table

Hi, I am not a C expert, but needs to implements a look up table on a
16-bit processor using C. A 256 data should be enough for what I want
to do. My table should contains two columns of data. 1st one is the
calculated power, and the second is the voltage of the associated
power. THis voltage should be stored in the memory so that it can be
fed to the outside world.

Is there any sample C algorithm nearer to this task that I can study?
I was told that Hash Table should be faster in performance.

To be honest, I dont really know how to write a look up or hash table.

Any advice?

Thanks

Green



Mon, 25 Jul 2005 08:09:05 GMT  
 Lookup Table or Hash Table
I meant I dont really know how to write an efficient lookup table.

What about fitting the lookup table into an equation?? Would that be better?

Quote:
> Hi, I am not a C expert, but needs to implements a look up table on a
> 16-bit processor using C. A 256 data should be enough for what I want
> to do. My table should contains two columns of data. 1st one is the
> calculated power, and the second is the voltage of the associated
> power. THis voltage should be stored in the memory so that it can be
> fed to the outside world.

> Is there any sample C algorithm nearer to this task that I can study?
> I was told that Hash Table should be faster in performance.

> To be honest, I dont really know how to write a look up or hash table.

> Any advice?

> Thanks

> Green



Mon, 25 Jul 2005 17:58:12 GMT  
 Lookup Table or Hash Table

Quote:

> Hi, I am not a C expert, but needs to implements a look up table on a
> 16-bit processor using C. A 256 data should be enough for what I want
> to do. My table should contains two columns of data. 1st one is the
> calculated power, and the second is the voltage of the associated
> power. THis voltage should be stored in the memory so that it can be
> fed to the outside world.

> Is there any sample C algorithm nearer to this task that I can study?
> I was told that Hash Table should be faster in performance.

Colin...

There are a lot of ways to solve this problem. I'll provide you
with one approach to a look-up that makes the assumption that its
more desirable to underpower than overpower; and that if all the
values in the table would result in overpowering your circuit,
your program will want to do some kind of error recovery.

First of all, lets make a 256-element look-up table. I decided to
use an array of structures, each element of which contains a
power value and a voltage value, arranged in order of increasing
power values:

    struct
    {  double power;
       double voltage;
    }  look_up[256] = /* Your init value pairs here */;

So now we need a function that takes a power and returns the
voltage associated with the highest table power that doesn't
exceed the target:

    double power_to_voltage(double power)
    {  int i;
       for (i=255; i >= 0; i--)
       {  if (power >= look_up[i].power)
          {  return look_up[i].voltage;
          }
       }
       return VOLTAGE_ERROR;
    }

Note that you'll need to define VOLTAGE_ERROR somewhere; and that
it'll need to be a value that power_to_voltage() can legally
return (a double in this example).

This is fairly straight-foreward. A hashing approach might be
much faster; but if you're at a stage where you're unsure of how
to code a table look-up, the simpler the better.

HTH
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c



Mon, 25 Jul 2005 18:53:07 GMT  
 Lookup Table or Hash Table


Quote:

>Hi, I am not a C expert, but needs to implements a look up table on a
>16-bit processor using C. A 256 data should be enough for what I want
>to do. My table should contains two columns of data. 1st one is the
>calculated power, and the second is the voltage of the associated
>power. THis voltage should be stored in the memory so that it can be
>fed to the outside world.

>Is there any sample C algorithm nearer to this task that I can study?
>I was told that Hash Table should be faster in performance.

>To be honest, I dont really know how to write a look up or hash table.

>Any advice?

>Thanks

>Green

Hello Colin,

If your table only contains 256 entries consisting of pairs of numbers, you
don't need to worry about speed of execution unless there's some extremely
stringent requirement on the response time.

I guess one could imagine cases where lookups would occur extremely frequently
(say, millions of lookups per second); if that's what you're facing then of
course your concern is justified.

But unless you have those tough requirements, it's better to use a simple
brute-force algorithm. Easier to code without making mistakes, and easier to
understand if you need to revisit it at some later date.

Good luck,
PP



Tue, 26 Jul 2005 07:10:17 GMT  
 Lookup Table or Hash Table
Hey Morris and Pika,

Thanks a lot for the help.

1) Compilation of the following code gives me errors:(as attached
below)
Compiling...
lookup_test.cpp
(23) : error C2601: 'power_to_voltage' : local function definitions
are illegal
(40) : fatal error C1004: unexpected end of file found
Error executing cl.exe.

2) How do you construct two column table in arrray. I know one column
table can be constructed as below

 for example if Power = 1; voltage = 200

then a table of one column is created as

 voltage[0] = 3000;
 volatge[1] = 200; and etc...for voltage being a 257 data array

and to get the voltage when power = 1 is

voltage[power] = 200 as voltage[1] = 200;

3) when you initialise the structure as in your code like below, the
(2000, 300) is storedd in look_up[0] isntead of look_up[1] right?

Thanks...sorry for the trouble...
-----------------------------------------
#include<stdio.h>

double power_to_voltage(double);

main()
{
    struct
    {  double power;
       double voltage;
    }  look_up[257] = {2000, 300};

    double power_to_voltage(double power)
    {  
                int i;

                for (i=255; i >= 0; i--)

           {    
                        if (power >= look_up[i].power)
          {  
                        return look_up[i].voltage;
          }

           }
           return VOLTAGE_ERROR;

Quote:
}

--------------------------------------------


Tue, 26 Jul 2005 18:42:48 GMT  
 Lookup Table or Hash Table

Quote:

> 1) Compilation of the following code gives me errors:(as attached
> below)
> Compiling...
> lookup_test.cpp

C and C++ are different languages. Do not confuse one with the other. If
you write C, call your file lookup_test.c to prevent your compiler from
treating it as C++. If you write C++, consult the people in
comp.lang.c++.

Quote:
> (23) : error C2601: 'power_to_voltage' : local function definitions
> are illegal

Seems a simple, clear error message to me. Local function definitions
are not allowed in C. You can define functions only at file level, not
within another function's body. You'll have to move the definition of
power_to_voltage() outside of main(). If you don't want it to be visible
program-wide, make it static, then it'll only be visible in this source
file.

Quote:
> (40) : fatal error C1004: unexpected end of file found
> Error executing cl.exe.

I wouldn't be surprised if the previous error were capable of confusing
the compiler's parser, since it is a rather fundamentally syntactical
one; but in this case, you really do seem to be missing the final } in
main().

Quote:
> 2) How do you construct two column table in arrray. I know one column
> table can be constructed as below

>  for example if Power = 1; voltage = 200

> then a table of one column is created as

>  voltage[0] = 3000;
>  volatge[1] = 200; and etc...for voltage being a 257 data array

No, it isn't. In fact, you do not have an array called voltage[] at all;
you have an array called lookup[], each member of which is a struct with
the members power and voltage. You only explicitly initialise the first
of these structs, whose power will be 3000 and whose voltage is 200; the
rest will be initialised to {0,0}.

Quote:
> 3) when you initialise the structure as in your code like below, the
> (2000, 300) is storedd in look_up[0] isntead of look_up[1] right?

Yes. So, if you understand this, what exactly did you mean in question
2? You have no voltage table at all.

Quote:
> main()
> {
>     struct
>     {  double power;
>        double voltage;
>     }  look_up[257] = {2000, 300};

>     double power_to_voltage(double power)
>     {  
>       return VOLTAGE_ERROR;
> }

Note the misleading indentation. This brace actually belongs to
power_to_voltage().

Richard



Tue, 26 Jul 2005 20:35:46 GMT  
 Lookup Table or Hash Table

Quote:

> Hey Morris and Pika,

> Thanks a lot for the help.

> 1) Compilation of the following code gives me errors:(as attached
> below)
> Compiling...
> lookup_test.cpp
> (23) : error C2601: 'power_to_voltage' : local function definitions
> are illegal
> (40) : fatal error C1004: unexpected end of file found
> Error executing cl.exe.

> 2) How do you construct two column table in arrray. I know one column
> table can be constructed as below

>  for example if Power = 1; voltage = 200

> then a table of one column is created as

>  voltage[0] = 3000;
>  volatge[1] = 200; and etc...for voltage being a 257 data array

> and to get the voltage when power = 1 is

> voltage[power] = 200 as voltage[1] = 200;

> 3) when you initialise the structure as in your code like below, the
> (2000, 300) is storedd in look_up[0] isntead of look_up[1] right?

> Thanks...sorry for the trouble...
> -----------------------------------------
> #include<stdio.h>

> double power_to_voltage(double);

> main()
> {
>     struct
>     {  double power;
>        double voltage;
>     }  look_up[257] = {2000, 300};

>     double power_to_voltage(double power)
>     {  
>            int i;

>            for (i=255; i >= 0; i--)

>       {    
>                    if (power >= look_up[i].power)
>           {  
>                    return look_up[i].voltage;
>           }

>            }
>       return VOLTAGE_ERROR;

> }
> --------------------------------------------

Hi,

This is terribly wrong. In C, functions cannot be nested.

Cheers
Nagaraj C



Tue, 26 Jul 2005 23:36:36 GMT  
 Lookup Table or Hash Table

Quote:

> Hey Morris and Pika,

> Thanks a lot for the help.

> 1) Compilation of the following code gives me errors:(as attached
> below)
> Compiling...
> lookup_test.cpp
> (23) : error C2601: 'power_to_voltage' : local function definitions
> are illegal
> (40) : fatal error C1004: unexpected end of file found
> Error executing cl.exe.

> 2) How do you construct two column table in arrray. I know one column
> table can be constructed as below

>  for example if Power = 1; voltage = 200

> then a table of one column is created as

>  voltage[0] = 3000;
>  volatge[1] = 200; and etc...for voltage being a 257 data array

> and to get the voltage when power = 1 is

> voltage[power] = 200 as voltage[1] = 200;

> 3) when you initialise the structure as in your code like below, the
> (2000, 300) is storedd in look_up[0] isntead of look_up[1] right?

> Thanks...sorry for the trouble...

No trouble.

Quote:
> -----------------------------------------
> #include<stdio.h>

   #define VOLTAGE_ERROR (-1.0)

- Show quoted text -

Quote:

> double power_to_voltage(double);

> struct
> {  double power;
>    double voltage;
> }  look_up[256] = /* Note that this table needs */
> {  { 2000, 300},  /* 255 more value pairs       */
> };

> double power_to_voltage(double power)
> {  int i;
>    for (i=255; i >= 0; i--)
>    {  if (power >= look_up[i].power)
>       {  return look_up[i].voltage;
>       }
>    }
>    return VOLTAGE_ERROR;
> }

> int main(void)
> {  double power = 2000.0;

     printf("For power = %G, power_to_voltage returns %G\n",

             power,power_to_voltage(power));

     return 0;

Quote:
> }

We can't nest function definitions (yet) in standard C. I
re-arranged your code somewhat, defined VOLTAGE_ERROR[!], and
gave main() something to do.

Elements of look_up[] that you don't specify will be initialized
to zeros. You'll either need to fill the table, shrink the table
or restrict the search to avoid returning zero from
power_to_voltage().

Please note that main() should be implicitly typed (as 'int') and
that you'll be more highly regarded in comp.lang.c if you
actually return a legitimate value (0, EXIT_SUCCESS, or
EXIT_FAILURE  8^)

The look-up can, of course, be done in many different ways; and
I'm only going to do one of them - but I'll be glad to help you
debug one of yours for which /you/ post the code.  8^>
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c



Wed, 27 Jul 2005 00:29:59 GMT  
 Lookup Table or Hash Table

Quote:
> Hello Colin,

> If your table only contains 256 entries consisting of pairs of numbers, you
> don't need to worry about speed of execution unless there's some extremely
> stringent requirement on the response time.

> I guess one could imagine cases where lookups would occur extremely frequently
> (say, millions of lookups per second); if that's what you're facing then of
> course your concern is justified.

> But unless you have those tough requirements, it's better to use a simple
> brute-force algorithm. Easier to code without making mistakes, and easier to
> understand if you need to revisit it at some later date.

> Good luck,
> PP

At the moment it runs of about 8kH interrupt, and only about another
50us left for it to do the lookup besides all other main
functionalities...

If there is 256 entried, each of the entry needs to be searched
through before it finds the real one...

Yes, I need the luck...:)



Fri, 29 Jul 2005 18:13:08 GMT  
 Lookup Table or Hash Table


Quote:

>> Hello Colin,

>> If your table only contains 256 entries consisting of pairs of numbers, you
>> don't need to worry about speed of execution unless there's some extremely
>> stringent requirement on the response time.

>> I guess one could imagine cases where lookups would occur extremely
frequently
>> (say, millions of lookups per second); if that's what you're facing then of
>> course your concern is justified.

>> But unless you have those tough requirements, it's better to use a simple
>> brute-force algorithm. Easier to code without making mistakes, and easier to
>> understand if you need to revisit it at some later date.

>> Good luck,
>> PP

>At the moment it runs of about 8kH interrupt, and only about another
>50us left for it to do the lookup besides all other main
>functionalities...

>If there is 256 entried, each of the entry needs to be searched
>through before it finds the real one...

>Yes, I need the luck...:)

So what's it running on then? The optimization strategies will be a bit
different between, say, an 8 MHz 8051 and a 2.66 GHz Pentium IV...

PP



Sat, 30 Jul 2005 07:16:35 GMT  
 Lookup Table or Hash Table
Hi for the lookup table method, what happen if we need something
between the two points? Do we assume that is linear and use an
equation, like y = mx to get the results in between the points?

Thanks

C. Green



Mon, 22 Aug 2005 00:50:29 GMT  
 Lookup Table or Hash Table
Hi guys,

If I want a 2 D lookup table, which the power and the current are the
input and the voltage is the output, I modified the original code.
However, it does not work. Any advice?

C. Green

---------------------------

 #include<stdio.h>

   #define VOLTAGE_ERROR (0)

 int power_to_voltage(int);

 struct
 {  int power;
    int current;
    int voltage;
 }  look_up[3][3] = /* Note that this table needs */
 {  { {20,10}, 3},  {{30,10}, 2}, {{40,20}, 100}/* 255 more value
pairs       */
 };

 int power_to_voltage(int power)
 {  int i,j;
    for (i=2; i >= 0; i--)
                for (j=2; j >= 0; j--)
                        {  if (power == look_up[i][j].power)
                                {  return look_up[i][j].voltage;
                                }
                        }  return VOLTAGE_ERROR;
 }

 int main(void)
 {  int power = 30;
  int current = 10;

     printf("For power = %d, power_to_voltage returns %d\n",

             power,power_to_voltage(power));

     return 0;
 }



Fri, 26 Aug 2005 19:42:01 GMT  
 Lookup Table or Hash Table
Yes Pika, I have moved the lookup to a slower loop, as it does take up
lots of CPU time.


Fri, 26 Aug 2005 19:44:20 GMT  
 Lookup Table or Hash Table
The compiler initializes the array elements in order with braces,
so in this case the first element will be initialized like
power=20, current=10, voltage=0
while the next element will be initialized like ..
power=3, current=0, voltage=0

You should give the values of an array element in a wrapped with single
brace
rather a hierarchical.
unless you have to do it for making it more legible ! while you have
struct members.
-- { {20,10, 3},  {30,10, 2}, {40,20, 100} }



Fri, 26 Aug 2005 20:49:56 GMT  
 
 [ 14 post ] 

 Relevant Pages 

1. template and CMap Trying to make a Hash table for Hashing a String to an Int

2. Enter lookup table with char...

3. ==>>Mapping and lookup table

4. mapping a lookup table to s structure

5. lookup table

6. Need a large arrays shuffling algo (no lookup table)

7. Lookup tables

8. Structures as lookup tables?

9. Character signedness, character classification and table lookups

10. Function Lookup Table?

11. Fast table lookup in C ?

12. Lookup tables?

 

 
Powered by phpBB® Forum Software