Как посчитать сумму позиций из 2-х источников?

Question

[lexstile]

Как найти общую сумму позиций?
Дано 2 массива, в одном лежит количество, во втором стоимость 1 позиции, их нужно перемножить. Связаны между собой по id.
Я могу сделать это через цикл в цикле, но хочется найти более элегантное решение.

$dishesRequest = collect([
            [
                'id' => 1,
                'quantity' => 4,
            ],
            [
                'id' => 2,
                'quantity' => 8,
            ],
        ]);

        $dishes = collect([
            [
                'id' => 1,
                'price' => 100,
            ],
            [
                'id' => 2,
                'price' => 200,
            ],
        ]);

* collect - коллекция из laravel.

Comments

[Дмитрий]

Зачем вам 2 цикла, если данные отсортированы и у нас есть 100 уверенность что каждому id в одном массиве есть соответствие в втором. Одним циклом идете и смещаете позицию для обоих массивов

[Дмитрий]

Ну и сильное подозрение что это надо делать в бд.

[Михаил Ливач]

у нас есть 100 уверенность

Это если она есть. А если нет? ( например: в первом случае возвращаются только элементы с quantity > 0 ).
Если нет - надо перевести данные в более удобную форму. Например, пройтись по второму массиву, построив производный массив, где ключи - это значения id. И вложенный цикл становится ненужным

[Дмитрий]

Михаил Ливач, а если нет надо добавить if. Алгоритм называется merge join и разбирается даже в википедии

[Михаил Ливач]

Дмитрий, merge join прекрасен на больших объемах (имхо, от десятков тысяч записей). А если это корзина в интернет магазине, то производный массив - более читабельное решение.
( даже интересно стало, какой вариант будет быстрее при реализации на PHP ...)

[Дмитрий]

Михаил Ливач, этот алгоритм прекрасен когда у нас оба массива отсортированы, какая разница какие обьемы? Вместо вложенных циклов - 1. O(n^2) и O(n)

Здесь я сортировку вижу - следовательно это первая мысль. Если ее нет - то стоит посмотреть в сторону hash join если массивы можно получить где id будет ключом - массивы в php это хеш таблицы и следовательно будет из коробки.

[Михаил Ливач]

Дмитрий,

какая разница какие обьемы?

Поймите, код пишется в основном для людей, и лишь в малом проценте случаев - для машин. Если n = 5 ( да даже 1000), то преимущество merge join в работе за один проход по сравнению с предложенным мной вариантом в 2 прохода не играет роли. O(n) + O(n) = O(n)

[Дмитрий]

Михаил Ливач, я прекрасно понимаю что такое поддержка проекта. И хорошо представляю что надо постараться что бы написать цикл с одним ифом так что бы он был не понятен, без вопросов возможно - но надо стараться. А учитывая что разговор идет о фреймоворке Laravel то я вообще добавлю это как метод класса Collection и будет что нибудь типа

$dishesRequest->mergeJoin('id', function($item1, $item2){ код мерджа}, $dishes);

Да и через array_walk это делается легко и понятно.

в 2 прохода не играет роли.

Угу. Это если у вас этот код выполняется раз в сутки. А если 100 раз в секунду это будет уже не так весело.

[Михаил Ливач]

А если 100 раз в секунду это будет уже не так весело

Зависит от n

[Дмитрий]

Михаил Ливач, ну если у нас в среднем товаров от двух и больше на n можно не надеятся.

Итого. Алгоритм мердж джоин сложности не представляет, работает он быстрее и без дополнительных трат в виде дополнительных массивов и прочего. Упование на то что кому то он может показаться сложным и кто то его не осилит - критики не выдерживает. Засим предлагаю закрыть тему

[lexstile]

Дмитрий,

Ну и сильное подозрение что это надо делать в бд.

Это добавление в БД - таблица order_dishe.
Первая коллекция приходит с фронта.
Вторая берется из БД - таблица dishes.

Мне нужно посчитать, а могу ли я создать заказ - не больше ли сумма предельно допустимой.

[lexstile]

Дмитрий,

Зачем вам 2 цикла, если данные отсортированы

Если whereIn сохраняет порядок при получении, то можно считать, что данные отсортированы, тогда я соглашусь, достаточно одного прохода.
Вход => выход:
[10, 5] => [['id' => 10, 'name' => 'Блюдо 10'], ['id' => 5, 'name' => 'Блюдо 5']]

