3

Есть задача: имеется произвольное кол-во массивов цен (представленных BigDecimal) в кол-ве от 1 до 100. Цены во всех массивах отсортированы в порядке возрастания. Массивы могут содержать разное кол-во элементов, минимум 1, максимум 100. Каждый массив может содержать одинаковые цены. Необходимо получить итератор, который последовательно переберет декартово произведение всех этих массивов. При этом элементы декартового произведения (т.е. кортежи) должны перебираться в порядке не убывания сумм их элементов (если несколько кортежей имеют одинаковую сумму - их можно выдать в любом порядке).

Пример:

  1. Исходные массивы [1,2], [10,100], [10, 20].
  2. Итератор должен выдать следующую последовательность:
  • [1,10,10] | (сумма = 21) | кортеж индексов [0,0,0]
  • [2,10,10] | (сумма = 22) | кортеж индексов [1,0,0]
  • [1,10,20] | (сумма = 31) | кортеж индексов [0,0,1]
  • [2,10,20] | (сумма = 32) | кортеж индексов [1,0,1]
  • [1,100,10] | (сумма = 111) | кортеж индексов [0,1,0]
  • [2,100,10] | (сумма = 112) | кортеж индексов [1,1,0]
  • [1,100,20] | (сумма = 121) | кортеж индексов [0,1,1]
  • [2,100,20] | (сумма = 122) | кортеж индексов [1,1,1]

Как именно происходит обращение к результатам работы алгоритма:

Пользователь(не обязательно человек) запрашивает данные порциями в размере от 1_000 до 10_000 элементов. Между запросами интервал в 1-2 секунды. Пример, пользователь запрашивает сперва первые 10_000 элементов, потом спустя секунду - следующие после них 10_000 элементов и т.д.

Ограничения:

Время получения каждого следующего элемента последовательности не должно превышать 0.05 секунды, объем памяти используемый алгоритмом не должен превышать 20 мб.

Вот до чего я пока смог додуматься:

  1. Это задача связана с графами, скорее всего - с алгоритмом Дейкстры.
  2. Вершинами графа будут выступать кортежи индексов.
  3. Каждой вершине графа назначен вес равный сумме элементов массивов, на которые ссылается кортеж индексов представляющий эту вершину. Так первый индекс кортежа ссылается на элемент под этим индексом в первом массиве, второй индекс кортежа ссылается на элемент под этим индексом во втором массиве и т.д.
  4. Т.к. мы можем двигаться только к вершинам с большим или равным весом, то граф является ориентированным.
  5. Если хотя бы один индекс кортежа А меньше соответствующего индекса кортежа В, а остальные индексы попарно равны - то вес вершины А меньше или равен весу вершины В.
  6. Число смежных вершин каждой рассматриваемой вершины не превышает кол-во элементов кортежа представляющего данную вершину. Это обусловлено тем, что при поиске следующей вершины с большим весом относительно текущей - мы просматриваем те вершины, у которых один из индексов больше на единицу соответствующего индекса текущей вершины, а остальные индексы попарно равны.
  7. Исходя из пунктов 2 - 6 имеем область N-мерного пространства(где N - число массивов цен) ограниченную гиперкубом со сторонами равными размерам соответствующих массивов. Внутри этой области имеется ориентированный взвешенный граф вершинами которого выступают все точки этой области имеющие целочисленные координаты. Каждой вершине назначен вес (как описано в пункте 3).

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

16
  • 1
    Генерация всех кортежей из тома 4а "Искусства программирования" Кнута. Это если без упорядочения по сумме. Если с упорядочением - ну, тут в общем случае задача посложнее. Разве что - сгенерировать все и отсортировать?... Графы тут вроде как в полной мере ни при чем.
    – Harry
    2 мая 2021 в 8:20
  • "Разве что - сгенерировать все и отсортировать?" - @Harry, на вход может запросто может прийти 10 массивов по 10 элементов, а может и больше. Вариант "все сгенерировать" отпадает, т.к. банально не хватит оперативной памяти + дико долго.
    – Bakuard
    2 мая 2021 в 9:13
  • @Stanislav Volodarskiy - 10 массивов по 10 элементов, а может и больше. P.s. добавил метку для языка.
    – Bakuard
    2 мая 2021 в 9:14
  • 1
    stackoverflow.com/questions/49417578 - вы смотрели этот вопрос? Кажется, в качестве ответа там предложено как раз то, о чем вы говорите, но в убывающем порядке, а не в возрастающем.
    – EzikBro
    2 мая 2021 в 12:53
  • 1
    По ссылке я увидел Дейкстру на прямоугольной решетке. Размер очереди ограничен призведением длин массивов делённым на на размер самого длинного из массива. Это легко доказать, но поля этой книги маловаты. 2 мая 2021 в 16:24

