Sprawdź ciągi znaków dla tych samych znaków w Objective-C

Question

Mam tablicę ciągów, z których chciałbym wyodrębnić tylko te z unikalnymi zestawami znaków. (Na przykład "asdf" i "fdsa" będą uznane za zbyteczne). Jest to metoda, z której aktualnie korzystam:

NSMutableArray *uniqueCharSets = [[NSMutableArray alloc] init]; 
NSMutableArray *uniqueStrings = [[NSMutableArray alloc] init];   

for (NSString *_string in unique) { 
    NSCharacterSet *_charSet = [NSCharacterSet characterSetWithCharactersInString:_string]; 
    if (![uniqueCharSets containsObject:_charSet]) { 
     [uniqueStrings addobject:_string]; 
     [uniqueCharSets addObject:_charSet]; 
    } 
} 

To wydaje się działać, ale jest bardzo powolne i wymaga dużych zasobów. Czy ktoś może wymyślić lepszy sposób na zrobienie tego?

Answer 1

Po prostu połączyłem szybki przykład tego, jak do tego podejść, ale okazuje się, że jest bardziej, dziwnie, niż się spodziewasz. Po pierwsze, NSCharacterSet nie wprowadza równości w celu sprawdzenia zawartości. Używa tylko wartości wskaźnika. Na tej podstawie Twój przykład NIE będzie działał prawidłowo.

Moje podejście polega na wykorzystaniu NSSet do radzenia sobie z tym hashowaniem.

@interface StringWrapper : NSObject 
@property (nonatomic, copy) NSString *string; 
@property (nonatomic, copy) NSData *charSetBitmap; 
- (id)initWithString:(NSString*)aString; 
@end 

@implementation StringWrapper 
@synthesize string, charSetBitmap; 

- (id)initWithString:(NSString*)aString; 
{ 
    if ((self = [super init])) 
    { 
     self.string = aString; 
    } 
    return self; 
} 

- (void)setString:(NSString *)aString; 
{ 
    string = [aString copy]; 
    self.charSetBitmap = [[NSCharacterSet characterSetWithCharactersInString:aString] bitmapRepresentation]; 
} 

- (BOOL)isEqual:(id)object; 
{ 
    return [self.charSetBitmap isEqual:[object charSetBitmap]]; 
} 

- (NSUInteger)hash; 
{ 
    return [self.charSetBitmap hash]; 
} 

@end 

int main (int argc, const char * argv[]) 
{ 
    @autoreleasepool { 
     NSMutableSet *stringWrappers = [[NSMutableSet alloc] init]; 
     NSArray *strings = [NSArray arrayWithObjects:@"abc",@"aaabcccc",@"awea",@"awer",@"abcde", @"ehra", @"QWEQ", @"werawe", nil]; 
     for (NSString *str in strings) 
      [stringWrappers addObject:[[StringWrapper alloc] initWithString:str]]; 

     NSArray *uniqueStrings = [stringWrappers valueForKey:@"string"]; 
     NSLog(@"%@", uniqueStrings); 

    } 
    return 0; 
} 

Kod jest dość prosty. Tworzymy obiekt kontenera, aby buforować wyniki reprezentacji bitmap zestawu znaków. Używamy reprezentacji bitmap, ponieważ NSData implementuje odpowiednio: isEqual:.

Answer 2

Jedyną rzeczą, która się w moim umyśle nie jest w użyciu containsObject: od NSMutableArray nie jest zamawiany (w ogóle), możemy założyć, że containsObject prostu iteracje tablicę od początku, dopóki nie znajdzie się obiekt. Oznacza to w najgorszym przypadku porównania.

Lepszym rozwiązaniem może być uporządkowanie uporządkowanej tablicy i użycie niestandardowej metody wyszukiwania przy użyciu dichotomic approach. W ten sposób będziesz miał złożoność O(log n).
Oczywiście należy zadbać o zachowanie uporządkowanej tablicy (o wiele bardziej wydajnej niż dodawanie i zmiana kolejności), więc należy użyć metody insertObject:atIndex:, aby poprawnie wstawić element.

Answer 3

1. Korzystanie NSDictionary, mapa każdy łańcuch jest leksykograficznie-sortowane równoważnym do NSArray ciągów wejściowych (np adfs =>[afsd, asdf, ...])
2. Spacer słownika, drukując klawiszy (lub ich wartości), które tylko jednoelementowe wartości tablicowe