Всем привет! Задача - провести 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 написал: По логике вначале можно запустить 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.
Андрей 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 написал: А что, если у меня было бы 16 Гб RAM?
Тогда будет не частный случай оптимизационных задач, условно называемых задачей о рюкзаке. Надеюсь Михаил MCH меня поправит, если не прав. Но, учитывая, что такой класс задач NP полный, то обычно не мучаются, а пользуются жадным алгоритмом - он не оптимальный, но зато самый быстрый. В этом случае вам нужно уходить от функций (путь даже и udf), а переходить к макросам. Суть алгоритма проста: 1. упорядочиваем данные не по возрастанию 2. подбираем первое по порядку, которое можно разместить в рюкзаке, исключаем найденное. 3. для оставшегося места подбираем аналогично 2. 4. если уже ничего не лезет - считаем рюкзак заполненным 5. переходим к новому рюкзаку того же размера и в 2 6. 2-5 выполняем пока не кончатся предметы.
Нашёл подходящий файл. Если задать 50 чисел (от 5400 до 500 с шагом 100) и размер выборки от 1 до 4, то метод "Ограниченный перебор" выдаёт - при кол-ве RAM ("желаемая сумма") = 5500 - 426 вариантов (достаточно 27-ми), - при кол-ве RAM ("желаемая сумма") = 15400 - 1527 вариантов Остальные варианты не так работают. Кто сможет доработать?
Светлый, проверил со значениями 5500, 15000 и 31000 - вроде все цифры "на месте"! Хотя при значении 31000 6 этап можно "уместить" в 5-ом. А так очень круто! Спасибо!
Итого вариант, который я хотел проверить, полностью работает. Но Андрей VG прав - для ситуации, когда startRam/endRam/stepRam/maxRAM полностью динамические, макрос удобнее. Может MCH (Михаил Ч.) или кто-то из Гуру откликнется, потому что я такой макрос не потяну. )
Светлый, просто отлично! Спасибо огромное! Ввёл динамические диапазоны - формула нагляднее и данные можно добавлять, не растягивая формулы. Есть 2 вопроса: - Как рассчитать высоту и ширину таблицы, если потребуется тест от Х до Y МБ с шагом Z? - Сортировка вроде не влияет, несимметричный шаг тоже, какие-то ограничения есть?
MCH написал: Возможно жадный алгоритм из 15го сообщения не все распределил
Формульный алгоритм немного модифицирован. Сначала ищем одно (для этого диапазон в формуле должен захватить пустые ячейки) или два свободных значения, чтобы в сумме дали равенство размеру контейнера. Если выровнять объём не удаётся, то берём максимальное. Следующие значения аналогично. Если при добавлении самого маленького свободного элемента контейнер переполнится, начинаем заполнять следующий контейнер. Хотелось бы проверять комбинацию из трёх элементов, но формула очень сильно усложнится и будет тормозить. Надо проверять, чтобы свободный элемент не суммировался два раза.
Несколько другой подход. Так же с минимизацией числа пулов тестов, но с выравниванием количества тестов в каждом пуле. Правда требуется предварительная сортировка по неубыванию.