macOS Advice on an approach to a problem please

mdeh · Mar 15, 2010

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 · Mar 15, 2010

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 · Mar 15, 2010

GorillaPaws said:
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 · Mar 15, 2010

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 · Mar 15, 2010

lee1210 said:
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 · Mar 15, 2010

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 · Mar 15, 2010

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 · Mar 16, 2010

chown33 said:
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 · Mar 16, 2010

jpyc7 said:
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 · Mar 16, 2010

mdeh said:
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 · Mar 16, 2010

lee1210 said:
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 · Mar 16, 2010

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 · Mar 16, 2010

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 · Mar 16, 2010

JoshDC said:
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.

Search

Search

macOS Advice on an approach to a problem please

mdeh

macrumors 6502

GorillaPaws

macrumors 6502a

mdeh

macrumors 6502

lee1210

macrumors 68040

mdeh

macrumors 6502

jpyc7

macrumors 6502

chown33

Moderator

mdeh

macrumors 6502

mdeh

macrumors 6502

lee1210

macrumors 68040

mdeh

macrumors 6502

lee1210

macrumors 68040

JoshDC

macrumors regular

mdeh

macrumors 6502

Our Staff