|
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.
|
|
|
|
|
It sounds like you need to make a policy decision that's algorithm-independent: How large can a block be before you decide it's a denial-of-service attack?
This is domain-dependent. It depends on the knowledge you have of blocks' contents from your particular domain, and on the resources of your system. If you have lots of memory, you can afford to accept a big block on the chance it may be real.
The memory-reallocation approach wastes time because each reallocation requires you to recopy all the data received for that block so far. This starts to approach an O(n^2) running time for what should be a linear algorithm.
It seems like a buffer pool would use up memory waiting for big blocks that may never come. It would also limit the maximum size of a block you could accept.
The linked-list approach is the standard way of dealing with this type of situation; don't preallocate anything, and dynamically allocate blocks as you need them.
|
|
|
|
|
I know that I am opening Pandora's box, and I fully expect to be met with an angry hoard of rabid Bats, but I have an idea for constructing a convex hull from a data set. What I was looking for was a "Best" algorithm (here come the Bats) so that I might code it as a baseline to see if my algorithm is any faster. I was actually looking for triangulation, but wanted to start with the convex hull first.
I have already googled convex hull, but there is not too much info about relative performance.
The data will be just 2D (x,y) where there will be 64K-1 unsigned shorts for both x and y, no repeats (randomly select an integer from the set of (1 to (64k-1)), then remove the integer from the set, decrement the set size, and randomly select another entry from the remainder of the set). x and y will be independently randomized. The x y pair will not both be equal (swap the y value with the immediately following or previously defined pair whichever does not violate x!=y for either resultant pair). The set of points will be saved on a file as binary pairs, each algorithm will then be used to read the points and create the convex hull.
I will code my algorithm and the base algorithm in MASM, single threaded (the method should be able to be implemented as multi threaded, but for simplicity and timing, I wanted single threaded). I will use the MASM32 timing macros to set the CPU into Real Time Priority to try to get as accurate a timing as possible.
I'm not looking for code, just a detailed algorithm which would allow me to implement this sought after "Best" algorithm to use as a baseline.
Anyone have a guess how long this 64K-1 set might take to encircle? Should I reduce the size of the set?
Bring on the Bats!
Dave.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
