Как найти несколько верхних значений из массива? - PullRequest
Новая
       23

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

2 голосов
/ 06 марта 2009

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

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

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

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

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

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

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

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

Ответы [ 4 ]

9 голосов
/ 06 марта 2009

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

Используйте кучу размера 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
2 голосов
/ 06 марта 2009

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

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.

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

2 голосов
/ 06 марта 2009

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

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

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

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

1 голос
/ 07 января 2010

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

Я нашел реализацию быстрого выбора c # здесь: текст ссылки

Плюсы:

  1. O (n + k) среднее время работы.

Минусы:

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