Страницы: 1
RSS
Расчёт числа параллельных процессов
 
Всем привет!
Задача - провести 50 тестов, каждый из которых занимает на 100 МБ больше памяти, чем предыдущий.
То есть тест 1 - 500 МБ, 2 - 600 МБ, 3 - 700 МБ, ..., 50 - 5400 МБ. Всего памяти - 5500 МБ.
По логике вначале можно запустить 6 тестов параллельно (суммарно 4500 МБ).
Далее 4(5000)--3(4800)--2(3700)--2(4100)--2(4500)--2(4900)--2(5300) и ещё 27 тестов по одиночке (2800-5400).
Вопрос - формула/UDF, позволяющая рассчитать число тестов, которое я могу запустить параллельно
и расходуемую при этом память?
Изменено: Acid Burn - 08.09.2019 13:42:32
 
Доброе время суток
Цитата
Acid Burn написал:
По логике вначале можно запустить 6 тестов
Цель то какая? Если минимизировать число тестов, то повторить арифметические прогрессии, особенно ту легенду про суммирование чисел от 1 до 100 :)
Подсказка минимум 25 тестов
 
Андрей VG, да, цель  - минимизировать число тестов (этапов). Но как Вы получили 25?
Если же легко можно рассчитать 25, то хорошо бы получить 2 функции:
1) первая выдаёт число этапов: 25;
2) вторая выдаёт имена групп тестов, которые можно запустить параллельно на данном этапе.
Т.е. я вижу, что всего 25 этапов, затем вручную ввожу цифры от 1 до 25 и в соседней ячейке получаю ответ:
н-р, ввожу 1 - получаю 500m 600m 700m 800m 900m 1000m; ввожу 2 - получаю 1100m 1200m 1300m 1400m.

Вы про вот эту формулу говорили?
Изменено: Acid Burn - 08.09.2019 14:04:29
 
Приношу свои извинения - лопухнулся без расчёта на бумажке :(  Вот такие соображения - будет 27 тестов
 
Андрей VG, а как получить это же решение, оперируя переменными startRam, endRam и stepRam из моего файла?
Ну и соответственно вывести имена (условно - ID) тестов для каждого из 27 этапов/шагов?
Что-то похожее нашёл тут, но никак не соображу...

Число тестов: TestCount = (endRAM-startRAM)/stepRAM+1 = (5400-500)/100+1 = 50
Расход памяти: TestRAM = (endRAM+startRAM)/2*TestCount = (5400+500)/2*50 = 147500
Число этапов: StageCount = TestRAM/endRAM = 147500/5400 = 27

Далее Вы комбинировали процессы: 23+24, 22+25, ..., 1+46, с 47 по 50 - поодиночке. Границей стал тест 46 (5000 Мб):
limRAM = endRAM-startRAM+stepRAM = 5400-500+100 = 5000; limProc = (limRAM-startRAM)/stepRAM+1=(5000-500)/100+1 = 46.
Далее строим последовательность startRAM+(StageNum-1)*stepRAM & startRAM+(limProc - StageNum)*stepRAM.

этап №01: 500+(1-1)*100 & 500+(46-1)*100 = 500 & 5000;
этап №46: 500+(46-1)*100 & 500+(46-46)*100 = 5000 & 500
этап №47: 500+(47-1)*100 & 500+(46-47)*100 = 5100 & 400 - 400<startRAM, оставляем только процесс 5100.

Проверить пока не могу - свет отключили. Что-то типа того?
Изменено: Acid Burn - 08.09.2019 16:14:54
 
Ну вот, получился вот такой файл.
А что, если у меня было бы 16 Гб RAM? Тогда процессы можно комбинировать как-то иначе.
Только как?
Изменено: Acid Burn - 08.09.2019 18:40:27
 
Цитата
Acid Burn написал:
А что, если у меня было бы 16 Гб RAM?
Тогда будет не частный случай оптимизационных задач, условно называемых задачей о рюкзаке.  Надеюсь Михаил MCH меня поправит, если не прав. Но, учитывая, что такой класс задач NP полный, то обычно не мучаются, а пользуются жадным алгоритмом - он не оптимальный, но зато самый быстрый. В этом случае вам нужно уходить от функций (путь даже и udf), а переходить к макросам. Суть алгоритма проста:
1. упорядочиваем данные не по возрастанию
2. подбираем первое по порядку, которое можно разместить в рюкзаке, исключаем найденное.
3. для оставшегося места подбираем аналогично 2.
4. если уже ничего не лезет - считаем рюкзак заполненным
5. переходим к новому рюкзаку того же размера и в 2
6. 2-5 выполняем пока не кончатся предметы.
 
Андрей VG, логика понятна, но такое написать мне не по зубам.
Upd: Попробовал - точно не смогу. Что-то весьма похожее нашёл тут и тут.

Друзья, помогите кто-нибудь!
Изменено: Acid Burn - 08.09.2019 21:13:08
 
Нашёл подходящий файл.
Если задать 50 чисел (от 5400 до 500 с шагом 100) и размер выборки от 1 до 4,
то метод "Ограниченный перебор" выдаёт
- при кол-ве RAM ("желаемая сумма") = 5500 - 426 вариантов (достаточно 27-ми),
- при кол-ве RAM ("желаемая сумма") = 15400 - 1527 вариантов
Остальные варианты не так работают.
Кто сможет доработать?
 
"Жадный алгоритм" формулами:
Код
=МАКС(($J$41-СУММ(L$37:L37)>=$C$2:$C$51)*(СЧЁТЕСЛИ($K$38:K$49;$C$2:$C$51)+СЧЁТЕСЛИ(L$37:L37;$C$2:$C$51)=0)*$C$2:$C$51)
Думаю над формулой, которая два последних значения будет подбирать для точного равенства.
 
Светлый, проверил со значениями 5500, 15000 и 31000 - вроде все цифры "на месте"!
Хотя при значении 31000 6 этап можно "уместить" в 5-ом.
А так очень круто! Спасибо!

Итого вариант, который я хотел проверить, полностью работает.
Но Андрей VG прав - для ситуации, когда startRam/endRam/stepRam/maxRAM полностью динамические, макрос удобнее.
Может MCH (Михаил Ч.) или кто-то из Гуру откликнется, потому что я такой макрос не потяну. )