[Дмитрий]

lexstile, нет конечно. Никакой in() порядок не сохраняет, для указания порядка используется order by. Все остальное будет возвращать так как бд удобнее. Однако что мешает запихнуть в order by сортировку на основе позиции в списке

[Дмитрий]

lexstile, бд какая?

[lexstile]

Дмитрий, MySQL БД.
Не знал, что можно сортировать точечно на основе идентификаторов.

[Дмитрий]

lexstile, версия?

ORDER BY FIND_IN_SET(id, '5,10')

[lexstile]

Дмитрий, я точно не помню сейчас, мажорная 8, а минорную надо смотреть.

[Дмитрий]

lexstile, ну смысл такой. в mysql 8, и postgres можно приджойнить значения. например для мускула

select 
         sum(dishes.price*prices.quantity) 
from 
         dishes 
join (VALUES ROW(5,100), ROW(10,600)) AS quantities(dishe_id, quantity) 
on quantities.dishe_id = dishes.id;

[Дмитрий]

lexstile, для mysql <8 вроде как тоже можно - но совсем костыльно.

[lexstile]

Дмитрий, правильно ли я понял, что я могу передать количество, которое приходит с фронта сразу в запрос, где MySQL сервер за меня все посчитает и вернет результат?

[Дмитрий]

lexstile, конечно. вы ж передаете уже id с фронта. В чем проблема к этому добавить цену? Пример запроса который приблизительно должен получиться я вам привел. Только придется потрахать мозги QueryBuilder'у и проверить не свихнется ли оптимизатор мускула.

[lexstile]

Дмитрий, спасибо большое за идеи и подсказки.

Answer 1

[Ипатьев]

В общем случае избежать "цикла в цикле" позволяет использование индексации массива идентификатором и - соответственно - обращение по индексу вместо перебора.
В данном случае вторую коллекцию проиндексировать можно с помощью метода keyBy('id');

И тогда останется только один цикл по первому массиву, в котором обращаться ко второму по id.
То есть сложность будет длина массива * 2 вместо длина массива * длина массива

Если же данные берутся из базы, то, как правильно заметили в комментариях, там же и надо сразу считать

spoiler

Типичный, кстати, вопрос из серии "Выучил ларавель, не выучил программировать"

Comments

[lexstile]

А разве keyBy под капотом не использует цикл?
Как я понимаю, все равно цикла будет 2, но мы просто скрываем логику - используем готовые инструменты.

И почему именно keyBy, а не тот же $dishesRequest->pluck('quantity', 'id')?

[Ипатьев]

Как я понимаю, все равно цикла будет 2

Неправильно понимаете
попробуйте вспомнить разницу между умножением и возведением в степень из начальной школы

И почему именно keyBy, а не тот же $dishesRequest->pluck('quantity', 'id')?

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

[lexstile]

Хотя я не вижу, как он тут поможет

output $dishesRequest->pluck('quantity', 'id'):

Illuminate\Support\Collection {#1468 // app\Rules\DishesRule.php:40
  #items: array:2 [
    11 => "2"
    12 => "3"
  ]
  #escapeWhenCastingToString: false
}

Где 11, 12 - id
А 2, 3 - quantity

[lexstile]

В данном случае вторую коллекцию проиндексировать можно с помощью метода keyBy('id');

И тогда останется только один цикл по первому массиву, в котором обращаться ко второму по id.

Почему-то я все равно 2 цикла насчитал, foreach внутри keyBy и обход основной коллекции...

[Ипатьев]

Очень хорошо. А теперь попробуйте вспомнить, с каким количеством циклов вы это сравниваете.

[lexstile]

Ипатьев, тоже с двумя.
1. Проходим тем же foreach и подготавливаем результаты.
2. Затем следующей операцией проходим по основному массиву и выцепляем нужные данные из индексированного.

Я понял, где мы разошлись. Я написал в посте - цикл в цикле, вы, скорей всего, про него имели ввиду.
Прошу прощения.

[Ипатьев]

все верно, я и исходил из формулировки цикл в цикле

pluck с индексацией в вашем случае сработает, это я проглядел.
keyBy просто более общее решение, индексирует весь массив, а не одну колонку.