Возьмите первые 10 продуктов из двух отсортированных массивов с наименьшей суммой - PullRequest
Новая
       26

Возьмите первые 10 продуктов из двух отсортированных массивов с наименьшей суммой

1 голос
/ 23 октября 2019

Не удалось найти название этой проблемы в Google, надеюсь, этот вопрос поможет сообществу.

Предположим, у нас есть два отсортированных массива чисел, например: 

 2  8
12 18
45 35
85 48
87 49
97 59

И мыхотите эффективно взять сначала k (10) комбинаций чисел с наименьшей суммой из обоих массивов. В нашем случае это будет: 

 2 +  8 = 10 
 2 + 18 = 20
12 +  8 = 20
12 + 18 = 30
 2 + 35 = 37
12 + 35 = 47
 2 + 48 = 50
 2 + 49 = 51
45 +  8 = 53
12 + 48 = 60

Каков будет правильный подход? Я поцарапал наивную реализацию (улучшенную @sanyash), но она не использует тот факт, что массивы отсортированы и проблема кажется выполнимой за линейное время ... 

def smallest_product(k, arr1, arr2):
    product_iter = itertools.product(
        itertools.islice(arr1, k),
        itertools.islice(arr2, k),
    )
    product_sorted = sorted(product_iter, key=sum)
    product_sliced = itertools.islice(product_sorted, k);
    return list(product_sliced)

print(smallest_product(10, 
    [ 2, 12, 45, 85, 87, 98], 
    [ 8, 18, 35, 48, 49, 59]))

Аналогичный вопрос: эффективное отсортированное декартово произведение двух отсортированных массивов целых чисел (но оно имеет дело с созданием полного результирующего массива, тогда как в моем случае мне нужны только первые несколько значений)

PS Я добавил python пометьте это как математическую задачу, но я буду рад решению на любом языке или просто объяснению, или ссылке на википедию ...

Ответы [ 4 ]

2 голосов
/ 23 октября 2019

Представьте, что мы создаем таблицу с использованием наших двух массивов: 

for arr in [[i + j for j in arr2] for i in arr1]: print(arr)

Мы получаем вывод, подобный этому: 

[10, 20, 37, 50, 51, 61]
[20, 30, 47, 60, 61, 71]
[53, 63, 80, 93, 94, 104]
[93, 103, 120, 133, 134, 144]
[95, 105, 122, 135, 136, 146]
[106, 116, 133, 146, 147, 157]

Обратите внимание, что в этой матрице matrix[i][j] == arr1[i] + arr2[j]. Таким образом, мы можем вычислить значение элемента в любой позиции матрицы в O(1). Обратите внимание, что это отсортированная матрица , где все строки и столбцы монотонно растут, и мы пытаемся найти самые маленькие элементы k внутри нее.

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

Это не в полной мере относится к ситуации, однако существуют варианты поиска в седле, которые позволяют найти kth наименьший элемент в отсортированной матрице в O(N) вместо O(KlogN), как в случае сподход выше. Вероятно, есть способ изменить подход, принятый в этой статье , до O(K), но в этой ситуации он, скорее всего, излишним.

2 голосов
/ 23 октября 2019

Вы можете использовать кучу: 

import heapq


def smallest_product(k, a, b):
    k = min(k, len(a) * len(b))
    l = [(a[0] + b[0], 0, 0)]
    heapq.heapify(l)

    seen = set()
    for _ in range(k):
        s, i, j = heapq.heappop(l)

        if i + 1 < len(a) and (i + 1, j) not in seen:
            heapq.heappush(l, (a[i + 1] + b[j], i + 1, j))
            seen.add((i + 1, j))
        if j + 1 < len(b) and (i, j + 1) not in seen:
            heapq.heappush(l, (a[i] + b[j + 1], i, j + 1))
            seen.add((i, j + 1))
        yield (a[i], b[j])

result = list(smallest_product(10, [ 2, 12, 45, 85, 87, 98], [ 8, 18, 35, 48, 49, 59]))

print(result)

Вывод 

[(2, 8), (2, 18), (12, 8), (12, 18), (2, 35), (12, 35), (2, 48), (2, 49), (45, 8), (12, 48)]

Приведенный выше код является переводом Python с кода в здесь . Этот метод имеет временную сложность O(k*log k).

Выход (Для k = 11) 

[(2, 8), (2, 18), (12, 8), (12, 18), (2, 35), (12, 35), (2, 48), (2, 49), (45, 8), (12, 48), (2, 59)]
0 голосов
/ 24 октября 2019

Эту проблему можно решить за три шага.

  1. Построить список длины-m итерируемых отсортированных пар, где m = min(len(list1), k);
  2. Применить m путь слияния (подробнее см. this ) в итерации для получения одной итерируемой отсортированной пары с использованием суммы каждой пары в качестве ключа;
  3. Takeпервые k элементы из итерируемого.

Существуют разные алгоритмы слияния m. Ниже приводится реализация на основе кучи. Сложность O (k * logm). 

from itertools import islice
from heapq import merge

def smallest_pairs(k, list1, list2):
    pairs = map(lambda x:((x, y) for y in list2), islice(list1, k))
    return list(islice(merge(*pairs, key=sum), k))

print(smallest_pairs(10, 
      [ 2, 12, 45, 85, 87, 98],
      [ 8, 18, 35, 48, 49, 59]))
0 голосов
/ 23 октября 2019

Сначала обрежьте оба массива до len k. После этого используйте вашу предыдущую реализацию. Это будет сложность O (k ^ 2): 

import itertools

def smallest_product(k, arr1, arr2):
    product_iter = itertools.product(
        itertools.islice(arr1, k),
        itertools.islice(arr2, k),
    )
    product_sorted = sorted(product_iter, key=sum)[:k]
    return list(product_sorted)


print(smallest_product(
    10, 
    [ 2, 12, 45, 85, 87, 98], 
    [ 8, 18, 35, 48, 49, 59])
)
...