Búsqueda de un NSArray para el número más cercano

Question

¿Existe una forma fácil de buscar números NSArray para encontrar las coincidencias más cercanas (o exactas si existen) con un número de entrada de usuario?

Digamos que tengo una matriz como esta: 7, 23, 4, 11, 18, 2, y el usuario ingresa 5.

El programa devuelve los tres valores más cercanos con el fin de cercanía descendente: 4, 7, 2, y lo más importante da el índice de los tres objetos NSArray: 2, 0, 5.

Answer 1

Actualización: ver más abajo para una solución mejor que el primero.

Aquí hay una solución que usa envoltorios NSDictionary para cada número y su índice, con clasificación usando un bloque de comparación. Probablemente no se escala muy bien, pero hace el trabajo bien.

static NSString *const kValueKey = @"value"; 
static NSString *const kIndexKey = @"index"; 

+ (void)searchArray:(NSArray *)array forClosestValuesTo:(int)value resultValues:(NSArray **)values resultIndexes:(NSArray **)indexes 
{ 
    NSMutableArray *searchObjs = [NSMutableArray arrayWithCapacity:[array count]]; 

    [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { 
     [searchObjs addObject:[NSDictionary dictionaryWithObjectsAndKeys:obj, kValueKey, [NSNumber numberWithUnsignedInt:idx], kIndexKey, nil]]; 
    }]; 

    [searchObjs sortUsingComparator:^NSComparisonResult(id obj1, id obj2) { 
     NSUInteger d1 = ABS([[obj1 objectForKey:kValueKey] intValue] - value); 
     NSUInteger d2 = ABS([[obj2 objectForKey:kValueKey] intValue] - value); 
     if (d1 == d2) { return NSOrderedSame; } 
     if (d1 < d2) { return NSOrderedAscending; } 
     return NSOrderedDescending; 
    }]; 

    NSArray *results = [searchObjs subarrayWithRange:NSMakeRange(0, 3)]; 

    if (values) { 
     *values = [results valueForKey:kValueKey]; 
    } 

    if (indexes) { 
     *indexes = [results valueForKey:kIndexKey]; 
    } 
} 

Actualización: he aquí una solución actualizada que ordena una matriz C de índices, eliminando la necesidad de envolturas NSDictionary

static NSString *const kValueKey = @"value"; 
static NSString *const kArrayKey = @"array"; 

int 
CSCompareIndexes(void *data, const void *value1, const void *value2) 
{ 
    NSDictionary *dict = (NSDictionary *)data; 

    NSArray *array = [dict objectForKey:kArrayKey]; 
    int valueToFind = [[dict objectForKey:kValueKey] intValue]; 

    int index1 = *(int *)value1; 
    int index2 = *(int *)value2; 

    NSNumber *num1 = [array objectAtIndex:index1]; 
    NSNumber *num2 = [array objectAtIndex:index2]; 

    return ABS([num1 intValue] - valueToFind) - ABS([num2 intValue] - valueToFind); 
} 

void 
CSSearchNumberArray(NSArray *array, int valueToFind, NSArray **resultValues, NSArray **resultIndexes) 
{ 
    NSInteger numValues = [array count]; 

    NSUInteger *indexes = malloc(sizeof(NSUInteger) * numValues); 
    assert(indexes); 

    int i; 
    for (i = 0; i < numValues; i++) { 
     indexes[i] = i; 
    } 

    NSDictionary *data = [NSDictionary dictionaryWithObjectsAndKeys:array, kArrayKey, [NSNumber numberWithInt:valueToFind], kValueKey, nil]; 
    qsort_r(indexes, numValues, sizeof(NSUInteger), (void *)data, CSCompareIndexes); 

    NSMutableArray *tmpValues = [NSMutableArray arrayWithCapacity:3], 
        *tmpIndexes = [NSMutableArray arrayWithCapacity:3]; 

    for (i = 0; i < 3; i++) { 
     [tmpValues addObject:[array objectAtIndex:indexes[i]]]; 
     [tmpIndexes addObject:[NSNumber numberWithInt:indexes[i]]]; 
    } 

    if (resultValues) { 
     *resultValues = [NSArray arrayWithArray:tmpValues]; 
    } 

    if (resultIndexes) { 
     *resultIndexes = [NSArray arrayWithArray:tmpIndexes]; 
    } 

    free(indexes); 
} 

