Printable View
So I am asked to speed up some code, I am storing a file which I am going to compile into a big dictionary. Right now I am using a linked list to store the words in order.. but what data structures should I use to make it faster? A binary tree or a hash table? opinions?
Depends on access patterns.
If no one ever accesses the data, it doesn't matter how you store it.
If it is accessed in the order you are storing it, changing that order will only hurt you.
If it is accessed in a random order, and you have to search through it to find anything, then you need a better indexing, storage or access mechanism.
it is accessed after all is stored
And the sky is blue!
Most data won't be accessed until it is "stored" into its structures.
well here's how it goes.. I have a file of words the file has words in it and there are two types of it.. one is sorted in alphabetical and the other one is not.. our job is to construct a dictionary of words and when we create it we can request the dictionary to keep the dictionary in sorted order or not
What's the point of having an unsorted dictionary?Quote:
Originally Posted by -EquinoX-
The point here is, what do you want to do with the dictionary once it's created? A binary tree is probably your best bet here, but it does very much depend on what you want to do.
QuantumPete
> What's the point of having an unsorted dictionary?
If you're just looking for a simple yes/no "is this word in the dictionary", then perhaps a hash would work well.
But any kind of searching would be better using some kind of tree.
> A binary tree or a hash table? opinions?
Consider a tree where each node say has pointers for 'a' to 'e', 'f' to 'j', 'k' to 'o' etc.
Somewhere between a strict binary tree, and having 26 pointers for every possible next letter, where many such combinations are in fact useless.
It's not a dictionary.. so first I read a I read a list of words and put it into some data structure
secondly I read a different file, which is also a list of words and then compare that words to see if any matches the word in the first file if it does then I copy that word to a data structure.. thirdly I would iterate through previous data structure and put the list of the words in a new data structure so that the list of the words would be sorted.. that's all I need to do basically
so what is the most efficient and fast way to do this? what data structure should I use the first time, second time, and third time?
What I have in mind right now is first just to store the first file in a data structure, the second one in a binary tree, and the third one in a binary tree too.. I don't know if it's fast enough
1. What is your time limit for the execution.
2. If you don't know which method to use, make sure you isolate the storage from the code that fetches/stores data in the tree/list/etc.
3. Start with a very simple method of storing your data, such as a straight, unsorted array, or a simple linked list.
4. If the time is "too long", then adjust your storage method.
--
Mats
What about just indexing your words? Then keep them in sorted order, and use a binary search. The index would be an array of structs, something like this:
0) 0, 24
1) 25, 44
2) 45, 53
etc.
Where Index[0] = low and high index numbers for the letter 'a' words in your dictionary.
Index[1] = low and high index numbers for the letter b words in your dictionary.
etc.
Now you get a request for "beach", is it in your dictionary? Your binary search will begin with the 25th element of your dictionary array, and have an initial ceiling value of 44. That changes a binary search (already fast), to a supercharged binary search.
I still think this smells of "premature optimization". The basic principle should be: make the code work, using the simplest reasonable methods. If you need to make it run faster when you have it working, then make changes to the working code.
--
Mats
I have a code that already work and right now it's using a linked list to store the words sorted, which is bad , bad , and bad! so I am thinking using hash table for the first one and use a binary tree for the second one as the file will be smaller after we find a commonly words
It may be bad from a performance perspective, but the performance aspect is only really important if you have code that runs sufficiently slow that there's any point in making it faster.Quote:
Originally Posted by -EquinoX-
Also, linked lists are great for inserting/removing stuff from.
--
Mats
yes but it's bad and I need to improve it somehow
Define "bad"
Or, perhaps I should say
Quantify "bad"
bad here means that it's slow!
That's still vague.
You could read the two lists of words into two dynamic arrays, sort them, and then do a single pass through each of them simultaneously to find the words in the second list that appear in the first list. Since the resulting list is sorted, another dynamic array will do, assuming you do not intend to frequently insert elements to the middle of it.Quote:
It's not a dictionary.. so first I read a I read a list of words and put it into some data structure
secondly I read a different file, which is also a list of words and then compare that words to see if any matches the word in the first file if it does then I copy that word to a data structure.. thirdly I would iterate through previous data structure and put the list of the words in a new data structure so that the list of the words would be sorted.. that's all I need to do basically
so what is the most efficient and fast way to do this? what data structure should I use the first time, second time, and third time?
Alternatively, just sort the first list, and then use binary search on it. However, the resulting list would then not be sorted, so you would have to sort it.
Of course, the point that people are making is that if your lists of words are sufficiently small, doing all this sorting would not help, and would merely be wasted effort.
I am thinking of storing the first file in a hash table first...