Разбить ArrayList на максимально равные по количеству элементов части / Java

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Java [игнор отключен] [закрыт для гостей] / Разбить ArrayList на максимально равные по количеству элементов части

25 сообщений из 27, страница 1 из 2

все

Разбить ArrayList на максимально равные по количеству элементов части

#39827202

Molasar

Участник

Сообщения: 838

Рейтинг: 0 / 0

Всем привет!

Нужен алгоритм, который делит большой ArrayList на несколько мелких ArrayList так, чтобы полученные мелкие ArrayList были максимально равны по количеству элементов.

Например:
100 / 5 = 20 + 20 + 20 + 20 + 20
101 / 5 = 20 + 20 + 20 + 20 + 21
13 / 4 = 3 + 3 + 3 + 4

...

Рейтинг:

0 / 0

17.06.2019, 13:28

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827223

Alexey Tomin

Участник

Откуда: Самара

Сообщения: 1 715

Рейтинг: 0 / 0

MolasarВсем привет!

Нужен алгоритм, который делит большой ArrayList на несколько мелких ArrayList так, чтобы полученные мелкие ArrayList были максимально равны по количеству элементов.

Например:
100 / 5 = 20 + 20 + 20 + 20 + 20
101 / 5 = 20 + 20 + 20 + 20 + 21
13 / 4 = 3 + 3 + 3 + 4

100р на телефон и я напишу Вам эту лабораторку.

...

Рейтинг:

0 / 0

17.06.2019, 14:02

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827225

SQL2008

Участник

Откуда: Москва

Сообщения: 3 848

Рейтинг: 0 / 0

MolasarВсем привет!

Нужен алгоритм, который делит большой ArrayList на несколько мелких ArrayList
На сколько частей?

...

Рейтинг:

0 / 0

17.06.2019, 14:08

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827228

SQL2008

Участник

Откуда: Москва

Сообщения: 3 848

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

17.06.2019, 14:13

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827235

Molasar

Участник

Сообщения: 838

Рейтинг: 0 / 0

SQL2008Если количество частей заранее не определено, то в цикле делить длину большого массива на переменное число частей и смотреть дробную часть от полученного значения.
Если она близка к нулю или к единице, то найденное число делителя это подходящее значение.
Количество частей заранее неизвестно.
А если не близко к 0 или 1, например:
13 / 5 = 2,6

Как получить оптимальный вариант: 3 + 3 + 3 + 2 + 2?

...

Рейтинг:

0 / 0

17.06.2019, 14:24

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827243

Leonid Kudryavtsev

Участник

Сообщения: 9 300

Рейтинг: 0 / 0

Molasar...
Количество частей заранее неизвестно.
А если не близко к 0 или 1, например:
13 / 5 = 2,6

Как получить оптимальный вариант: 3 + 3 + 3 + 2 + 2?
Обычный, самый тупой, алгоритм диззиринга из графики:

2 (trunc(2.6) ошибка 0.6) + 3 (trunc(2.6+0.6) ошибка 2.6+0.6-3=0.2) + 2 (ошибка 2.6+0.2-3=0.8) + 3 (ошибка 0.4) + 3 (ошибка 0)

2 + 3 + 2 + 3 + 3

IMHO

...

Рейтинг:

0 / 0

17.06.2019, 14:40

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827245

vsl

Гость

MolasarSQL2008Если количество частей заранее не определено, то в цикле делить длину большого массива на переменное число частей и смотреть дробную часть от полученного значения.
Количество частей заранее неизвестно.
А если не близко к 0 или 1, например:
13 / 5 = 2,6

Как получить оптимальный вариант: 3 + 3 + 3 + 2 + 2?
Используйте алгоритм Брезенхема для прямой (из (0;0) в (N;K), где N — длина масива, K — кол-во частей)

...

Рейтинг:

0 / 0

17.06.2019, 14:41

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827252

Озверин

Участник

Откуда: Ростов-на-Дону

Сообщения: 3 646

Рейтинг: 0 / 0

MolasarВсем привет!

Нужен алгоритм, который делит большой ArrayList на несколько мелких ArrayList так, чтобы полученные мелкие ArrayList были максимально равны по количеству элементов.

Например:
100 / 5 = 20 + 20 + 20 + 20 + 20
101 / 5 = 20 + 20 + 20 + 20 + 21
13 / 4 = 3 + 3 + 3 + 4

условия не очень понятны.

почему 13/4 хуже чем 13/2(6+7) или 13/3(5+4+4)?

