генерировать лучшие значения k

Question

У меня есть проблема, и я хочу убедиться, что я делаю это наиболее эффективно.У меня есть массив A значений с плавающей запятой размера N. Все значения находятся в диапазоне от 0 до 1.

Я должен найти верхние значения k, которые могут быть произведены максимум из трех чисел из A. Итак,список top-k может иметь отдельные числа от A, произведение двух чисел или произведение трех чисел от A.

Итак, вот как я это делаю сейчас.Я могу получить топ-k чисел в защищенном порядке за O (Nlogk) время.Затем я создаю максимальную кучу и инициализирую ее наилучшими значениями максимального размера 3, т. Е. Если я представляю отсортированный массив (по убыванию) значений k как B, а числа по его индексу в этом массиве, я вставляю числа, находящиеся по индексу (0), (0,1) и (0,1,2).Затем я выполняю извлечение в куче, и всякий раз, когда я извлекаю значение размера z (произведение чисел z), я заменяю его на набор следующих возможных чисел размера z, т.е. если предположить, что (2,4) извлечено, я могу заменить его на(3,4) и (2,5).И извлекайте k раз, чтобы получить результаты.

Нужны лучшие идеи, если у вас есть.Спасибо всем.

Answer 1

если я вас правильно понимаю, вам нужно найти k старших чисел, которые можно получить, умножив вместе 1, 2 или 3 элемента из вашего списка, и все значения будут числами с плавающей запятой от 0 до 1.

Понятно, что вам нужно только рассмотреть k старших чисел из списка.Остальные могут быть сброшены сразу.Вы можете использовать свой алгоритм O (n log k), чтобы получить их, снова в отсортированном порядке (я предполагаю, что ваш список не упорядочен).Чтобы упростить задачу, теперь вы можете взять их логарифмы и попытаться максимизировать суммы чисел вместо первоначальной задачи максимизации продуктов.Это может немного ускориться.

Теперь (учитывая логарифмическое представление) все ваши числа отрицательны, поэтому добавление большего количества из них просто создаст все больше и больше отрицательных чисел.

Давайте назовемk старших чисел А1 ... Ак.Теперь мы можем уменьшить проблему, предполагая, что существует также число A0, которое имеет значение 0 в лог-представлении и 1 в исходном представлении;тогда задача состоит в том, чтобы перечислить первые k 3-кортежей (x, y, z в {A0, ..., Ak}) с ограничением x ≥ y ≥ z и z

Мы используем максимальную кучу, как воригинальная формулировка;мы помещаем тройки в кучу, используя их суммы (S [...]) в качестве ключа заказа.Алгоритм начинается с нажатия [0,0,0] в кучу.Тогда:

answer = []
for m in 0 .. k:
  top = heap.pop()
  answer.append(sum(top))
  (i,j,n) = top # explode the tuple
  if (n < k - 1):
      heap.push((i,j,n+1))
  if (j == n):
      heap.push((i,j+1,j+1))
      if (i == j):
          heap.push((i+1,i+1,i+1))

В конце ответ содержит k + 1 элементов, первый из которых - [0,0,0], которые необходимо отбросить.

Пусть задано как-1, -3, -8, -9.Затем алгоритм работает следующим образом:

Heap
Top          Rest (shown in order)

[ 0, 0, 0] | 
[ 0, 0,-1] | [ 0,-1,-1] [-1,-1,-1]
[ 0,-1,-1] | [-1,-1,-1] [ 0,-1,-3] [ 0,-3,-3]
[-1,-1,-1] | [-1,-1,-2] [ 0,-1,-3] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3]
[-1,-1,-2] | [ 0,-1,-3] [-1,-1,-3] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3]
[ 0,-1,-3] | [-1,-1,-3] [ 0,-1,-4] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3]
[-1,-1,-3] | [ 0,-1,-4] [-1,-1,-4] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3]
[ 0,-1,-4] | [-1,-2,-2] [-1,-1,-4] [ 0,-1,-5] [-2,-2,-2] [ 0,-3,-3]
...
etc.

Приятной особенностью этого алгоритма является то, что он не перечисляет дубликаты и размер кучи равен O (k);чтобы понять почему, обратите внимание, что алгоритм добавляет на каждой итерации максимум элементов в куче (часто меньше), поэтому после k итераций в куче не может быть более 2k элементов.

Это дает тогда время выполненияO (n log k + k log k) = O ((n + k) log k).

Answer 2

Я определенно вижу оптимизацию, которую вы могли бы сделать.

Let M be the highest number from A.
Let M2 be M * M.
Let setMM2 consist of all x from A such that M2 < x < M
If size(setMM2) >= k, 
    then your top-k consist of the highest k elements.
Else
    all x in setMM2 are in your top-k and your search becomes smaller

Вы можете повторить этот метод с max (secondHighestNumber ^ 2, M ^ 3) и обобщить алгоритм.

Answer 3

kN Так как числа от 0 до 1, чем больше цифр вы используете, тем хуже будет проблема, и проблема с большим k, например, k = N ^ 2

Сначала попробуйте ввести одно число, а затем вставить в кучу,O (N * Log (k))

Чем использовать эти числа из кучи и создать еще одну кучу B с 2 числами в худшем случае => O (k * log (k)), но вы можете сделать некоторые ускорения, еслиВы сортируете числа в случае, когда k> N

И затем у вас есть куча с двумя числами и продуктами и попробуйте сделать третью кучу C из кучи B так же, как вы делали бы для B, но из гораздо большей кучи.

Я думаю, что это сделает O (k * log (k))