I have some very large files I need to do quick lookups on --like 60K records. The files are static -not updated. From what I've read a "perfect hash" is the fastest way to go. I'm new to the hash algorithm although I understand the basic concept but I am ignorant of the mechanics of it. Anyone know a good link to get started with writing hash algorithms? "Hashes for dummies"?
Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations Chris Miller on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Getting Started with a Perfect Hash
- Thread starter sen5241b
- Start date
DonQuichote
Programmer
- Nov 9, 2001
- 980
PHP can calculate md5 and SHA1 hashes be default. Even for files (md5_file and sha1_file functions). I suggest you just use one of those.
But I fail to see what hashes have to do with lookups or what the structure of those "records" in the file is. If these files are actually tables, a database might be a better option.
+++ Despite being wrong in every important aspect, that is a very good analogy +++
Hex (in Darwin's Watch)
But I fail to see what hashes have to do with lookups or what the structure of those "records" in the file is. If these files are actually tables, a database might be a better option.
+++ Despite being wrong in every important aspect, that is a very good analogy +++
Hex (in Darwin's Watch)
- Thread starter
- #3
I have just a few lists of first and last names for lookups. The lists have a single field, the name itself, and are not related to each other. SQLlite is a a little too much trouble for this simpler application.
From Wikipedia "Perfect Hash":
Using a perfect hash function is best in situations where there is a large set, S, which is not updated frequently, and many lookups into it.
From Wikipedia "Perfect Hash":
Using a perfect hash function is best in situations where there is a large set, S, which is not updated frequently, and many lookups into it.
60000 records is no sweat for a database. and sqlite would be a perfect solution for this kind of application.
but if you must use a flat file then i would say a hash is only going to be a valid timesaver if each line is quite long (more than 16 characters on average, 24 if you use sha1).
if each line is unique, then a strpos or similar might be much more efficient.
remember with modern computing, disk drives and memory mapping techniques, file i/o operations are stormingly fast. i would not be remotely surprised if you got great results using file() and in_array().
but if you must use a flat file then i would say a hash is only going to be a valid timesaver if each line is quite long (more than 16 characters on average, 24 if you use sha1).
if each line is unique, then a strpos or similar might be much more efficient.
remember with modern computing, disk drives and memory mapping techniques, file i/o operations are stormingly fast. i would not be remotely surprised if you got great results using file() and in_array().
DonQuichote
Programmer
- Nov 9, 2001
- 980
Indeed. And when reading SQLite's web site it says this is exactly what it is made for. I do not think this is overly complex.
+++ Despite being wrong in every important aspect, that is a very good analogy +++
Hex (in Darwin's Watch)
+++ Despite being wrong in every important aspect, that is a very good analogy +++
Hex (in Darwin's Watch)
- Status
Similar threads
