Digest for comp.lang.c++@googlegroups.com - 4 updates in 1 topic

comp.lang.c++@googlegroups.com

Google Groups

Topic digest
View all topics

• Alf's Boggle solution - 4 Updates

Alf's Boggle solution

Paavo Helde <myfirstname@osa.pri.ee>: Feb 11 11:46PM +0200 On 11.02.2017 23:29, Öö Tiib wrote:   > Trie is doomed to win any lower_bound in anything because finding > all words that start with F from trie is O(1) and after that > finding all the words that start with FR is again O(1).   Yes, but this O(1) may involve a large jump in memory whereas in a sorted vector FR is guaranteed to be near F. The big-O notation holds better in case of large N, which incidentally means those jumps in memory go larger.

"Christopher J. Pisz" <cpisz@austin.rr.com>: Feb 11 03:53PM -0600 On 2/11/2017 2:25 PM, Chris Vine wrote: > but haven't dealt with it.)   > You have dealt with the clog point.   > Chris   I did both of those things in my code like 15 posts ago :)

Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Feb 11 10:10PM On Sat, 11 Feb 2017 15:53:37 -0600   > > You have dealt with the clog point.   > > Chris   > I did both of those things in my code like 15 posts ago :)   Are we at cross purposes? It wasn't in the code you posted in your posting beginning "I got Alf's solution to run on the test site" when you gave your timings.   Did these changes affect the results?   Take this off line and email me (without the "--nospam--") if it isn't clear what I was talking about.

"Öö Tiib" <ootiib@hot.ee>: Feb 11 02:21PM -0800 On Saturday, 11 February 2017 23:46:18 UTC+2, Paavo Helde wrote: > sorted vector FR is guaranteed to be near F. The big-O notation holds > better in case of large N, which incidentally means those jumps in > memory go larger.   Not sure what you mean. You mean that the "FR" of "FRACTAL" and "FR" of "FROG" are not far from each other in a memory in sorted vector of strings because of small string optimization? If so then Ok.   However in trie the "FRACTAL" and "FROG" share the starting "FR" with each other. So if we have discovered "FR" on boggle board then that means potential for both "FRACTAL" and "FROG" immediately. No searches needed. Trie just rules in that task. ;)

Back to top

You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.