2
\$\begingroup\$

In my game project I have a lot of word existance checks based on some word bank. As usual arrays or map/set are not realy appropriate for this due to their speed/memory usage, I want to use Ternary Search Tree. After some googling I've realised that there's not so much info or code ready to use there. So I want to implement it myself.

Question is - can I write it in C++ and then export to Unity with cross-platform support? To be more precise: will I be able to use this cpp library on Android and iOS? Or maybe I should just write it in C# which, I believe, will be slightly less efficient?

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Are you sure a hash map is not good enough for your purpose? How many millions of words do you have? How many thousands of searches do you do in it per second? This really seems like premature optimization to me. \$\endgroup\$
    – Philipp
    Commented Nov 29, 2017 at 18:18
  • \$\begingroup\$ For PC - yes, as developing for smartphones I want to optimize as much as I can to save battery. If hashmap is good though - I can definately use it at least for prototyping and maybe even for a full game. Thank you for your response. \$\endgroup\$
    – user109982
    Commented Nov 29, 2017 at 18:37
  • 3
    \$\begingroup\$ Beware of making performance judgements before you've actually implemented and tested at least a prototype version of the feature. For a basic data structure like a search tree or finite state acceptor, storing static data that's not being re-allocated during queries, there's no particular reason to expect significantly worse performance from C# - especially if you stick to simple arrays under the hood in your implementation. It might be better to try it that way first and measure performance before complicating your project. \$\endgroup\$
    – DMGregory ♦
    Commented Nov 29, 2017 at 18:50

2 Answers 2

Reset to default
1
\$\begingroup\$

As the comments point out, don't prematurely optimize. What this means is either "test it with a prototype" or "do a believable back-of-napkin Fermi estimate based on known implementation features"

Or maybe I should just write it in C# which, I believe, will be slightly less efficient

Why would you believe it is less efficient? What makes it less efficient? Finding out the answers to these questions should be way less effort than writing a Ternary Search Tree in C++ and then figuring out cross-platform native interop in Unity.

Do you actually need it?

I think between two sublinear algorithms, there won't be a noticesable difference. Just for fun, I took the TWL06 Scrabble dictionary as a text file (178,690 words). Linear search with grep takes like 10ms (I can't easily measure the precise time with time) , as measured on the command line and uses 1MB memory. Obviously, this is a terribly inefficient strategy to use repeatedly. But even this is "good enough".

\$\endgroup\$
1
\$\begingroup\$

If you need to search for words in a lexicon, then simply storing them pre-sorted and using a binary search algorithm can reduce the complexity to O(log2N), that's basically the best you can get.

Similar with the memory. An average english word is around 5.1 letters long, if you store 200,000 word, that takes up around 1 megabyte, which isn't much, even on cellphones.

Searching through these takes 18 checks. You can't even measure that in milliseconds.

\$\endgroup\$
3
  • \$\begingroup\$ You can technically do "better" (asymptotically) than logN with a finite state acceptor. There your upper bound is linear in the length of the word (times a constant that's at most the size of the alphabet), and common prefixes/suffixes can share storage. Significantly more work to set up than a search tree or hash table though, so unlikely to be an important distinction for most game uses. \$\endgroup\$
    – DMGregory ♦
    Commented Nov 30, 2017 at 2:36
  • \$\begingroup\$ I haven’t even thought about binary search, that’s a fantastic idea, thank you. \$\endgroup\$
    – user109982
    Commented Nov 30, 2017 at 4:50
  • \$\begingroup\$ @RiotBr3aker Note that C# already comes with a binary tree implementation supporting O(log n) search. \$\endgroup\$
    – Philipp
    Commented Nov 30, 2017 at 12:21

You must log in to answer this question.