Verificare le stringhe per gli stessi caratteri in Objective-C

Question

Ho una matrice di stringhe, da cui vorrei estrarre solo quelli con set di caratteri univoci. (Ad esempio, "asdf" e "fdsa" sarebbero considerati ridondanti). Questo è il metodo attualmente sto usando:

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]; 
    } 
} 

Questo sembra funzionare, ma è molto lento e molte risorse. Qualcuno può pensare a un modo migliore per farlo?

Answer 1

Ho appena messo insieme un rapido esempio di come mi avvicinerei a questo, ma si scopre che è più, strano, di quanto inizialmente ti aspetti. Per uno, NSCharacterSet non implementa l'uguaglianza per controllare il contenuto. Usa solo il valore del puntatore. Sulla base di questo tuo esempio NON funzionerà correttamente.

Il mio approccio è utilizzare una NSSet per gestire l'hashing di questi per noi.

@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; 
} 

Il codice è piuttosto semplice. Creiamo un oggetto contenitore per memorizzare nella cache i risultati della rappresentazione bitmap del set di caratteri. Usiamo la rappresentazione bitmap perché NSData implementa isEqual: in modo appropriato.

Answer 2

L'unica cosa che mi vengono in mente è di non usare containsObject: dal NSMutableArray non è ordinata (in generale), si può supporre che containsObject semplicemente itera la matrice a partire dall'inizio finché non trova l'oggetto. Questo significa O(n) (n confronti nel caso peggiore).

Una soluzione migliore può consistere nel mantenere ordinato l'array e utilizzare un metodo di ricerca personalizzato utilizzando uno dichotomic approach. In questo modo avrai una complessità O(log n).
Naturalmente, è necessario assicurarsi di mantenere ordinato il proprio array (molto più efficiente di aggiungere e riordinare), quindi è necessario utilizzare il metodo insertObject:atIndex: per inserire correttamente l'elemento.

Answer 3

1. Utilizzando un NSDictionary, la mappa equivalente lessicografico-ordinato di ogni stringa in un NSArray di stringhe di input: (es adfs =>[afsd, asdf, ...])
2. Passeggiata attraverso il dizionario, la stampa di chiavi (o dei loro valori) che hanno solo valori di array a elemento singolo