Как найти несколько верхних значений из массива?

StackOverflow https://stackoverflow.com/questions/617424

  •  03-07-2019
  •  | 
  •  

Вопрос

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

Изначально я построил систему так, чтобы она просматривала массив и находила максимальное значение обычным способом, сравнивая значение в текущей позиции с записанным максимальным значением на данный момент и обновляя переменную положения при изменении максимального значения на данный момент.Это сработало хорошо, алгоритм O (n) был очень простым.Позже я узнал, что мне нужно сохранить не только наивысшее значение, но и три или четыре лучших.Я расширил ту же процедуру и усложнил значение max-so-far до массива из четырех max-so-far, и теперь код получается уродливым.

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

Я делаю это в MATLAB с помощью функции сортировки, которая возвращает два массива, отсортированный список и сопровождающий его исходный список позиций.Просмотрев первые несколько значений, я получил именно то, что мне нужно.Я копирую эту функциональность в программу на C # .NET 2.0.

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

Это работало хорошо, но теперь я ловлю себя на том, что хочу получить пятое максимальное значение и вижу, что переписывание средства проверки max-so-far, которое в настоящее время представляет собой уродливую путаницу операторов if, только усугубит уродство.Это работало бы нормально, и добавление пятого уровня было бы не медленнее, но я хочу спросить сообщество SO, есть ли способ получше.

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

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

Это было полезно?

Решение

Я могу предложить альтернативный алгоритм, который вам придется кодировать:)

Используйте кучу размера K, где K обозначает количество верхних элементов, которые вы хотите сохранить. Инициализируйте это для первых K элементов вашего исходного массива. Для всех N - K элементов пройдитесь по массиву, вставляя по мере необходимости. 

proc top_k (array<n>, heap<k>)
heap <- array<1..k-1>
for each (array<k..n-1>) 
  if array[i] > heap.min
     heap.erase(heap.min)
     heap.insert(array[i])
  end if
end for

Другие советы

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

class IndexAndValue : IComparable<IndexAndValue>
{
    public int index;
    public double value;

    public int CompareTo(IndexAndValue other)
    {
        return value.CompareTo(other.value);
    }
}

Затем вы можете вставить их в список, сохранив при этом информацию об индексе. Если вы сохраняете только самые большие элементы в списке, то ваша эффективность должна быть O (mn).

Я не знаю, какой алгоритм вы сейчас используете, но я предложу простой. Признание того, что у вас есть массив с плавающей точкой f и максимум емкости номера, вы можете сделать следующее: 

int capacity = 4; // number of floats you want to retrieve
float [] f; // your float list
float [] max_so_far = new float[capacity]; // max so far

// say that the first 'capacity' elements are the biggest, for now
for (int i = 0; i < capacity; i++)
  max_so_far[i] = i;

// for each number not processed
for (int i = capacity; i < f.length; i++)
{
  // find out the smallest 'max so far' number
  int m = 0;
  for (int j = 0; j < capacity; j++)
    if (f[max_so_far[j]] < f[max_so_far[m]])
      m = j;

  // if our current number is bigger than the smallest stored, replace it
  if (f[i] > f[max_so_far[m]])
    max_so_far[m] = i;
}

К концу алгоритма у вас будут храниться индексы самых больших элементов в max_so_far .

Обратите внимание, что если значение acity будет расти, оно станет немного медленнее, чем альтернатива, которая сортирует список, отслеживая начальные позиции. Помните, что сортировка требует O (n log n) сравнений, в то время как этот алгоритм принимает O (n емкость).

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

Я нашел реализацию quick-select на c # здесь: текст ссылки

Плюсы:

  1. O (n + k) среднее время выполнения.

Минусы:

  1. Найденные k элементов не сортируются.Если вы отсортируете их, то время выполнения составит O (n + logk).
  2. Я не проверял это, но я думаю, что для очень маленького k лучшим вариантом является выполнение k пробегов по массиву, каждый раз находя следующий наименьший / наибольший элемент.
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top