2 ответа 2

4
+50

Какая-то у вас невозможная задача.

Я решал алгоритмом обхода в ширину.

Среднее время поиска следующего кортежа в оптимизированной версии 2-3 микросекунды, максимальное число вершин в очереди порядка 10-20% от общего числа кортежей.

Из статистических соображений я сделал оценку для числа вершин в очереди как t_{max} = \large\frac{2m^{n-1}}{\sqrt{\pi/6}} (вывод во второй половине ответа).

Для случая 10 множеств по 5 элементов :

Initial memory: 1553968
Chunk 1, max queue size: 994658, average queue size: 594489.313674, number of tuples: 1000000, time per tuple (us): 3.978, memory footprint 378.535936
Chunk 2, max queue size: 1452588, average queue size: 1246088.370882, number of tuples: 2000000, time per tuple (us): 3.8685, memory footprint 514.328576
Chunk 3, max queue size: 1695265, average queue size: 1588153.053864, number of tuples: 3000000, time per tuple (us): 3.7563333333333335, memory footprint 746.061824
Chunk 4, max queue size: 1787139, average queue size: 1752202.050448, number of tuples: 4000000, time per tuple (us): 3.65425, memory footprint 789.055488
Chunk 5, max queue size: 1790000, average queue size: 1780446.911269, number of tuples: 5000000, time per tuple (us): 3.554, memory footprint 1121.452032
Chunk 6, max queue size: 1790000, average queue size: 1692331.183893, number of tuples: 6000000, time per tuple (us): 3.476166666666667, memory footprint 1350.043648
Chunk 7, max queue size: 1790000, average queue size: 1496542.423178, number of tuples: 7000000, time per tuple (us): 3.3787142857142856, memory footprint 1477.967872
Chunk 8, max queue size: 1790000, average queue size: 1193571.100488, number of tuples: 8000000, time per tuple (us): 3.275625, memory footprint 1526.204416
Chunk 9, max queue size: 1790000, average queue size: 772911.238497, number of tuples: 9000000, time per tuple (us): 3.1741111111111113, memory footprint 1481.637888
Max queue size: 1790000(18.3296)%, number of tuples: 9765625, time per tuple (us): 3.116032, max mem (mb): 959.973376
Max tuples: 18.3296%, predicted: 17.480774889473263%

Java разбухает почти до полутора гигабайтов, в очереди в пике 1.8 миллиона вершин, в среднем по миллиону вершин. О 20 мегабайтах остаётся только мечтать. Вы точно уверены, что у вас нет ограничений на число множеств?

Сумма элементов, соответствующих конечной вершине дуги, задаёт вес дуги. Граф ориентированный, в нём есть одна минимальная вершина [0,...,0] и одна максимальная вершина [s1, s2, ..., s_n], где s_i - размер i-го множества.

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

Размер данных для хранения одной вершины у меня 4*n+8 байт. По 4 байта на каждый индекс плюс 8 байт на double, в котором хранится сумма. Плюс накладные на хранение сортированного списка в дереве.

Прогон на вашем примере:

1: sum: 21, row:[1, 10, 10]
2: sum: 22, row:[2, 10, 10]
3: sum: 31, row:[1, 10, 20]
4: sum: 32, row:[2, 10, 20]
5: sum: 111, row:[1, 100, 10]
6: sum: 112, row:[2, 100, 10]
7: sum: 121, row:[1, 100, 20]
8: sum: 122, row:[2, 100, 20]

Прогон на трёх индентичных множествах {0,1,2}:

1: sum: 0, row:[0, 0, 0]
2: sum: 1, row:[0, 0, 1]
3: sum: 1, row:[0, 1, 0]
4: sum: 1, row:[1, 0, 0]
5: sum: 2, row:[1, 1, 0]
6: sum: 2, row:[0, 2, 0]
7: sum: 2, row:[2, 0, 0]
8: sum: 2, row:[0, 0, 2]
9: sum: 2, row:[0, 1, 1]
10: sum: 2, row:[1, 0, 1]
11: sum: 3, row:[2, 0, 1]
12: sum: 3, row:[0, 1, 2]
13: sum: 3, row:[1, 0, 2]
14: sum: 3, row:[1, 1, 1]
15: sum: 3, row:[0, 2, 1]
16: sum: 3, row:[1, 2, 0]
17: sum: 3, row:[2, 1, 0]
18: sum: 4, row:[1, 2, 1]
19: sum: 4, row:[2, 2, 0]
20: sum: 4, row:[0, 2, 2]
21: sum: 4, row:[1, 1, 2]
22: sum: 4, row:[2, 0, 2]
23: sum: 4, row:[2, 1, 1]
24: sum: 5, row:[2, 1, 2]
25: sum: 5, row:[1, 2, 2]
26: sum: 5, row:[2, 2, 1]
27: sum: 6, row:[2, 2, 2]

Сначала я сделал как написано, на BigDecimal. Потом переделал на double и заменил очередь на TreeSet. Время счёта уменьшилось в 10 раз. Оптимизированная версия лежит здесь.

Но даже в оптимизированной никаких 20 мегабайтов.

UPDATE

К вопросу о размере фронта обхода. Фронт составляют узлы с близкими значениями суммы.

Пример - 7x7, семь множеств по семь элементов. Число кортежей 823543, максимальное число вершин в фронте 131285 или 15.9% от общего числа кортежей.

Вот график роста суммы значения кортежа и частотное распределение суммы.

сумма кортежей

Оранжевая линия - нормальное распределение. Прерывистые линии показывают область кортежей, "близких" к центру распределения. Ниже я объясню, что такое "близкие"

Пусть M - верхняя граница чисел в упорядоченном множестве (в вашем примере 100), а m - число элементов в множестве (в моём примере m == 7). Тогда среднее расстояние между точками в множествах равно w = M/m. Когда индекс в кортеже увеличивается на 1, сумма в среднем увеличивается на w. Такие кортежи я назвал "близкими"

Если бы мы были физиками, то мы могли бы сразу сказать, что в фронте обхода находятся кортежи, отстоящие друг от друга на ±w. Поэтому физики оценили бы максимальное значание кортежей в фронте как число сумм в полосе шириной 2w вокруг максимума распределения: d = max(p)*2w.

По центральной предельной теореме распределение сумма n случайных величин стремится к нормальному распределению. Среднеквадратичное отклононение этого распределения равно Sigma_sum = Sigma_M*sqrt(n), где Sigma_M - среднеквадратичное отклонение отдельной случайной величины.

Итак, будь мы физиками, написали бы d = 2w/(Sigma_sum*sqrt(2pi))

Если отдельные множества рассматривать как равномерно распределенные от 0 до M, то Sigma_M = M/sqrt(12).

Сводя всё вместе: d = 2/(m*sqrt(n)*sqrt(pi/6)), а оценка максимального числа вершин в фронте волны t_max = d*(m**n) = 2(m**n)/(m*sqrt(n)*sqrt(pi/6))

В моём примере семи множеств оценка d = 0.148. В эксперименте же число вершин в фроне волны было 15.9%. Хорошее совпадение эксперимента и модели. Физики молодцы :)

Модель предсказывает экспоненциальный рост фронта по мере роста n: O(m**(n-1)).

11
  • Честно говоря, я отчаяно надеялся, что из факта отсортированости исходных массивов удастся вывести (математически) какое-то свойство, которое могло бы минимизировать размер фронта алгоритма обхода итогового графа.
    – Bakuard
    14 мая 2021 в 16:41
  • Это сделано в моём ответе (N / n_k). 14 мая 2021 в 17:27
  • @Bakuard фронт формируют узлы с близкими значениями суммы. В силу центральной предельной теоремы сумма N случайных величин стремится к нормальному распределению, причём чем больше N, тем круче "колокол". То есть большая часть кортежей "кучкуются" вокруг среднего значения суммы. Из-за этого в середине счёта накапливается большое число "кандидатов" на обработку.
    – Pak Uula
    14 мая 2021 в 21:55
  • @StanislavVolodarskiy, меня смущает ваша формула. Почему в ней именно n_k? Почему не n_1? Казалось бы, достаточно переставить к-е множество и первое - общее число кортежей не изменится, а N изменится. Как так?
    – Pak Uula
    14 мая 2021 в 21:56
  • Формула не для графа, а для его остовного дерева. А остовное дерево устанавливает порядок на размерностях. Все листья в дереве на последней размерности. 14 мая 2021 в 22:21
