Re: Mutually exclusive item filtering-comparing
Re: Mutually exclusive item filtering-comparing
- Subject: Re: Mutually exclusive item filtering-comparing
- From: Chris Paveglio <email@hidden>
- Date: Tue, 05 Nov 2013 14:47:42 -0800 (PST)
Could you expand on that a bit or maybe send me a link for more info? My ID numbers aren't sequential from 0 to 100. They are somewhat random (457, 853, 1587, etc). An example would be {item1ID: 234, itemID2: 3987, exclusive:yes}. From your explanation, would a bitmap index work? Adding my item# together and multiply n wouldn't give a real offset to a bit in a bitmap.
Chris
On Tuesday, November 5, 2013 2:07 PM, Jens Alfke <email@hidden> wrote:
On Nov 5, 2013, at 10:17 AM, Chris Paveglio <email@hidden> wrote:
My exclusions array has many simple objects. Each object has 3 ivars- (int)itemID1, (int)itemID2, (string)isMutuallyExclusive (not my design but could be changed if there is a better way).
>
You can build a bitmap out of this for efficient testing. If there are n possible items, then it’s an n x n array of bits where a 1 entry means the two items are mutually exclusive. (To be specific, you index it by computing n * itemID1 + itemID2, then using that as a bit index into the data. Get the byte at index/8, then test the bit at index%8. Or just use an NSMutableIndexSet.)
So, repeat with 100 items in the table, each table row comparing against the exclusion list which has over 100 entries. It could result in up to 10,000 comparisons getting tested until the exclusion is found or exhausted.
>
Doing 10,000 lookups in a bitmap won’t take a noticeable amount of time.
—Jens
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden