11

After not programming for a long, long time (20+ years) I'm trying to get back into it. My first real attempt is a Scrabble/Words With Friends solver/cheater (pick your definition). I've built a pretty good engine, but it's solves the problems through brute force instead of efficiency or elegance. After much research, it's pretty clear that the best answer to this problem is a DAWG or CDWAG. I've found a few C implementations our there and have been able to leverage them (search times have gone from 1.5s to .005s for the same data sets).

However, I'm trying to figure out how to do this in pure Objective-C. At that, I'm also trying to make it ARC compliant. And efficient enough for an iPhone. I've looked quite a bit and found several data structure libraries (i.e. CHDataStructures ) out there, but they are mostly C/Objective-C hybrids or they are not ARC compliant. They rely very heavily on structs and embed objects inside of the structs. ARC doesn't really care for that.

So - my question is (sorry and I understand if this was tl;dr and if it seems totally a newb question - just can't get my head around this object stuff yet) how do you program classical data structures (trees, etc) from scratch in Objective-C? I don't want to rely on a NS[Mutable]{Array,Set,etc}. Does anyone have a simple/basic implementation of a tree or anything like that that I can crib from while I go create my DAWG?

Volo
  • 28,673
  • 12
  • 97
  • 125
tachijuan
  • 191
  • 1
  • 6
  • 5
    Anything you can write in C is Objective-C, as Objective-C is entirely a superset of C. It mainly bolts on a Smalltalk-like OOP paradigm which does not seem applicable to this problem. – alexantd Oct 24 '11 at 19:18
  • Clearly understood and sorry if I didn't make it apparent in my original question. I get that I could implement the DAWG as a C "thing" and then wrap Objective-C stuff around that to insert/enumerate/serialize/etc. However, as an exercise, I want to create a pure object driven implementation. Believe me, I get that this is not optimal, will likely not provide the fastest implementation, or even the most space efficient one. However, it will teach me and others how to make an object data structure thing work. Purely didactical. – tachijuan Oct 24 '11 at 20:07
  • @outis: ARC = Automatic Reference Counting. – Can Berk Güder Oct 24 '11 at 21:34
  • Have you considered using a [GADDAG](http://en.wikipedia.org/wiki/GADDAG) rather than a DAWG? _It is generally twice as fast as the traditional DAWG algorithms, but take about 5 times as much space for regulation Scrabble dictionaries._ – Aidan Steele Oct 24 '11 at 21:59
  • I did, but from what I have seen of the algorithm - it's twice as hard to implement and I'm not so sure that 5x the memory for an iphone app is appropriate. Specially since 2x the speed is relative and I'm not doing that many lookups. – tachijuan Oct 25 '11 at 00:18

1 Answers1

3

Why shoot yourself in the foot before you even started walking?

You say you're

trying to figure out how do this in pure Objective-C

yet you

don't want to rely on a NS[Mutable]{Array,Set,etc}

Also, do you want to use ARC, or do you not want to use ARC? If you stick with Objective-C then go with ARC, if you don't want to use the Foundation collections, then you're probably better off without ARC.

My suggestion: do use NS[Mutable]{Array,Set,etc} and get your basic algorithm working with ARC. That should be your first and only goal, everything else is premature optimization. Especially if your goal is to "get back into programming" rather than writing the fastest possible Scrabble analyzer & solver. If you later find out you need to optimize, you have some working code that you can analyze for bottlenecks, and if need be, you can then still replace the Foundation collections.

As for the other libraries not being ARC compatible: you can pretty easily make them compatible if you follow some rules set by ARC. Whether that's worthwhile depends a lot on the size of the 3rd party codebase.

In particular, casting from void* to id and vice versa requires a bridged cast, so you would write:

void* pointer = (__bridge void*)myObjCObject;

Similarly, if you flag all pointers in C structs as __unsafe_unretained you should be able to use the C code as is. Even better yet: if the C code can be built as a static library, you can build it with ARC turned off and only need to fix some header files.

CodeSmile
  • 64,284
  • 20
  • 132
  • 217
  • Really appreciate the answer. The thing is that I have made it work with the built in native NS[DataType] stuff - two different ways. One was with brute enumeration so I could use "." as a wildcard. Another was with a hash on an NSDictionary with NSMutableArray elements. The first is slow, the second is super fast, but doesn't give me a simple wild card implementation. Hence trying to build a DAWG. So I'm trying to build a tree with just Objective-C objects (i.e. create a class "letter" and then build a DAWG of linked "letter" objects). Am I barking up the wrong tree? – tachijuan Oct 24 '11 at 22:05
  • Have you had a look at OFC? They have 3 different versions of a tree collection. http://code.google.com/p/ofc/ – CodeSmile Oct 24 '11 at 22:11
  • That's not one that popped up before. Thank for the pointer. I'll report back on the results. It looks like a rather large code base to sift through. – tachijuan Oct 25 '11 at 00:26
  • I looked through the OFC code. It's a really cool library of stuff, but at it's code it does use structs with objects inside. ARC doesn't like that. So that really begs the question - is this because of performance or because creating a linked list of pure objects just doesn't work? – tachijuan Oct 25 '11 at 12:04
  • Any struct can be represented as an Objective-C class. Some may use structs out of habit, some for performance reasons, hard to tell. Until recently no one really knew what bugs ARC and what doesn't. I expect more and more libraries be made ARC compatible in the future, if only by adding the correct compiler keywords (__unsafe_unretained id object;). – CodeSmile Oct 25 '11 at 18:57