macOS Advice on an approach to a problem please

[mdeh]

Hi all,
I wonder how the "aces" would approach this issue.

I have a class which has 3 ivars. I want to store each object with it's three values in a dictionary, but most importantly, I want to be able to search the dictionary for a specific element of the object in an efficient way.

So, I have tried the method "allKeys", then iterate through each "key" of the returned array, to examine each object for the specific element (using the keys to query the dictionary)....but this seems really inefficient.

Wonder how you would approach this?

Thanks

 

[GorillaPaws]

If speed is critical, I suspect you might want to build a hash table with the ivar values and their corresponding parent object perhaps? In other words, index the ivar values, but you'd have to write some code to keep your table and the underlying model data in sync. I can't wait to hear how wrong my approach is lol.

 

[mdeh]

If speed is critical, I suspect you might want to build a hash table with the ivar values and their corresponding parent object perhaps? In other words, index the ivar values, but you'd have to write some code to keep your table and the underlying model data in sync. I can't wait to hear how wrong my approach is lol.

Well, perhaps a little more insight into what I am doing would help.
Let's say one of the ivars is "letter", another is "theCount" and the last is "alternativeLetter". So, the idea would be to get a query that would present a letter, and the code would then have to check the dictionary if the letter was already present in the "LetterInfoObject", increment the count if it was present, or create a new object with a new letter if none was found. At some point, the program would suggest an "Alternative" letter and of course, this would lead to the search once again for that letter, but this time setting a new value for that ivar. I don't think displaying the data is going to be that hard, but searching for that letter has me bamboozled...unless I use brute force?

 

[lee1210]

GorillaPaws approach still seems sound after you explained further. Your NSMutableDictionary's keys would be the letters(probably wrapped in something, since the key has to be an NSObject), the value would be the instance if your class for that letter. A new letter is entered, so you grab the object with that value. If there is none (nil is returned), create a new instance and insert into the dictionary. If an object us returned, increment the count.

I'm not sure about the alternate letter stuff. If you need to find the object with a particular alternate letter fast, I'd just use a second NSMutableDictionary with alternate letter for the key. You'd have to be sure you added to this when a new letter came in.

How you'd manipulate the dictionaries when you do your alternate replacement might be involved, but I didn't quite understand that piece.

-Lee

Edit: while it's sloppier, you could have a C-style array of LetterInfoObject * with a length equal to the number of possible letters. Initialize to nil. Then use the entered letter as the index. If the value is non-nil, increment. Otherwise instantiate and store the pointer. This will cost memory, but would definitely be fast for lookups.

 

[mdeh]

GorillaPaws approach still seems sound after you explained further. Your NSMutableDictionary's keys would be the letters(probably wrapped in something, since the key has to be an NSObject), the value would be the instance if your class for that letter.
-Lee

Lee, you hit the nail on the head as far as making each letter a key in the dictionary. Sorry about the really dumb question, but when you say "probably wrapped in something" could you perhaps enlighten further ie what exactly do you do? ( I do understand the issue of only having an object in a dictionary)

Thanks as always for answering.

 

[jpyc7]

This is a pattern I've used, but I don't know if it is in the Gang of Four design patterns book.

You will want to have at least 2 dictionaries. One dictionary is keyed by Letter and the other by AlternativeLetter. Both dictionaries contain pointers to the class instances, LetterInfoObject. This means the memory for the LetterInfoObject would have to come from the heap (unless you want to implement your own memory management for them).

You have to update the appropriate dictionary whenever you change the value of Letter or AlternativeLetter. By just using pointers, your data sync problem is limited to just the keys to the dictionary. When you change the key value, you delete the old key from the dictionary and insert the new key.

Anyway, the general design pattern is that you have Collections which simply hold pointers to your class instances. You can search for class instances via any collection as needed by your program. Each collection has a key (Index) that is a subset of attributes from your object. Each collection uses the appropriate data structure, like hash or binary tree for efficient search/insert/delete, etc. A collection is updated when the subset of attributes that correspond to the collection's key change.

That said, I'm not sure in your example what your initial query was based on. It sounds like you might need another collection for that query. Also, while I was writing this post, I see Lee's post, which suggests that you're just doing the query based on a Letter that is submitted by the user.

 