Ну а сейчас всем спокойной ночи! До связи!
Изменено: Acid Burn - 09.09.2019 00:27:08
 
Цитата
Светлый написал:
которая два последних значения будет подбирать для точного равенства
Придумал. Неоптимизированная:
Код
=ЕСЛИ($J$41-СУММ(L$56:L56);ЕСЛИ(МАКС(($J$41-СУММ(L$56:L56)=(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*ТРАНСП(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$52)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$52)=0)*($C$2:$C$51+ТРАНСП($C$2:$C$52)))*$C$2:$C$51)>0;МАКС(($J$41-СУММ(L$56:L56)=(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*ТРАНСП(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$52)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$52)=0)*($C$2:$C$51+ТРАНСП($C$2:$C$52)))*$C$2:$C$51);МАКС(($J$41-СУММ(L$56:L56)>=$C$2:$C$51)*(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*$C$2:$C$51));"")

Цитата
Acid Burn написал:
6 этап можно "уместить" в 5-ом
Не хватало строк. Увеличил.
*Формулу немного переделал:
Код
=ЕСЛИ($J$41-СУММ(L$56:L56);ОСТАТ(МАКС(($J$41-СУММ(L$56:L56)=(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*ТРАНСП(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*($C$2:$C$51+ТРАНСП($C$2:$C$51)))*($C$2:$C$51+10^8);($J$41-СУММ(L$56:L56)>=$C$2:$C$51)*(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*$C$2:$C$51);10^8);"")

**Исправил недоработку:
Код
=ЕСЛИ($J$41-СУММ(L$56:L56);ОСТАТ(МАКС(($J$41-СУММ(L$56:L56)=(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*(СТРОКА($2:$51)<>ТРАНСП(СТРОКА($2:$51)))*ТРАНСП(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*($C$2:$C$51+ТРАНСП($C$2:$C$51)))*($C$2:$C$51+10^8);($J$41-СУММ(L$56:L56)>=$C$2:$C$51)*(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$51)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$51)=0)*$C$2:$C$51);10^8);"")

***Ещё улучшил:

Код
=ЕСЛИ($J$41-СУММ(L$56:L56);ОСТАТ(МАКС(($J$41-СУММ(L$56:L56)=(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$52)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$52)=0)*(СТРОКА($2:$52)<>ТРАНСП(СТРОКА($2:$52)))*ТРАНСП(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$52)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$52)=0)*($C$2:$C$52+ТРАНСП($C$2:$C$52)))*($C$2:$C$52+10^8);($J$41-СУММ(L$56:L56)>=$C$2:$C$52)*(СЧЁТЕСЛИ($K$57:K$73;$C$2:$C$52)+СЧЁТЕСЛИ(L$56:L56;$C$2:$C$52)=0)*$C$2:$C$52);10^8);"")
Изменено: Светлый - 09.09.2019 08:27:21
 