2

Наиболее прямолинейное решение задачи состоит в сортировке всех кортежей. Хранение всех кортежей в памяти требует много памяти. Предварительная сортировка требует времени, которое должно быть потрачено до выдачи первого кортежа. Остальные кортежи выдаются быстро, так как уже хранятся в нужном порядке.

Везде ниже индексация ведется от нуля.

Упаковка кортежей

Для экономии памяти кортежи можно хранить в виде порядковых номеров. Пусть N = n_0 * n_1 * ... * n_k-1 - общее число кортежей и размерности нашего декартого произведения. Кортежу (i_0, i_1, ..., i_k-2, i_k-1) сопоставляется его номер i_0 + n_0 * (i_1 + n_1 * (... (i_k-2 + n_k-2 * i_k-1)...)). Номера лежат в интервале [0...N).

По номеру кортежа можно восстановить сам кортеж. Таким образом мы можем сортировать номера кортежей в соответствии с суммами которые они представляют.

В случае Java это помогает уменьшить требования к памяти в несколько раз: мы заменяем int[k] (или byte[k] - не влияет существенно) на int или long. Массивы в Java - это объекты, которые должны быть выделены в куче, индексы - примитивные типы, которые не требуют дополнительных аллокаций.

Если N < 2^31, то в качестве индекса можно использовать int. 2^31 <= N < 2**53 - long.

Переход от кортежа к его номеру замедляет работу с ним. Сортировка производит множество сравнений элементов, значения элементов не хранятся из-за требований по памяти. Компромиса можно достичь используя небольшой кеш для значений кортежей.

Поиск в графе

Предварительная сортировка тратит много времени до выдачи первого элемента. От сортировки можно избавиться.

Кортежи соберём в граф - (гипер)кубическую решетку. Для обхода графа используем алгоритм Дейкстры. У нас нет весов ребер, а есть веса вершин, по которым веса ребер можно восстановить. В этой модификации Дейкстра решит задачу без предварительной сортировки. Кроме того фронт в алгоритме Дейкстры может оказаться гораздо меньше общего числа вершин в графе - экономия памяти.

Сделаем граф направленым. Из кортежа выходит не более k ребер в соседние кортежи с большими индексами:

(i_0, i_1, ..., i_k-1) -> (i_0 + 1, i_1    , ..., i_k-1    )
(i_0, i_1, ..., i_k-1) -> (i_0    , i_1 + 1, ..., i_k-1    )
...
(i_0, i_1, ..., i_k-1) -> (i_0    , i_1    , ..., i_k-1 + 1)

В такой модификации вес любого пути из кортежа p_1 в p_2 равен w(p_2) - w(p_1) - где w - функция веса кортежа. Получившийся граф не имеет циклов.

Превратим граф в дерево. i_j - последний не нулевой индекс в кортеже, тогда единички можно прибавлять к нему и ко всем нулям после него:

(i_0, i_1, ..., i_j, 0, 0, ..., 0) -> (i_0, i_1, ..., i_j + 1, 0, 0, ..., 0)
(i_0, i_1, ..., i_j, 0, 0, ..., 0) -> (i_0, i_1, ..., i_j    , 1, 0, ..., 0)
(i_0, i_1, ..., i_j, 0, 0, ..., 0) -> (i_0, i_1, ..., i_j    , 0, 1, ..., 0)
...
(i_0, i_1, ..., i_j, 0, 0, ..., 0) -> (i_0, i_1, ..., i_j    , 0, 0, ..., 1)

В такой схеме любой кортеж достижим по единственному пути из кортежа (0, ..., 0). Следовательно новый граф - дерево.

Дерево поиска

Алгоритм Дейкстры на дереве сводится к поиску в дереве. Если в поиске в ширину обычную очередь заменить на очередь приоритетов, то такой поиск будет выдавать узлы в том же порядке что и Дейкстра. В отличие от Дейкстры теперь не нужно хранить множество посещённых узлов. Так же можно оценить максимальный размер очереди приоритетов.

Размер очереди приоритетов для поиска в дереве

