0

I use a static list of unique strings T (french dictionary), with 402 325 entries. My code is playing Scrabble and uses a specialized construction called a DAGGAD to construct playable words and verifies that the words are actually in the list. Is there a way faster than list.indexof(T) to find if a word exists ? I looked at HashSet.Contains(T) but it does not use an index that I can use to retrieve a word. For example, for a given turn of play there could be thousands of valid solutions: I actually store only the index of the list, but with a HashSet I would not be able to do that and will have to store all words, which increases memory usage. In most cases solutions are found in one or two seconds, but in some cases (i.e. with blanks) it takes up to 15 seconds, and I need to reduce that if at all possible with VB !

Pierre Labrie
  • 11
  • 1
  • I could only find a reference to GADDAG (in [A Faster Scrabble Move Generation Algorithm](https://ericsink.com/downloads/faster-scrabble-gordon.pdf)), do you have a link to DAGGAD? – Andrew Morton Apr 02 '21 at 08:18
  • A HashSet would probably be the fastest but brings a storage overhead: There is some good information in this other similar SO post https://stackoverflow.com/questions/1009107/what-net-collection-provides-the-fastest-search – GoodJuJu Apr 02 '21 at 09:18
  • If your list is sorted, you can probably implement your own binary search on it. That would likely be faster than `IndexOf` which I expect would have to assume that the list is not sorted and do a linear search. You could also look into other containers, e.g. I think a trie is designed for the kind of usage you would have, but you'd have to write the entire container (or find an existing implementation). – Craig Apr 02 '21 at 13:07
  • Thanks Andrew. The article you refer to was my starting point. Using a GADDAG improves performance drastically compared to SQL. Once my code finds a playable word it stores only the index from the list which uses less memory than storing the word, but requires an additional step to find the index in the list. This is what I want to speed up. – Pierre Labrie Apr 02 '21 at 13:15
  • Thanks Craig. I changed from IndexOf to BinarySearch on my sorted list and this is a great improvement, around 10 times faster. – Pierre Labrie Apr 02 '21 at 15:05

1 Answers1

1

As Craig suggested, using List.BinarySearch(T) on a sorted list of T improves the speed by around 10 fold. A Scrabble play with a blank letter is now taking no more than 1 or 2 seconds compared to 15 to 20 seconds when I was using IndexOf.

Pierre Labrie
  • 11
  • 1