Постановка задачи - загадчная.

...

Рейтинг:

0 / 0

17.06.2019, 14:50

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827254

Leonid Kudryavtsev

Участник

Сообщения: 9 300

Рейтинг: 0 / 0

Самое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"

...

Рейтинг:

0 / 0

17.06.2019, 14:55

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827265

lleming

Участник

Сообщения: 1 905

Рейтинг: 0 / 0

Leonid KudryavtsevСамое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"

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

...

Рейтинг:

0 / 0

17.06.2019, 15:03

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827270

Озверин

Участник

Откуда: Ростов-на-Дону

Сообщения: 3 646

Рейтинг: 0 / 0

llemingLeonid KudryavtsevСамое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"

наверняка неявно подразумевается что минимальное количество элементов в каждом из разбитых 2
тогда почему бы все не бить на 2 или 2+1?

...

Рейтинг:

0 / 0

17.06.2019, 15:08

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827282

Leonid Kudryavtsev

Участник

Сообщения: 9 300

Рейтинг: 0 / 0

Озвериннаверняка неявно подразумевается...

я бы скорее подумал. что подразумевается кол-во частей sqrt( ArrayList.count )

...

Рейтинг:

0 / 0

17.06.2019, 15:18

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827289

Molasar

Участник

Сообщения: 838

Рейтинг: 0 / 0

ОзверинMolasarВсем привет!

Нужен алгоритм, который делит большой ArrayList на несколько мелких ArrayList так, чтобы полученные мелкие ArrayList были максимально равны по количеству элементов.

Например:
100 / 5 = 20 + 20 + 20 + 20 + 20
101 / 5 = 20 + 20 + 20 + 20 + 21
13 / 4 = 3 + 3 + 3 + 4

условия не очень понятны.

почему 13/4 хуже чем 13/2(6+7) или 13/3(5+4+4)?

Постановка задачи - загадчная.
Изначально неизвестно на какое количество частей нужно делить ArrayList. Для простоты будем говорить про массив.
Размер массива тоже неизвестен.
13/4 не хуже чем 13/2(6+7).
Если делитель 4, то должно быть 3 + 3 + 3 + 4 или 4 + 3 + 3 + 3.
Если делитель 2, то 6+7

...

Рейтинг:

0 / 0

17.06.2019, 15:29

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827304

Molasar

Участник

Сообщения: 838

Рейтинг: 0 / 0

Leonid KudryavtsevСамое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"
Приходит Object[N] его нужно обработать на K-потоках. Для этого необходимо, чтобы каждому потоку досталась максимально равная часть работы, т.е. часть массива. Вот поэтому и делим.

...

Рейтинг:

0 / 0

17.06.2019, 15:55

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827328

забыл ник

Участник

Сообщения: 3 596

Рейтинг: 0 / 0

Жесть. А про пул потоков не слышали?

...

Рейтинг:

0 / 0

17.06.2019, 16:16

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827333

Molasar

Участник

Сообщения: 838

Рейтинг: 0 / 0

забыл никЖесть. А про пул потоков не слышали?
Слышал и???
Как вы раздадите одну задачу на пул потоков????

...

Рейтинг:

0 / 0

17.06.2019, 16:23

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827335

забыл ник

Участник

Сообщения: 3 596

Рейтинг: 0 / 0

Molasar, очевидно разобью на маленькие части. один элемент массива - одна задача

...

Рейтинг:

0 / 0

17.06.2019, 16:26

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827347

Molasar

Участник

Сообщения: 838

Рейтинг: 0 / 0

забыл никMolasar, очевидно разобью на маленькие части. один элемент массива - одна задача
А если данные нужно сохранить в БД. Например, 100000 строк.
Вы будете под запись каждой строки выделять поток?

...

Рейтинг:

0 / 0

17.06.2019, 16:35

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827348

Озверин

Участник

Откуда: Ростов-на-Дону

Сообщения: 3 646

Рейтинг: 0 / 0

MolasarLeonid KudryavtsevСамое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"
Приходит Object[N] его нужно обработать на K-потоках. Для этого необходимо, чтобы каждому потоку досталась максимально равная часть работы, т.е. часть массива. Вот поэтому и делим.

наверное, это задача решается немного иначе.

