Objective-C: наиболее эффективный способ сопоставления номера с соответствующим NSRange в NSDictionary

#objective-c #performance #algorithm

#objective-c #Производительность #алгоритм

Вопрос:

У меня много объектов с соответствующими диапазонами:

 Object1 => 0 - 23
Object2 => 24 - 84
Object3 => 85 - 103
...

Эти диапазоны различаются, теперь я ищу наиболее эффективный способ в Objective-C сказать: «Хорошо, у меня есть число 56; какой объект имеет соответствующий диапазон? Ах, да: это Object2 «.

Есть идеи? Двоичный поиск? Что-то еще?

Большое спасибо!

1. Сохраните конечные точки диапазонов и используйте двоичный поиск =)

2. NSArray Использование filteredArrayUsingPredicate также будет работать (но будет менее эффективным). После фильтрации массива вы можете получить индекс NSRange объекта и использовать этот индекс для получения ваших пользовательских объектов из другого NSArray , связанного с этим диапазоном. См. Руководство по программированию предикатов .

3. Боюсь, я ищу наиболее эффективный способ, поэтому фильтрация не вариант. Я полагаю, что я заканчиваю бинарным поиском?

4. Всегда ли диапазоны следуют друг за другом без пробелов? Например, никогда (3,6), (9,20)?

5. да, пробелов нет! ваш пример: 0-2, 3-6, 7-8, 9-20, 21-…

Ответ №1:

Это очень похоже на нахождение позиции указанного значения в отсортированном списке различных точек вашего сегмента, в вашем случае вы можете взять, например : [-0.5,23.5,84.5,103.5] это список средней точки между началом и концом каждого сегмента.

если позиция указанного вами значения равна 1 => объект 1

если это 2 => object2

если это 3 => объект 3

Для 56 вы получите 2 => объект 2

надеюсь, это поможет

Редактировать :

Для массива A размера N псевдокод для этого модифицированного двоичного поиска будет следующим.

   min := 0; //my array start at index 0
  max := N-1; 
  repeat
    mid := (min max) div 2;
    if x > A[mid] then
      min := mid   1;
    else
      max := mid - 1;
  until (A[mid 1] > x >A[mid]) or (min > max);
  return mid 1

Я изменил условие до (см. статью Википедии о двоичном поиске), чтобы соответствовать ограничению проблемы. Я изменяю mid до тех пор, пока x не окажется между 2 элементами, и я возвращаю mid 1

1. звучит интересно… но как я могу управлять тем, что 56 доставляет 2? Я полагаю, я снова в двоичном поиске?

2. @swalkner Я пытался написать псевдокод для двоичного поиска, я отредактировал свой пост, идея поиска состоит в том, чтобы найти, где я могу вставить X в A. (A отсортирован), извините, я недостаточно знаю objective C, чтобы перевести код в objective C