We are running a survey to help us improve the experience for all of our members. If you see the survey appear, please take the time to tell us about your experience if you can.
I have large numbers of records store in 24C256,4 bytes for 1 record. The record store in EEPRom is in sequence,and I want to find a record matched data from them. I now write a subfunction like following: First,I read record 1 form EEPRom,verify it and find if it is match my data. If match, return "1"(the record NO.);If no,I read record 2 ... and so on. If the last record is reached and it is still not the record I wanted,The function will return "0". Is this called Compare In Sequence Arithmetic? Routine will be very slowly when the matched record is in the back of EEPRom. The Dichotomy Arithmetic and Cut In Block Arithmetic cann't be use because of the record stored in EEPRom is random. Can you tell me a good arithmetic? Thank you.
I would call that algorithm a "linear search". Interesting terminology. I'd guess that "Dichotomy Arithmetic" is what I'd call a "binary search algorithm". I'm not entirely sure what the "Cut In Block" would be. Unfortunately, if you store the data in a random fashion, you're not going to be able to do better than the linear search when you do the lookup. Faster search algorithms depend on having some structure to the data that you can take advantage of when doing the search. (Your first sentence says the records are "in sequence", but later on you say that they are random.) How about a "hash table"? That is, you use a function that calculates an index (record number) into the EEPROM, given the record key (perhaps the whole record, if its only 4 bytes). When you store a record, you calculate the hash value, and put the record at that location. When you want to match, you calculate the hash of your record to match, and then you look at that location to see if the record is actually present. (Note that this implies that you can tell the difference between an "empty" record in the EEPROM and all other values. You'll need at least a sentinel value for that purpose.) Sometimes, your hash function will give you the same index for two different records. This is usually called a "collision", and your hasing code needs to have a rule for how you resolve collisions. One simple way is to use the hashed index as a starting point for a linear search. There are more complicated methods with better performance. Any algorithms book should have a discussion of hashing. Some information on hash functions: http://www.wikipedia.org/wiki/Hash_function http://burtleburtle.net/bob/hash/
Thank you very much,Drew Davis. I know Hash Table,It need more room to store data,I will try to find a good Hash Function. Thank you.
David, If the data is placed in memory in an ascending or descending structure then you could use a bisection algorithm. This algorithm will find your result in log2n tests. However, if the data is not in any order then you will probably have to use a linear or hash based algorithm.