1. Во-первых, вы должны исходить из некой пропускной способности. Допустим, 10 объектов в секунду.
2. Во-вторых, вы должны знать максимально эффективное кол-во потоков, которое имеет смысл пускать на сервере(если все измеряется потоками). Делается это через нагрузочное тестирование.
3. В-третьих, просто следить за пропускной способностью и добавлять потоки, когда требуется до n потоков.

В общем случае, вам может подойти нечто вроде disruptor`а - этий кольцевой массив событий, который обрабатывает несколько консьюемров, причем могут сразу пачкой(если логика позволяет).

...

Рейтинг:

0 / 0

17.06.2019, 16:38

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827350

Озверин

Участник

Откуда: Ростов-на-Дону

Сообщения: 3 646

Рейтинг: 0 / 0

...

Рейтинг:

0 / 0

17.06.2019, 16:39

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827357

забыл ник

Участник

Сообщения: 3 596

Рейтинг: 0 / 0

Molasarзабыл никMolasar, очевидно разобью на маленькие части. один элемент массива - одна задача
А если данные нужно сохранить в БД. Например, 100000 строк.
Вы будете под запись каждой строки выделять поток?
Начинаешь задавать правильные вопросы.

К тем пунктам что добавил Озверин, ты должен решить задачу написав функцию, которая принимает на вход int(число элементов в массиве) и вычисляет другой int(количество элементов в партитишене), учитывая коээфициенты -
1) количество потоков в системе
2) CPU или IO-bound таск. При CPU-bound коэффийиент должен быть строго 1, при IO - от 2-5 обычно, но надо мерять на реальной нагрузке
3) минимальное количество элементов на один таск, ибо если у тебя мало элементов, то нету особого смысла параллелить.

...

Рейтинг:

0 / 0

17.06.2019, 16:47

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39827363

Leonid Kudryavtsev

Участник

Сообщения: 9 300

Рейтинг: 0 / 0

Molasar....Вот поэтому и делим.

просто циклично кидать в ArrayList'ы по одной штуке

Был на входе набор элементов 1,2,3,4,5,6,7
нужно побить на 3-и массива, просто циклически в массивы и кидаете
массив A: 1, 4, 7
массив B: 2, 5, не хватило
массив C: 3, 6, не хватило

в чем проблема - мне не понятно. Можно "размазать" 21909803 . Можно заранее посчитать, какая будет длина короткого массива truncate( length / threads_count ), сколько будет "перебравших +1" ( length % threads_count ), сколько будет "коротких" ( threads - length % threads_count).

Если запросом, то опять таки:

SELECT rownum mod threads_count as n, my_table.* FROM my_table

Задача не стоящая выяденного яйца. IMHO

...

Рейтинг:

0 / 0

17.06.2019, 16:53

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39828981

Мозговой_слизень

Участник

Сообщения: 3 019

Рейтинг: 0 / 0

Leonid KudryavtsevСамое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"

5 баллов! ИМХО просто шедеврально. И главное, укладывается в "условия задачи".
Но можно пойти еще дальше. Зачем нам 13-ть ArrayList'ов, зачем память засирать. Лучше пусть будет 1. Таким, образом, мы пришли к выводу, что задачу решать вообще не имеет смысла. Можно считать ее решенной уже на этапе постановки.

Зачем подниматься на 3-ий этаж и спускаться на первый, если по условиям задачи нужно быть на первом. Можно просто не подниматься.

...

Рейтинг:

0 / 0

21.06.2019, 04:23

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39828982

Мозговой_слизень

Участник

Сообщения: 3 019

Рейтинг: 0 / 0

llemingLeonid KudryavtsevСамое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"

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

Нельзя ли уточнить. А то так придешь к врачу, он тебе так неявно не то лекарство даст и неявно откинешься.

...

Рейтинг:

0 / 0

21.06.2019, 04:24

| Ответить | Цитировать | Написать

Разбить ArrayList на максимально равные по количеству элементов части

#39829086

chpasha

Участник

Сообщения: 10 713

Рейтинг: 0 / 0

офигенный пример того, почему на любой заданный вопрос нужно отвечать вопросом "объясни, зачем это нужно"

...

Рейтинг:

0 / 0

21.06.2019, 10:59

| Ответить | Цитировать | Написать

25 сообщений из 27, страница 1 из 2

все

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=59&fpage=26&tid=2121226]:	0ms
get settings:	9ms
get forum list:	15ms
check forum access:	4ms
check topic access:	4ms
track hit:	75ms
get topic data:	12ms
get forum data:	3ms
get page messages:	62ms
get tp. blocked users:	2ms
others:	11ms

total:	197ms