Основание Objective-c: словарь с массивом;Дикт с Диктом - PullRequest
Новая
       15

Основание Objective-c: словарь с массивом;Дикт с Диктом

3 голосов
/ 29 апреля 2011

Предположим, у меня есть NSDictionary с двумя вложенными коллекциями NSArray и NSDictionary: 

NSMutableDictionary *mkDict(void){
    NSMutableDictionary *dict=[NSMutableDictionary dictionary];
    NSMutableDictionary *sub=[NSMutableDictionary dictionary];
    NSMutableArray *array= [NSMutableArray array];
    [dict setObject:array forKey:@"array_key"];
    [dict setObject:sub forKey:@"dict_key"];
    return dict;
}

Существует множество способов получить доступ к одному элементу вложенной коллекции, и я выбрал время для трех из них.

Первый способ - это косвенный доступ к подэлементам путем доступа к ключу родительского элемента: 

void KVC1(NSMutableDictionary *dict, int count){

    for(int i=0; i<count; i++){
        char buf1[40], buf2[sizeof buf1];
        snprintf(buf1,sizeof(buf1),"element %i", i);
        snprintf(buf2, sizeof buf2, "key %i", i);

        [[dict objectForKey:@"array_key"] 
          addObject:
             [NSString stringWithUTF8String:buf1]];
        [[dict objectForKey:@"dict_key"] 
          setObject:[NSString stringWithUTF8String:buf1] 
          forKey:[NSString stringWithUTF8String:buf2]];
    }
}

Второй - использовать KeyPath-доступ: 

void KVC2(NSMutableDictionary *dict, int count){

    for(int i=0; i<count; i++){
        char buf1[40], buf2[sizeof buf1], buf3[sizeof buf1];
        snprintf(buf1,sizeof(buf1),"element %i", i);
        snprintf(buf2, sizeof buf2, "key %i", i);
        snprintf(buf3, sizeof buf3, "dict_key.key %i",i);

        [dict insertValue:
             [NSString stringWithUTF8String:buf1] 
            atIndex:i inPropertyWithKey:@"array_key"];
        [dict setValue:
             [NSString stringWithUTF8String:buf1] 
            forKeyPath:
             [NSString stringWithUTF8String:buf3]];
    }
}

И третий, аналогичный первому, - получить доступ к указателю на подэлемент, а затем использовать этот указатель: 

void KVC3(NSMutableDictionary *dict, int count){

    NSMutableArray *subArray = [dict objectForKey:@"array_key"];
    NSMutableDictionary *subDict = [dict objectForKey:@"dict_key"];

    for(int i=0; i<count; i++){
        char buf1[40], buf2[sizeof buf1];
        snprintf(buf1,sizeof(buf1),"element %i", i);
        snprintf(buf2, sizeof buf2, "key %i", i);

        [subArray addObject:[NSString stringWithUTF8String:buf1]];
        [subDict 
           setObject:
            [NSString stringWithUTF8String:buf1] 
           forKey:
            [NSString stringWithUTF8String:buf2]];
    }
}

Вот код времени: 

#import <Foundation/Foundation.h>
#import <mach/mach_time.h>

// KVC1, KVC2 and KVC3 from above...

#define TIME_THIS(func,times) \
({\
mach_timebase_info_data_t info; \
mach_timebase_info(&info); \
uint64_t start = mach_absolute_time(); \
for(int i=0; i<(int)times; i++) \
func ; \
uint64_t duration = mach_absolute_time() - start; \
duration *= info.numer; \
duration /= info.denom; \
duration /= 1000000; \
NSLog(@"%i executions of line %i took %lld milliseconds", times, __LINE__, duration); \
});

int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSMutableDictionary *dict=mkDict();
    NSMutableDictionary *dict2=mkDict();
    NSMutableDictionary *dict3=mkDict();

    TIME_THIS(KVC1(dict,1000),10);
    TIME_THIS(KVC2(dict2,1000),10);
    TIME_THIS(KVC3(dict3,1000),10);

    if([dict isEqualToDictionary:dict2])
        NSLog(@"And they are the same...");
    [pool drain];
    return 0;
}

Вот результаты: 

