Re: Mutually exclusive item filtering-comparing
Re: Mutually exclusive item filtering-comparing
- Subject: Re: Mutually exclusive item filtering-comparing
- From: Jens Alfke <email@hidden>
- Date: Tue, 05 Nov 2013 11:06:57 -0800
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