Блог

Я пытаюсь нарезать список (вызовите этот список ввода и он содержит элементы типа данных Java double) на несколько частей (вложенные списки). Размер вложенных списков может быть неравным на небольшое число. Каждая часть (вложенный список) служит в качестве входных данных для другой программы. Размер входного списка — это переменная с максимальным размером 10000, то есть он может быть как 1, или 2, или 3, так и большим, как 100, или 10000, или любое число меньше 10000.

Каков наилучший способ разделить такой список на несколько частей? Я рассматривал распределение 3h 1 Дональда Кнута при проектировании пробелов для сортировки оболочки. Однако я не уверен, будет ли это уместно. Ценю вашу помощь.

Спасибо!

Чтобы расширить ответ, укажите оптимальное значение M,

Предположим, что существует некоторая функция затрат C, связанная с обработкой списка размера M.

Затем вы хотите минимизировать функцию

Общая стоимость = M * C (N / M) накладные расходы

где накладные расходы — это стоимость разделения списка.

Я думаю, что для большинства приложений не было бы большой разницы для разных значений M, поэтому нет смысла разделять его.

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

Общая стоимость = C (N / M) накладные расходы, если M < количество процессоров

таким образом, вы должны выбрать M, чтобы оно было близко к количеству процессоров, но меньше его.

Если я не неправильно понимаю этот вопрос, это кажется простым.

Учитывая список размером N, создать M подсписков, где M < N,

1. создайте M-1 списков размером K = N / M
   (округление в меньшую сторону)
2. создайте список размером M — (M — 1) * K

Затем

1. скопируйте первые K элементов в первый список
2. скопируйте следующие K элементов во второй список,
3. и так далее,
4. наконец, скопируйте последнее M — (M — 1) * K в последний список.