Что такое эффективный способ поиска корыто NSArray

Question

У меня есть NSStrings в моем массиве:

i[0] = axxx 
i[1] = axyz 
i[2] = axxy 
i[3] = abcd 

Я хочу передать строку поиска, чтобы найти все необходимые строки. Например, если я передаю «ax», тогда он вернет 3 строки, если я передам «axx», тогда он вернет 2 строки.

Производительность здесь также важна. Метод должен выглядеть следующим образом:

- (NSArray *)searchString:(NSString *)search; 

Noramlly Я использую NSPredicate, но на этот раз мне нужно использовать, может быть дерево префиксов или бинарное дерево, я не уверен, но это должно быть быстрее. Любое предложение или ссылки на реализацию.

Answer 1

Надеюсь, что это решение удовлетворит вас.

- (NSArray *)searchString:(NSString *)search{ 

    NSIndexSet *indexes = [dataArray indexesOfObjectsPassingTest: 
          ^BOOL (id obj, NSUInteger i, BOOL *stop) { 
           NSString *myObj = obj; 
           return [myObj containsString:search]; 
          }]; 
    NSArray *results = [dataArray objectsAtIndexes:indexes]; 

    return results; 

} 

Answer 2

Это довольно простая проблема.

Как указывает Ави в своем комментарии, есть две части: метод, который вы используете для сопоставления, и метод, который вы используете для поиска этих совпадений.

Если ваш массив отсортирован и вы ищете единственное идеальное совпадение, вы можете использовать двоичный поиск. Я считаю, что это даст вам производительность O (log (n)). (Время увеличивается с журналом количества элементов.)

Однако вы не ищете ни одного идеального матча. Вы ищете частичные матчи. Если они всегда должны совпадать с началом строки, вы все равно сможете использовать двоичный поиск, чтобы найти первое совпадение, а затем линейно искать вверх и вниз в массиве до первого несоответствия. Это даст вам немного хуже производительности O (log (n)), но не так плохо, как O (n).

Если вы соответствуете своей подстроке где-нибудь внутри записей, я думаю, вам придется проверять каждый элемент в массиве. Вам просто нужно будет проверить каждый элемент, предоставляя вам O (n) производительность.

Обратите внимание, что производительность O (n) обычно считается хорошей. Он хорошо масштабируется для больших наборов данных. (Вы хотите избежать производительности O (n^2). Это то, что вас убивает.)

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

Answer 3

Отсутствует существенная информация. Если вы ищете «axx», вы ожидаете, что «haxx» будет в ваших результатах? "HaXX"? "Axxyyyz"? «Ахй»? Сколько строк у вас есть? 10? 100? 1000? 100000? Как часто вы выполняете этот поиск? Как часто изменяется массив?

Первый шаг - выяснить, какой метод NSString будет соответствовать строкам, которые вы хотите сопоставить. Второй шаг - реализовать с использованием грубой силы и измерения (предикаты обычно в несколько раз медленнее, чем цикл через массив). Третий шаг - выяснить, может ли помочь сортировка данных.