Светлый, круто! Спасибо. Иногда работа формулистов завораживает :)
 
Светлый, а на таком наборе входных данных - формульное решение возможно?
 
Цитата
Андрей VG написал:
формульное решение возможно?
А то! Лишь бы все значения были разные.
*Немного красоты навёл:
Код
=ЕСЛИ($D$1>СУММ(F$3:F3)+МИН($B$4:$B$104);--ПРАВБ(МАКС(($D$1-СУММ(F$3:F3)=(СЧЁТЕСЛИ($E$4:E$40;$B$4:$B$104)+СЧЁТЕСЛИ(F$3:F3;$B$4:$B$104)=0)*(СТРОКА($4:$104)<>ТРАНСП(СТРОКА($4:$104)))*ТРАНСП(СЧЁТЕСЛИ($E$4:E$40;$B$4:$B$104)+СЧЁТЕСЛИ(F$3:F3;$B$4:$B$104)=0)*($B$4:$B$104+ТРАНСП($B$4:$B$104)))*($B$4:$B$104+10^8);($D$1-СУММ(F$3:F3)>=$B$4:$B$104)*(СЧЁТЕСЛИ($E$4:E$40;$B$4:$B$104)+СЧЁТЕСЛИ(F$3:F3;$B$4:$B$104)=0)*$B$4:$B$104);8);"")
Изменено: Светлый - 09.09.2019 10:46:58
 
Светлый, просто отлично! Спасибо огромное!
Ввёл динамические диапазоны - формула нагляднее и данные можно добавлять, не растягивая формулы.
Есть 2 вопроса:
- Как рассчитать высоту и ширину таблицы, если потребуется тест от Х до Y МБ с шагом Z?
- Сортировка вроде не влияет, несимметричный шаг тоже, какие-то ограничения есть?
Изменено: Acid Burn - 10.09.2019 16:42:58
 
Цитата
Светлый написал:
А то!
Супер, спасибо! Добавил в закладки - будет куда ТСов посылать :)
 
Задача напоминает классическую задачу об упаковке в контейнеры, либо задачу линейного раскроя
Цитата
Андрей VG написал:
а на таком наборе входных данных
Цитата
Светлый написал:
*Немного красоты навёл:
У меня макросами немного по другому получилось: см. вложение
Возможно жадный алгоритм из 15го сообщения не все распределил
 
Цитата
MCH написал:
Возможно жадный алгоритм из 15го сообщения не все распределил
Формульный алгоритм немного модифицирован. Сначала ищем одно (для этого диапазон в формуле должен захватить пустые ячейки) или два свободных значения, чтобы в сумме дали равенство размеру контейнера. Если выровнять объём не удаётся, то берём максимальное. Следующие значения аналогично. Если при добавлении самого маленького свободного элемента контейнер переполнится, начинаем заполнять следующий контейнер. Хотелось бы проверять комбинацию из трёх элементов, но формула очень сильно усложнится и будет тормозить. Надо проверять, чтобы свободный элемент не суммировался два раза.
 
Несколько другой подход. Так же с минимизацией числа пулов тестов, но с выравниванием количества тестов в каждом пуле. Правда требуется предварительная сортировка по неубыванию.
 
Друзья, 2 моих вопроса остались без внимания - прокомментируйте, пожалуйста.
 
Off
Цитата
Acid Burn написал:
прокомментируйте, пожалуйста.
да отстаньте Вы , тут уже подходы решения важнее, а не Ваши вопросы :-)
Это конечно шутка.
По вопросам из тем форума, личку не читаю.
 
БМВ, шутка хорошая, шутка понравилась. :-)
 
Цитата
БМВ написал:
тут уже подходы решения важнее
Именно

Цитата
Андрей VG написал:
Несколько другой подход. Так же с минимизацией числа пулов тестов, но с выравниванием количества тестов в каждом пуле.
Решил аналогичную задачу на тех же исходных данных, что и в 20 сообщении
Получилось 9 пулов, в 8ми по 11 тестов, в 9ом - 12 тестов

Расход памяти в каждом наборе тестов одинаковый (за исключением последнего)
вариант найденного решения во вложении.

Можно найти подобное решение формулами?
Изменено: MCH - 11.09.2019 11:24:49
Страницы: 1
Наверх