-
October 6th, 2010, 10:55 AM
#1
Best data structure/algorithm for word search?
Given a list of words, I need to determine whether a string perfectly matches a word in the list.
Which of the data structures below supports the fastest search/match algorithm?
1. a single-column (VARCHAR(), PRIMARY KEY) SQLite database table
2. a HashTable()
3. a Dictionary<string, int>
Your help is greatly appreciated.
Last edited by tr00don; October 6th, 2010 at 02:26 PM.
Reason: edited title is more informative
-
October 6th, 2010, 06:08 PM
#2
Re: Best data structure/algorithm for word search?
Maybe you should ask your teacher.
-
October 6th, 2010, 07:26 PM
#3
Re: Best data structure/algorithm for word search?
Hm... you either try to imply that it's obvious (which to me it won't be until I run tests with each of the three options) or you just don't know. Either way your answer is not helping.
-
October 7th, 2010, 04:05 AM
#4
Re: Best data structure/algorithm for word search?
I can give you a 100% correct and accurate answer - it depends. Any of those can potentially be the fastest depending on your dataset. The real answer is - who cares which is fastest unless it turns out to be a bottle neck. There are dozens of algorithms out there for string matching so if the simplest solution is a performance problem, then try another
www.monotorrent.com For all your .NET bittorrent needs
NOTE: My code snippets are just snippets. They demonstrate an idea which can be adapted by you to solve your problem. They are not 100% complete and fully functional solutions equipped with error handling.
-
October 13th, 2010, 07:21 PM
#5
Re: Best data structure/algorithm for word search?
All right, I chose Dictionary<string, int>. I need to store a lot of data but it's really fast, so performance is not an issue. The problem is, the application crashes with an OutOfMemory exception when working memory reaches 1 GB.
I know that objects in C# cannot be larger than 2 GB, but a 1 GB limit for the whole program? This is a 32-bit application. Any ideas?
Thanks.
-
October 14th, 2010, 02:34 AM
#6
Re: Best data structure/algorithm for word search?
Are you storing all that massive amount of info in one single dictionary? It's possible that the dictionary itself is resizing large enough that it alone is trying to allocate a massive amount of contiguous memory and that can't be satisfied by the operating system so the app is shut down.
If so you could just split your single massive dictonary of 1 billion items into several smaller dictionaries. Maybe based on the first char in the string like: a-e, f-j, k-p, etc. (assuming the first char is semi-random)
www.monotorrent.com For all your .NET bittorrent needs
NOTE: My code snippets are just snippets. They demonstrate an idea which can be adapted by you to solve your problem. They are not 100% complete and fully functional solutions equipped with error handling.
-
October 14th, 2010, 11:58 AM
#7
Re: Best data structure/algorithm for word search?
Thank you for your suggestion, it works. I created an array of 16 dictionaries (~ 2 letters each) and now the application work memory can go above 1 GB.
Last edited by tr00don; October 14th, 2010 at 12:01 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|