[chown33]

Please describe what you're trying to accomplish, rather than the way you're trying to accomplish it. Or describe the end result or the user experience, not how you think the code should implement it.

I'm confused about the role of "theCount" in your second explanation. It almost sounds like you have some kind of Markov chain, or maybe a tree of weighted digraphs (letter pairs that occur at some non-uniform frequency), and you want to produce a sequence from them. But since I can't see what you're trying to accomplish, I could be mistaken.

For example, are you trying to do something like Google's text-entry field (http://google.com/), where you type letters one at a time and it shows a ranked list of suggestions? Are you trying to write a "travesty generator" (aka "parody generator") that produces semi-random texts in the style of some input text?

 

[mdeh]

Please describe what you're trying to accomplish, rather than the way you're trying to accomplish it. Or describe the end result or the user experience, not how you think the code should implement it.

Sure.
I want to take a piece of text, and analyze it. The analysis will display a 2 column table with the number of occurrences of each letter. Another table will show a second analysis which, as the user replaces a single letter from the text with another, shows the old letter in one column, with the new substituted letter in the second column.

I thought the most efficient way was to use a single "info" object that would hold the letter, "number of occurences" and the substituted letter. But, translating that to something efficient and usable, is the interesting part!

 

[mdeh]

This is a pattern I've used, but I don't know if it is in the Gang of Four design patterns book.

You will want to have at least 2 dictionaries. One dictionary is keyed by Letter and the other by AlternativeLetter. Both dictionaries contain pointers to the class instances, LetterInfoObject. This means the memory for the LetterInfoObject would have to come from the heap (unless you want to implement your own memory management for them).

You have to update the appropriate dictionary whenever you change the value of Letter or AlternativeLetter. By just using pointers, your data sync problem is limited to just the keys to the dictionary. When you change the key value, you delete the old key from the dictionary and insert the new key.

Anyway, the general design pattern is that you have Collections which simply hold pointers to your class instances. You can search for class instances via any collection as needed by your program. Each collection has a key (Index) that is a subset of attributes from your object. Each collection uses the appropriate data structure, like hash or binary tree for efficient search/insert/delete, etc. A collection is updated when the subset of attributes that correspond to the collection's key change.

That said, I'm not sure in your example what your initial query was based on. It sounds like you might need another collection for that query. Also, while I was writing this post, I see Lee's post, which suggests that you're just doing the query based on a Letter that is submitted by the user.

Thank you jpyc7. Your input is appreciated.

 

[lee1210]

when you say "probably wrapped in something" could you perhaps enlighten further ie what exactly do you do? ( I do understand the issue of only having an object in a dictionary)

The most obvious way to handle this is using an NSNumber, grabbing new ones using numberWithChar:. Then you can get your char back out with charValue:.

There aren't specialized wrappers for every primitive in Objective-C like there is in, say, Java. Java also has a nice feature called autoboxing and autounboxing that will stick, say, an int into an Integer implicitly when you try to use a primitive where an object is required.

-Lee

 

[mdeh]

The most obvious way to handle this is using an NSNumber, grabbing new ones using numberWithChar:. Then you can get your char back out with charValue:.

Hi Lee,
Aha! I misunderstood you....and I also somewhat misstated the word "letter" perhaps implying it was some type of primitive. In fact, "letter" is an NSString Object, so , if I understand this correctly, (hopefully) there is no need to wrap this to store it in a collection. Mind you, "numberWithChar" is an interesting possibility too, allowing less conversions from the get go. Thanks

 

[lee1210]

Ah, if you already have something that inherits from NSObject, there's no need to do anything else to use it as a key in an NSMutableDictionary, so you should be good to go.

-Lee

 

[JoshDC]

How about using an NSCountedSet for the original frequency analysis? This way all you have to do is iterate though the string one character at a time and add it to the counted set. It does the rest for you. For the alternative character you could use a mutable dictionary with the letter as the key and alternate letter as the value.

 

[mdeh]

How about using an NSCountedSet for the original frequency analysis? This way all you have to do is iterate though the string one character at a time and add it to the counted set. It does the rest for you. For the alternative character you could use a mutable dictionary with the letter as the key and alternate letter as the value.

Thanks Josh...nice thought. That's why I asked.