|
I'm working on my first iPhone game and have come up against a bit of a showstopper. I need a scrabble dictionary in memory to do some very fast spellchecking, hopefully checking about 100 words vs 250,000+ words in a single frame. If I hardcode the whole thing in XCode 4 as a single massive line of code like this: wordList = [NSArray arrayWithObjects:@"aa", @"aah", @"aahed", ... @"zyzzyvas",nil]; The compiler just hangs. It doesn't crash, but it will sit there and chew on it for 30 minutes until I cancel it. In the past, I've written the same thing, both in C and in flash's actionscript without this sort of problem, so I'm just wondering if anyone can shed some light on any practical limits of XCode, the iOS GCC compiler and iOS itself, or maybe suggest a workaround to my crappy method. Also any suggestions on the best way to hold and process that amount of data in Objective C (and on an iPhone) would be good. I plan to just do a binary search on it for speed. But I have no idea how an NSString 'compare' will rate for speed and overhead against a simple C style string comparison like this: if( (char*)myWord < (char*)WordList[index] )
|
#
¿
Apr 17, 2011 11:04
|
|
|
|
| # ¿ May 2, 2024 14:22 |
|
|
pokeyman posted:First step is to use an NSSet, not an NSArray, because you don't care about order. But when you run into the same problem, check out tries, their memory-saving counterpart radix trees, and their goofy cousin dawgs. There's also plenty more where those come from, so poke around. Thanks! Not the answer I was looking for, but very interesting. I found that a plain binary search was fast enough, it's more the reason I need the whole thing in RAM all the time. When I say "fast enough"... a prototype version written in flash and running on an android phone is able to parse 200+ words without a hitch at 30FPS. I'll implement it as a binary search first (already wrote that code years ago) and if it's not quick enough, I'll definitely look into setting up a DAWG. On the surface, my guesstimation is that DAWG may shave off about 30% of the operations, but take about 3 times the RAM. This is only because a lot of the strings I have to check will be 9 letters long. Are you saying NSSet containsObject is faster than a binary search in an ordered array? I'm not familiar with NSSet, but that seems pretty amazing. Anyway the answer I really needed was "Load it from an external file, you dolt" Now I'm looking into how I'm supposed to do that. Wondering whether the convenience of arrayWithContentsOfFile is worth the XML bloat, and whether I can even use fopen and fgets on iOS.
|
|
#
¿
Apr 17, 2011 15:28
|
|
|
^^ oh, that 5 bit compression is nice, I'll use that. I got it working... The wordlist now loads as a NSString from a CSV file, the string is split into an NSArray, the NSArray converted to a NSSet. There's a hasWord method, [dict hasWord:@"TESTING"] returns true, [dict hasWord:"FKJHDSA"] returns false Everything is good. edit: and it's fixed. monkey fucked around with this message at 20:01 on Apr 17, 2011 |
|
#
¿
Apr 17, 2011 18:44
|
|
|
pokeyman posted:I don't know if you're familiar with big-O notation... Familiar enough to realise it's not O(exp n) so there's not much speed difference between 2,000 and 200,000 words. Would NSSet be practical to store nothing but long ints like in the stackoverflow link Bob Morales posted? I mean practical in terms of the memory footprint and any memory thrashing it may have, compared to just 1 static long int per word? I'm working on the other end of the search at the moment, and NSStrings are giving me a bit of grief with their handling of individual characters. I'm coming from Actionscript where "searchString+=charArray[x][y];" is valid syntax. It may turn out that converting to long ints will be a lot faster to stitch the searched words together out of a 2D array. I'll benchmark the two search methods anyway, since they're both written now.
|
|
#
¿
Apr 17, 2011 23:51
|
|