int main (int argc, char *argv[]) 
{ 
    NSAutoreleasePool *pool = [NSAutoreleasePool new]; 

    NSMutableArray *test = [NSMutableArray array]; 

    int i; 
    for (i = 0; i < 10; i++) { 
     [test addObject:[NSNumber numberWithInt:(arc4random() % 100)]]; 
    } 

    NSLog(@"Searching: %@", test); 

    NSArray *values, *indexes; 
    CSSearchNumberArray(test, 50, &values, &indexes); 

    NSLog(@"Values: %@", values); 
    NSLog(@"Indexes: %@", indexes); 

    [pool drain]; 
    return 0; 
} 

Answer 2

¿Es esta una pregunta de tarea? Una manera fácil de codificar esto mediante la utilización de apis es generar una matriz llamada distances que contiene la distancia de cada número original, crear una versión ordenada de esa matriz llamada sorted, luego buscar distances para obtener los tres números más bajos en sorted para obtener el índice de que puedes buscar el número original.

Answer 3

El método ingenuo sería buscar en la matriz de origen para 5, incrementar el recuento encontrado y almacenar la información apropiada si se encuentra, a continuación, busque y 46, etc.

Un segundo método sería la de mantener una copia ordenada de la matriz de origen: 2, 4, 7, 11, 18, 23

a continuación, utilizar -indexOfObjectPassingTest: para encontrar el primer número mayor que 5 en esa matriz, y luego comparar ese número con su vecino de la izquierda, para ver lo que está más cerca de 5:

(7-5) < (5-4) ? storeinfo(7) : storeinfo(4)

Si el vecino de la izquierda gana, almacenar su información, a continuación, comparar su vecino de la izquierda con el original mayor a la de cinco números:

(7-5) < (5-2) ? storeinfo(7) : storeinfo(2)

Pero si el lado derecho victorias, comparar su vecino de la derecha con el perdedor:

(11-5) < (5-2) ? storeinfo(11) : storeinfo(2)

Solo debe hacer tres comparaciones en este caso, y deberá decidir si desea usar < o <=. Su segunda matriz es simplemente tamaño n * ptr, por lo que no es un gran crecimiento de espacio.

Answer 4

Ordene la matriz existente de valores "indirectamente", usando una matriz de índices, y ordenando por la "distancia" al valor de búsqueda. Los tres primeros elementos después del género son los valores "más cercanos".

Ejemplo:

#import <Foundation/Foundation.h> 

@interface NearestSearcher : NSObject { } 
+ (NSArray *) searchNearestValuesOf: (int) value inArray: (NSArray *) values; 
@end 

@implementation NearestSearcher 

+ (NSArray *) searchNearestValuesOf: (int) value inArray: (NSArray *) values 
{ 
    // set up values for indexes array 
    NSMutableArray *indexes = [NSMutableArray arrayWithCapacity: values.count]; 
    for (int i = 0; i < values.count; i++) 
     [indexes addObject: [NSNumber numberWithInt: i]]; 

    // sort indexes 
    [indexes sortUsingComparator: ^NSComparisonResult(id obj1, id obj2) 
    { 
     int num1 = abs([[values objectAtIndex: [obj1 intValue]] intValue] - value); 
     int num2 = abs([[values objectAtIndex: [obj2 intValue]] intValue] - value); 

     return (num1 < num2) ? NSOrderedAscending : 
       (num1 > num2) ? NSOrderedDescending : 
           NSOrderedSame; 
    }]; 

    return [indexes subarrayWithRange: NSMakeRange(0, 3)]; 
} 
@end 


