Re: NSSet Inefficiency
Re: NSSet Inefficiency
- Subject: Re: NSSet Inefficiency
- From: Nat! <email@hidden>
- Date: Mon, 25 Mar 2002 00:25:29 +0100
Well, a NSNumber with ints or longs has a perfect hash function:
never will two different objects have the same hash value.
This is not always possible for other objects.
But you have to try hard to get there. NSSet becomes quickly
unusable if you don't hash well. Try my last program with the
following additions that make the hash worst case instead of best
case. And the time spent for 20 thousand objects (not 2 mio objects
as before) becomes 90 seconds.
The problem is that all objects are asked "isEqual:" the more
objects you have the lamer it gets. If you can't hash well at all
try some tree structure...
#import <Foundation/Foundation.h>
#define LOOPS 20000
@interface MyNumber : NSObject
{
unsigned long value_;
}
@end
@implementation MyNumber
- (id) initWithUnsignedLong:(unsigned long) value
{
[super init];
value_ = value;
return( self);
}
- (unsigned int) hash
{
return( 2222222);
}
- (BOOL) isEqual:(MyNumber *) other
{
return( other->value_ == self->value_);
}
@end
static NSObject *my_subroutine_returning_non_autoreleased_object
( unsigned long i)
{
return( [[MyNumber alloc] initWithUnsignedLong:i]);
}
Without knowing what the data might look like, the only suggestion
I have for a hash would be to try CRC32 on the data. (You can get
an implementation from
http://www.mulle-
kybernetik.com/software/MulleCipher)
No promises :)
Cheers
Nat!
------------------------------------------------------
Some people drink deep from the fountains of life, and
some just gargle. -- DLR
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.