В очереди приоритетов для дерева не может быть пар предок-потомок. Это доказывается по индукции. База очевидна - один узел в очереди. Индукционный переход: предположим что пока пар предок-потомок нет. Модифицируем очередь: удаляется узел, вставляются все его дети. Между собой дети образовать пару предок-потомок не могут. Предположим какой ребенок образовал пару предок-потомок с третьим узлом. Разбирая варианты можно показать что тогда удалённый родитель также образовывал пару предок-потомок с этим третьим узлом. Противоречие в индукционным предположением. Доказано.

Если пар предок-потомок в очереди нет, то размер очереди не может быть больше числа листьев в дереве. Доказывается по индукции по числу узлов в дереве. База - один узел в дереве - очевидна. Индукционные переход: пусть утверждение верно для всех деревьев с не более чем t узлов. Рассмотрим дерево с t + 1 узлом. Оно состоит из корня и поддеревьев. Для поддеревьев утверждение верно. Если сложить неравенства для поддеревьев, получим неравенство для дерева. Единственный неучтённый узел - корень. Но если он в очереди, то больше в очереди никого нет из-за запрета "предок-потомок". Доказано.

Сколько листьев в дереве кортежей? Листом является кортеж у которого в последней позиции n_k-1 - 1. Из такого кортежа нет выходящих ребер. Таких кортежей N / n_k-1 что и даёт оценку сверху на размер очереди приоритетов.

Ограничение в 20MB

Это очень жёсткое требование. Почти всю память расходует очередь. Какие могут быть ограничения на входные данные, так чтобы очередь уложилась в 20 MB?

Для иллюстрации будем считать что все массивы одинаковой длины, для индексов используется тип int:

число массивов   длина массива   длина очереди   размер очереди в байтах
        1              2^31               1                 4
        2           5242880         5242880          20971520 (=20MB)
        3              2289         5239521          20958084
        4               173         5177717          20710868
        5                47         4879681          19518724
        6                22         5153632          20614528
        7                13         4826809          19307236
        8                 9         4782969          19131876
        9                 6         1679616           6718464
       10                 5         1953125           7812500
       11                 4         1048576           4194304
       12                 4         4194304          16777216
       13                 3          531441           2125764
       14                 3         1594323           6377292
       15                 3         4782969          19131876
       16                 2           32768            131072
...
       23                 2         4194304          16777216

Кроме очереди память нужна для кеша значений. BigDecimal лучше заменить на double или long. В задаче речь идёт о ценах, следовательно их можно отмасштабировать в целые или вещественные числа без потери точности. Выигрыш в памяти и скорости будет существенным.

Эксперимент с десятью массивами по пять элементов требует не более 25MB. Значения хранятся как long, индексы тоже long.

Реализация

Код можно найти в этом репозитории.

Класс Driver отвечает за тестирование алгоритмов. makefile содержит примеры командных строк.

SortedArrayList - выполняет предварительную сортировку кортежей.

CompactSortedArrayList - предварительная сортировка номеров кортежей.

CompactPriorityQueue - поиск в дереве с приоритетами. Приоритеты вычисляются по номерам кортежей. Размер очереди установлен N / n_k-1.

Последний вариант на моей машине обрабатывает N = 10^10, N / n_k-1 = 10^9. Память < 8.5GB. 200-400 тысяч кортежей в секунду. Вся обработка длится менее шести часов.

3
  • 1
    Я поэкспериментировал с вашим кодом. В вашем алгоритме число узлов в очереди в два раза меньше, чем у меня в обходе в ширину, и хорошо согласуется с формулой, выведенной из нормального распределения. Для n множеств по m элементов ваш алгоритм даёт максимальный размер очереди близко к 1.0/(m*sqrt(n)*sqrt(Math.PI/6)). Пример для m==7. Первое значение экспериментальное, второе по формуле: 4: 9.1% vs 9.9%, 5: 8.1% vs 8.8%, 6: 8.2% vs 8.1%, 7: 7.9% vs 7.5%, 8: 8.1% vs 7.0, 9: 7.4% vs 6.1%.
    – Pak Uula
    15 мая 2021 в 14:16
  • Проблема моей реализации в том что ради экономии памяти я не использую контейнеры с динамическим размером. Следовательно не могу использовать вероятностные оценки длины очереди, только точные. :( 15 мая 2021 в 14:21
  • Чтобы сократить размер очереди примерно в k раз вам достаточно уменьшить число исходящих ребер тут: addKids. 15 мая 2021 в 14:25

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.