10 executions of line 256 took 57 milliseconds
10 executions of line 257 took 7930 milliseconds
10 executions of line 258 took 46 milliseconds
And they are the same...

Вопрос: Почему OS X Snow Leopard / Lion предложил метод использования KeyPaths настолько вонючий медленный? Если вы увеличите размер count до 10000 или более, KVC2 станет бесконечно медленным, тогда как два других метода увеличиваются линейно.

Я что-то не так делаю? Есть ли лучшая идиома для доступа к одному элементу вложенной коллекции в словаре?

Ответы [ 3 ]

3 голосов
/ 29 апреля 2011

В KVC2(), вы отправляете 

[dict insertValue:[NSString stringWithUTF8String:buf1] 
          atIndex:i
inPropertyWithKey:@"array_key"];

Документация для этого метода гласит следующее:

Метод insertIn<Key>:atIndex: вызывается, если он существует. Если соответствующий метод, соответствующий сценариям-KVC (insertIn<Key>:atIndex:), не найден, этот метод вызывает mutableArrayValueForKey: и изменяет результат.

Поскольку сообщение отправляется на dict, экземпляр NSDictionary, метод -insertIn<Key>:atIndex: отсутствует, следовательно, -mutableArrayValueForKey: отправляется. Документация для этого метода гласит следующее:

Возвращаемое значение Прокси с изменяемым массивом, обеспечивающий доступ на чтение и запись к упорядоченному отношению ко многим, заданному ключом.

Обсуждение Объекты, добавленные в изменяемый массив, становятся связанными с получателем, а объекты, удаленные из изменяемого массива, становятся несвязанными. Реализация по умолчанию распознает те же самые простые методы доступа и методы доступа к массиву, что и valueForKey:, и следует тем же политикам доступа к переменным прямого экземпляра, но всегда возвращает изменяемый объект прокси изменяемой коллекции вместо неизменяемой коллекции, которую valueForKey: вернет.

Итак, что происходит, это на каждой итерации:

  1. Прозрачный изменяемый массив создается как изменяемая копия исходного массива;
  2. Объект добавлен в массив прокси;
  3. Прокси-массив добавляет тот же объект к исходному массиву.

Если вы используете инструменты для профилирования вашей программы, вы заметите, что около 50% времени обработки тратится на -[NSKeyValueSlowMutableArray insertObject:atIndex:] - я думаю, можно с уверенностью предположить, что NSKeyValueSlowMutableArray - это прокси-массив, и его имя должно быть ключ к его производительности.

1 голос
/ 29 апреля 2011

1-я и 3-я реализации имеют «статическую» ссылку на подэлементы, которая определенно не оценивается во второй раз в 3-й реализации.Изменчивость 2-й реализации при доступе к подэлементам, вероятно, вызывает проблемы со временем ... И [NSDictionary insertValue: atIndex: forPropertyKey:] имеет проблему вставки произвольного доступа в не статически оцениваемый элемент (NSMutableArray) и также является KVOПроцедура, которая может вызвать ряд неизвестных побочных эффектов ... Попробуйте еще раз без использования сценариев KVO insertValue: atIndex: forPropertyWithKey: и посмотрите, если keyPath медленный, держу пари, он медленнее других, но в разных масштабах

1 голос
/ 29 апреля 2011

Поскольку фреймворк должен выяснить, как получить элементы с заданным путем доступа к строке: разбор строк, проверка ошибок, создание дополнительных экземпляров строк и их освобождение.

Это предпочтительный способ из-за наблюдения значения ключа, привязки и т. Д., Так что Какао может сделать для вас большую часть своей магии.И медленный относительный: он может быть медленнее, чем прямой доступ, но слишком ли он медленный?Только профилирование реального варианта использования может показать вам, если он становится слишком медленным и если вам нужно оптимизировать.Если вы установите несколько переменных с помощью keypath в пользовательском интерфейсе, вы, вероятно, не заметите недостатка скорости, если вы попытаетесь обработать большое количество данных, тогда keypath, вероятно, не лучшее решение.Как я уже сказал: профиль вы используете.

Вы должны пойти на компромисс между простотой кода, доступом ко всем вкусностям, которые предоставляет Cocoa KVC, и скоростью, и вы узнаете ответ только тогда, когда увидитекод как часть большей картины.

...