Помогите в написании алгоритма для генерирования отсортированного массива

Question

Например, два отсортированных массива

a = [1, 4, 5]
b = [3, 5, 7]

Необходимо выводить произведения a[i] * b[j]. В итоге должно получиться 3, 5, 7, 12, 15, 20, 25, 28, 35. Создать третий массив и в нем сортировать не подходит, так как массивы могут быть до 6000 элементов, а время не резиновое.

Answer 1

Сравним сортировку и порождение массива без сортировки.

Сортировка устроена так (вариант заимствован у extrn):

a = [1, 4, 5]
b = [3, 5, 7]
print(*sorted(itertools.starmap(operator.mul, itertools.product(a, b)))

3 5 7 12 15 20 25 28 35

Строится декартово произведение списков, которое превращается в произведения, которые сортируются.

Вариант без сортировки использует кучу:

a = [1, 4, 5]
b = [3, 5, 7]
seq = lambda f: (ai * f for ai in a)
print(*heapq.merge(*(seq(bi) for bi in b)))

3 5 7 12 15 20 25 28 35

Функция seq создаёт генераторы возрастающих последовательнотей, которые затем смешиваются в одну последовательность.

Сравним потребительские свойства обоих вариантов. Сортировка:

n = 6000
a = tuple(range(1, n + 1))
b = tuple(range(n + 1, 2 * n + 1))
print(sum(sorted(itertools.starmap(operator.mul, itertools.product(a, b)))))

972216009000000

Куча:

n = 6000
a = tuple(range(1, n + 1))
b = tuple(range(n + 1, 2 * n + 1))
seq = lambda f: (ai * f for ai in a)
print(sum(heapq.merge(*(seq(bi) for bi in b))))

972216009000000

На моём компьютере сортировка выполняется за 10.4с и потребляет 1.4Gb памяти. Куча работает 41.3с и требует 9.4Mb памяти. В четыре раза медленнее и в 140 (!) раз меньше памяти. В случае с сортировкой надо ждать пока будет создан и отсортирован массив целиком. Куча начинает выдавать элементы немедленно.

Если памяти хватает - сортируйте, если нет - можно разменять скорость на память.

Answer 2

Гм, поскольку о Python говорит только массив в квадратных скобках, а метки такой нет...

На С++ это отрабатывает достаточно быстро

int main(int argc, char * argv[])
{
    vector<int> v;
    v.reserve(36000000);
    for(int i = 1; i <= 6000; ++i)
        for(int j = 6001; j <= 12000; ++j)
            v.push_back(i*j);
    sort(v.begin(),v.end());
    long long s = 0;
    for(int x: v) s += x;
    cout << s;
}

Ну, а если sort(execution::par,v.begin(),v.end());, то, сами понимаете... :)

Answer 3

Если использовать библиотеку Numpy, то будет практически также быстро, как на C++, потому что внутри у этой библиотеки тоже C++:

%%time
import numpy as np
n = 6000
a = np.arange(1, n + 1)
b = np.arange(n + 1, 2 * n + 1)
c = np.multiply.outer(a, b).ravel()
c.sort(kind='stable')
print(c.sum())

Вывод:

972216009000000
CPU times: user 1.65 s, sys: 1.29 ms, total: 1.65 s
Wall time: 1.67 s

Да, в Numpy целые числа ограничены, в отличие от бесконечных целых самого питона, но в остальном Numpy ничем не хуже родного кода на C++, а то и лучше, потому что много готовых функций под самые разные задачи.

P.S. Если у кого-то будет переполнение, можно жёстко прописать побольше тип данных:

a = np.arange(1, n + 1, dtype=np.int64)
b = np.arange(n + 1, 2 * n + 1, dtype=np.int64)

БЛОГ НА HUSL

Помогите в написании алгоритма для генерирования отсортированного массива

Ответы (3 шт):