Как узнать индексы наименьших 15 объектов внутри массива NSMutable и сохранить эти индексы в другом массиве

Question

Как узнать индексы наименьших 15 объектов внутри массива NSMutable и сохранить эти индексы в другом массиве Im, пишущий мою программу в объективе-c я пытался использовать для циклов, но пока не смог найти подходящий алгоритм.

Answer 1

Самый простой способ - отсортировать массив и выбрать первые 15 элементов.

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

CoreFoundation предоставляет CFBinaryHeap, который может быть использован для этой цели, хотя вы получите удовольствие от получения id с входом и выходом void * s. Также есть NDHeap, о котором я ничего не знаю (кроме того, что он существует и имеет целью реализовать двоичную кучу).

Моим преимуществом было бы использовать C++ std::priority_queue, который тщательно протестирован и обрабатывает id s просто отлично с небольшим уговором.

auto lt = [](id a, id b) { return (whatever means "a < b" to you); }; 
std::priority_queue<id, std::vector<id>, decltype(lt)> pq{lt}; 

for (id e in myarray) { 
    if (pq.size() == 15 && lt(e, pq.top())) 
     pq.pop(); 
    if (pq.size() < 15) 
     pq.push(e); 
} 

NSMutableArray * top15 = [NSMutableArray arrayWithCapacity:15]; 
while (!pq.empty()) { 
    [top15 addObject:pq.top()]; 
    pq.pop(); 
} 

Для использования этого кода вам необходимо переименовать соответствующий .m файл в .mm.