Improving lookup performance for Hashtables

  • 4 Replies
  • 1338 Views
*

frankinstien

  • Replicant
  • ********
  • 502
    • Knowledgeable Machines
Improving lookup performance for Hashtables
« on: July 25, 2021, 03:03:37 am »
I read a few articles about hashtables and the problem with collisions. So I came up with a key algorithm using power functions to create unique keys from strings using only alphanumeric characters. So by precomputing the keys as doubles I get a lookup improvement of anywhere from 43% to 90%!

Below are some tests where the dictionary has 370,102 unique words and 100,000 lookups were performed for each test:

Code
Performce Test with NET string key dictionary

Total Time for all look ups: 0.04 seconds!

__________________________________
Performce Test with NET double key dictionary

Total Time for all look ups: 0.029 seconds!

__________________________________
Performce Test with NET string key dictionary

Total Time for all look ups: 0.053 seconds!

__________________________________
Performce Test with NET double key dictionary

Total Time for all look ups: 0.028 seconds!

__________________________________
Performce Test with NET string key dictionary

Total Time for all look ups: 0.041 seconds!

__________________________________
Performce Test with NET double key dictionary

Total Time for all look ups: 0.028 seconds!

Ultimately the key generator will be modified to work with numerical ranges so fuzzy states can be looked up using a hashtable.

*

MagnusWootton

  • Starship Trooper
  • *******
  • 306
Re: Improving lookup performance for Hashtables
« Reply #1 on: July 25, 2021, 03:15:16 am »
Dont understand,  are u getting a lookup speed increase?    and its just looking for an exact match or is it looking for a similarity match?

Ive got an optimization for nearest neighbour matching myself,   but I dont understand what  "precomputing the keys as doubles"  means!   why wouldnt an integer suffice - why need floating point unit?

*

frankinstien

  • Replicant
  • ********
  • 502
    • Knowledgeable Machines
Re: Improving lookup performance for Hashtables
« Reply #2 on: July 25, 2021, 03:25:45 am »
Right now it's an exact match but I just tried using byte arrays and I'm getting a 408% improvement over just using string keys! :D

Of course, there are data sources for partial matches or usual entry mistakes and this approach will shine with those kinds of resources.

*

frankinstien

  • Replicant
  • ********
  • 502
    • Knowledgeable Machines
Re: Improving lookup performance for Hashtables
« Reply #3 on: July 25, 2021, 11:02:21 pm »
Oops, that claim about byte arrays was due to an error in the code! But the use of the power function key(double) performance boost is consistent. O0

*

MagnusWootton

  • Starship Trooper
  • *******
  • 306
Re: Improving lookup performance for Hashtables
« Reply #4 on: July 26, 2021, 04:25:39 am »
Ai requires a really excellent optimization,  if it turns out your unlucky this time,   you've only failed once you've given up completely.

If you want to know about my KNN op,  just ask,   unless u want your own original invention, which I highly recommend over copying others!  :)
« Last Edit: July 26, 2021, 05:30:37 am by MagnusWootton »

 


What's everyone up to ?
by ivan.moony (General Chat)
Today at 04:15:34 am
So what if...
by MagnusWootton (General AI Discussion)
December 06, 2021, 10:07:46 pm
I want one!
by frankinstien (General Chat)
December 03, 2021, 06:57:48 pm
Pattern based NLP
by MikeB (General Project Discussion)
December 03, 2021, 11:19:32 am
New cryopreservation method is much better
by LOCKSUIT (General Chat)
December 02, 2021, 11:42:58 am
Artificial God?
by MagnusWootton (General AI Discussion)
December 01, 2021, 07:02:41 pm
Project Acuitas
by WriterOfMinds (General Project Discussion)
November 29, 2021, 05:31:57 am
java/kotlin to python
by yotamarker (AI Programming)
November 28, 2021, 07:23:54 pm

Users Online

43 Guests, 0 Users

Most Online Today: 59. Most Online Ever: 2369 (November 21, 2020, 04:08:13 pm)

Articles