|
The initial post mentioned that the search would be for record names that were stored in a filter. If only a field of the record (the name) needed to be checked, wouldn't that reduce the effort to create a hash - in fact wouldn't a Radix search be faster? That is why I asked for more information about the input and filter format.
Dave.
|
|
|
|
|
Member 4194593 wrote: If only a field of the record (the name) needed to be checked,
I understood that each record would contain a (single) filter field, that's why i suggested as radix tree. A hash would likely be more approriate if you wanted to match several fields.
Member 4194593 wrote: wouldn't that reduce the effort to create a hash
Yes. Sounds like you're in favour of using a hash table. 
Member 4194593 wrote: in fact wouldn't a Radix search be faster?
Yes, based on my op. Sounds like you're in favour of using a radix tree.
Original post: 'based on record names'
I assume this to mean strings, in which case my op stands.
...cmk
The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.
- John Carmack
|
|
|
|
|
Good point. Some other pros and cons: A radix tree would require more memory accesses. But on the other hand, a radix tree would take less memory than a hash table, so would be more likely to fit entirely in a cache.
The hash-value calculation wouldn't necessarily be slow; it would be all integer operations on a key that could be in a single cache line. Also the number of collisions can be reduced in two ways:
1. Randomly-hashed values follow a Poisson distribution, so the expected number of collisions can be calculated for a given hash-table size. The table size can be increased to achieve an acceptable collision rate.
2. Assuming the list of names is fixed, a perfect hash function http://en.wikipedia.org/wiki/Perfect_hash_function[^] can be constructed, which will have no collisions.
|
|
|
|
|
If it's necessary to check billions of records per day, that sounds like enough computer work--regardless of algorithm--that profiling will be necessary to achieve optimal performance. Radix trees can be good if the records to be searched for differ from other records in the characters that are examined first. They can be bad if records often differ only in the characters that are examined much later.
With hash functions, there is often going to be some trade-offs involving the time required to perform a hash, the hash table size, and the frequency of hash collisions and false matches. Increasing the complexity of a hash function such that the time required increases by more than half the cost of a direct record comparison won't make much sense if doing so unless it saves an average of one direct record comparison for every two records. Having a hash table so large that every access entails a cache miss may slow things down more than would the occasional hash collision or false match.
One approach that may be helpful would be to compute a somewhat long hash of a record, hash that to produce an index into a hash table, and have the table itself store the 'long' hash in addition to the actual record. One could thus at very little expense test the long hash of the record to be checked against the long hash in the table. This would eliminate a large fraction of the direct record comparisons that would otherwise be needed.
BTW, how fast are modern machines at 32x32 integer multiplication? If the strings are zero-padded as well as zero-terminated and multiplies are cheap, it might be good to do something like:
unsigned long *ptr;
unsigned long hash,temp;
do
{
temp = *ptr++;
hash += hash >> 23;
hash ^= temp;
hash *= some_big_prime_number;
} while(temp);
That would gobble up 32 bits of string data per loop iteration; I would expect the multiply, even if it takes multiple cycles, could be done concurrently with the next word fetch. Not the world's most sophisticated hash function by any stretch, but the execution time should be pretty minimal. If you want to use the hash function to yield a table index, use the upper bits. Taking the modulus of a prime number (distinct from the one used for the multiply) may be better, but modulus operations are more expensive than shifts.
|
|
|
|
|
Interesting points. Your comment about better performance if the records differ in the characters examined first reminded me of the ID3 algorithm http://en.wikipedia.org/wiki/ID3_algorithm[^]. Basically it builds a decision tree that first examines the attributes of a record that differ the most. This avoids wasting time examining attributes that don't differ much among the records.
Your point about cache misses is good; for this volume of data the best data structure is one that fits in the cache.
|
|
|
|
|
|
Vij@y wrote: anyone can convert this code to quick sort.
So convert it, then.
If you can't convert it, which part are you having problems with?
|
|
|
|
|
I need help from you who have experience with wumpus problem.
I would like to ask that at one step, how can we choose the adjacent field to go ?
I know one method that we choose the adjacent OK field (without mummies or pits) that has fewest visited times. My teacher said that it's not the most optimal method...
Would you mind helping me. Thanks in advance.
|
|
|
|
|
|
I just think that if you can not help other people, you shouldn't consider them as a joke... 
|
|
|
|
|
I think it was a way to indicate to you that you should look to other currently available sources before you ask others to spend their time trying to help you. Did you google "Wumpus"? Many available references. If you have checked those and still do not have an answer, then ask for individual help, but maybe on a gaming forum.
|
|
|
|
|
Sir, you win at the internet. Please remember to collect your prize before you disconnect.
|
|
|
|
|
The original BASIC code has been translated into C here[^].
I am not familiar with the Wumpus problem, but perhaps you can dissect the code. Google will also give Java implementations and I'm sure you can find others. Maybe looking at the code can help.
|
|
|
|
|
especially for special word, like "tooth", "teeth".
is there any snippet exists for this?
thanks
|
|
|
|
|
Use an "if" "elseif" structure since words like "tooth" and "teeth" are exceptions in English. Basically you'll need a lookup dictionary. To handle other cases you test if the last (and second to last) letter of the word is a vowel or not.
|
|
|
|
|
John, what is your opinion of this as a resource.
http://www.sequencepublishing.com/academic.html[^] or TheSage dictionary (and other applications) from this company. I have good things to say about TheSage - excellent freeware stuff.
modified 1-Aug-19 21:02pm.
|
|
|
|
|
Looks quite useful, Richard. I know when I write papers the biggest challenge is trying not to be repetitive. Too many phrases begin: "the model suggests that...", or "so and so, in their paper find that...."
Any resource (free!) that can improve the quality of academic publications is good value in my opinion. In fact, any resource that can improve the quality of writing in university courses is well worth it - even more so if the product is good quality and freely available. Others differ, but I don't mind open source/free software for educational purposes.
|
|
|
|
|
To supplement what 73Zep said, http://aspell.net/[^] - Free and Open Source spell checker. Have a look at their Manual [^] for some info ...
modified 1-Aug-19 21:02pm.
|
|
|
|
|
Hi,
I urgently need some research info or articles about Text Tables Comparison algorithms. Something like
An O(ND) Difference Algorithm and Its Variations ∗
[^]
but for tables.
Maybe someone was working in this field and have some old links.
Thanx a lot.
|
|
|
|
|
|
Hi Dave,
Thank you very much for your reply. I have many tab delimited text documents like:
Person \t Name \t Title
1 \t NoName \t NoTitle
...
I need to find differences in this files. I used GNU diff. But if one tab will be missing it's showing full add full delete.
One document:
1 \t NoName NoTitle
Another document:
1 \t NoName \t NoTitle
So i'm trying to make my own simple algorithm for such tabular text.
|
|
|
|
|
I would guess that something, more like SED, is what you need. As I remember it from way back (many years), it would search for differences down to single characters. Its name means Stream EDitor.
I'm not too sure whether this would work or not, depending on the implementation. Usually DIFF algos are based on line differences and the whole line is marked as different. Depending on how large the files are, this could take a lot of time (order O(nm)). The method I developed talking to Skippums (in the referenced thread) speeded this up with some tricks.
Later, Skippums had another problem. He wanted an archive method for huge files (exceeding 512 MB) where the files were prior versions of documents, or programs, etc, etc - what it amounted to was he needed a small SED type of file created in order to save only the changes. Once you get into massive files, comparisons like this are extremely difficult and time consuming. I developed a method to minimize this time and was testing this. I asked for a sample file or two of this massive size (I could only come up with 9 and 11 MB libraries). I had sent him this data (the algorithm - my code was in MASM) and he finally responded to my Email about a month later explaining that he had been on vacation and would get back to me That was in July. I have checked his message log, and that is about when his last message was posted here.
I have also worked with DIFF algos.
If any of this algo info would be of use to you, I would be happy to help you.
Dave.
|
|
|
|
|
Hi,
Thank you for your reply. Was thinking how to do it correctly. Diff will not work for sure. I posted new question.
|
|
|
|
|
Hi
There is a question I have been wondering about for ages and I was hoping someone could give me an answer to rest my mind.
Lets assume I have an input stream (like a file/socket/pipe) and want to parse the incoming data. Lets assume each block of incoming data is split by a newline like most common internet protocols. This just however just as well be parsing html/xml or any other smart data structure. The point is that the data is split into logical blocks by a delimiter rather than a fixed length. How can I buffer the data to wait for the delimiter to appear?
The question seems simple enough: just have a large enough byte/char array to fit the entire thing.
But what if the delimiter come after the fixed size buffer is full? This is actually a question about how to fit a dynamic block of data in a fixed size block. I can only really think of a few alternatives:
1) increase the buffer size when needed. This may require heavy memory reallocation, and may lead to resource exhaustion from specially crafted streams (or perhaps even denial of service in the case of sockets where we want to protect ourselves against exhaustion attacks and drop connections that try to exhaust resources...and an attacker starts sending fake, oversized, packets to trigger the protection)
2) start overwriting old data by using a circular buffer. Perhaps not an ideal method since the logical block would become incomplete
3) dump new data when the buffer is full. However, this way the delimiter will never be found so this choice is obviously not a good option
4) just make the fixed size buffer damn large and assume all incoming logical data blocks is within its bounds...and if ever full just interpret the full buffer as a logical block...
In either case I feel we must just assume that the logical blocks will never exceed a certain size...
Any thoughts on this topic? Obviously it must be a way since the higher level languages offer some sort of buffering mechanisms with their readLine() stream methods.
Is there any "best way" to solve this or is there always a tradeoff? I really appreciate all thoughts and ideas on this topic since this question has been haunting me everytime I have needed to write a parser of some sort.
|
|
|
|
|
You're right reallocation can be very costly, one solution I've seen to be quiet effective is to have a memory pool (set of buffers of common length) and have your stream maintain the chaining, as more memory is required (using a linked-list like approach) chain-in more blocks of memory from the pool.
Finally (socket example) when the frame, packet or token has arrived, provide per item(char usually) iterator access to the chain of buffers so as to make the chain transparent to the end user.
This obviously has its limits as well, specifically the largest block you can read will be the size of the pool of memory, however due to the design choice, if you ever reach that limit all you need to do is create more memory blocks in the pool which is much cheaper than realloc'ing everything accumulated so far.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