// DEMO 

#define NUM_VALUES 20 

int main (int argc, const char * argv[]) 
{ 

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; 

    // DEMO SETUP 

    // set up values array with random values 
    NSMutableArray *values = [NSMutableArray arrayWithCapacity: NUM_VALUES]; 
    for (int i = 0; i < NUM_VALUES; i++) 
     [values addObject: [NSNumber numberWithInt: arc4random() % 200]]; 

    // display values array 
    for (int i = 0; i < values.count; i++) 
     NSLog(@"%2d: %4d", i, [[values objectAtIndex: i] intValue]); 

    // get a random value for x 
    int x = arc4random() % 200; 

    // METHOD INVOCATION 

    NSArray *results = [NearestSearcher searchNearestValuesOf: x inArray: values]; 

    // SHOW RESULTS 

    NSLog(@"------------------------"); 

    NSLog(@"x: %d", x); 
    for (NSNumber *num in results) 
     NSLog(@"%@: %@", num, [values objectAtIndex: [num intValue]]); 

    [pool drain]; 
    return 0; 
} 

Answer 5

Código Probado: 100% trabaja

NSMutableArray *arrayWithNumbers=[[NSMutableArray alloc]initWithObjects:[NSNumber numberWithInt:7],[NSNumber numberWithInt:23],[NSNumber numberWithInt:4],[NSNumber numberWithInt:11],[NSNumber numberWithInt:18],[NSNumber numberWithInt:2],nil]; 

NSLog(@"arrayWithNumbers : %@ \n\n",arrayWithNumbers); 





NSMutableArray *ResultArray = [ [ NSMutableArray alloc] init]; 

NSMutableArray *lowestArray = [ [ NSMutableArray alloc] init]; 

NSMutableArray *tempArray = [ [ NSMutableArray alloc] init]; 

NSMutableArray *indexArray = [ [ NSMutableArray alloc] init]; 


NSNumber *numberToFind=[NSNumber numberWithInt:5]; 

int limitToFilter = 3; 


    for (NSNumber *number in arrayWithNumbers) { 

     int a=[number intValue]-[numberToFind intValue]; 

     [lowestArray addObject:[NSNumber numberWithInt:abs(a)]]; 


    } 

tempArray=[lowestArray mutableCopy]; 

NSSortDescriptor *LowestTohighest = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES]; 

[lowestArray sortUsingDescriptors:[NSArray arrayWithObject:LowestTohighest]]; 

int upto = limitToFilter-[ResultArray count]; 

for (int i = 0; i < upto; i++) { 


    [lowestArray objectAtIndex:i]; 

    if ([tempArray containsObject:[lowestArray objectAtIndex:i]]) { 


     NSUInteger index=[tempArray indexOfObject:[lowestArray objectAtIndex:i]]; 



     [ResultArray addObject:[arrayWithNumbers objectAtIndex:index]]; 


     [indexArray addObject:[NSIndexSet indexSetWithIndex:index]]; 



    } 

} 

NSLog(@"ResultArray is : %@ \n\n",ResultArray); 

NSLog(@"indexArray is : %@ \n\n",indexArray); 


    //here release all 4 arrays if u dont need them 

SALIDA:

arrayWithNumbers: ( 7, 23, 4, 11, 18,)

ResultArray es: ( 4, 7,)

indexArray es: (

"<NSIndexSet: 0x4e06620>[number of indexes: 1 (in 1 ranges), indexes: (2)]", 

    "<NSIndexSet: 0x4e04030>[number of indexes: 1 (in 1 ranges), indexes: (0)]", 

    "<NSIndexSet: 0x4e06280>[number of indexes: 1 (in 1 ranges), indexes: (5)]" 

     )