Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Разбить ArrayList на максимально равные по количеству элементов части  [new]
Molasar
Member

Откуда:
Сообщений: 773
Всем привет!

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

Например:
100 / 5 = 20 + 20 + 20 + 20 + 20
101 / 5 = 20 + 20 + 20 + 20 + 21
13 / 4 = 3 + 3 + 3 + 4
17 июн 19, 13:28    [21909724]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Alexey Tomin
Member

Откуда: Самара
Сообщений: 1783
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р на телефон и я напишу Вам эту лабораторку.
17 июн 19, 14:02    [21909757]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
SQL2008
Member

Откуда: Москва
Сообщений: 4006
Molasar
Всем привет!

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

На сколько частей?
17 июн 19, 14:08    [21909763]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
SQL2008
Member

Откуда: Москва
Сообщений: 4006
Если количество частей заранее не определено, то в цикле делить длину большого массива на переменное число частей и смотреть дробную часть от полученного значения.
Если она близка к нулю или к единице, то найденное число делителя это подходящее значение.
17 июн 19, 14:13    [21909769]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Molasar
Member

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

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

Как получить оптимальный вариант: 3 + 3 + 3 + 2 + 2?
17 июн 19, 14:24    [21909783]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7994
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
17 июн 19, 14:40    [21909803]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
vsl
Member

Откуда:
Сообщений: 44
Molasar
SQL2008
Если количество частей заранее не определено, то в цикле делить длину большого массива на переменное число частей и смотреть дробную часть от полученного значения.

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

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

Используйте алгоритм Брезенхема для прямой (из (0;0) в (N;K), где N — длина масива, K — кол-во частей)
17 июн 19, 14:41    [21909805]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Озверин
Member

Откуда: Ростов-на-Дону
Сообщений: 5183
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)?

Постановка задачи - загадчная.
17 июн 19, 14:50    [21909815]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7994
Самое загадочное - это ответ
Т.к. ArrayList наиболее правильно бьется просто на 13-ть ArrayList'ов
И тогда все получившиеся ArrayList'ы будут не просто максимально, а совершенно точно "равны по количеству элементов"
17 июн 19, 14:55    [21909819]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
lleming
Member

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


наверняка неявно подразумевается что минимальное количество элементов в каждом из разбитых 2
17 июн 19, 15:03    [21909839]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Озверин
Member

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


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

тогда почему бы все не бить на 2 или 2+1?
17 июн 19, 15:08    [21909850]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7994
Озверин
наверняка неявно подразумевается...


я бы скорее подумал. что подразумевается кол-во частей sqrt( ArrayList.count )
17 июн 19, 15:18    [21909866]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Molasar
Member

Откуда:
Сообщений: 773
Озверин
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
17 июн 19, 15:29    [21909876]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Molasar
Member

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

Приходит Object[N] его нужно обработать на K-потоках. Для этого необходимо, чтобы каждому потоку досталась максимально равная часть работы, т.е. часть массива. Вот поэтому и делим.
17 июн 19, 15:55    [21909900]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
забыл ник
Member

Откуда:
Сообщений: 3045
Жесть. А про пул потоков не слышали?
17 июн 19, 16:16    [21909938]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Molasar
Member

Откуда:
Сообщений: 773
забыл ник
Жесть. А про пул потоков не слышали?

Слышал и???
Как вы раздадите одну задачу на пул потоков????
17 июн 19, 16:23    [21909947]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
забыл ник
Member

Откуда:
Сообщений: 3045
Molasar, очевидно разобью на маленькие части. один элемент массива - одна задача
17 июн 19, 16:26    [21909951]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Molasar
Member

Откуда:
Сообщений: 773
забыл ник
Molasar, очевидно разобью на маленькие части. один элемент массива - одна задача

А если данные нужно сохранить в БД. Например, 100000 строк.
Вы будете под запись каждой строки выделять поток?
17 июн 19, 16:35    [21909968]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Озверин
Member

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

Приходит Object[N] его нужно обработать на K-потоках. Для этого необходимо, чтобы каждому потоку досталась максимально равная часть работы, т.е. часть массива. Вот поэтому и делим.



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

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


В общем случае, вам может подойти нечто вроде disruptor`а - этий кольцевой массив событий, который обрабатывает несколько консьюемров, причем могут сразу пачкой(если логика позволяет).
17 июн 19, 16:38    [21909971]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Озверин
Member

Откуда: Ростов-на-Дону
Сообщений: 5183
Molasar
забыл ник
Molasar, очевидно разобью на маленькие части. один элемент массива - одна задача

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


так это вы все еще про запись в бд что ли? Не поборол?
17 июн 19, 16:39    [21909974]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
забыл ник
Member

Откуда:
Сообщений: 3045
Molasar
забыл ник
Molasar, очевидно разобью на маленькие части. один элемент массива - одна задача

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

Начинаешь задавать правильные вопросы.

К тем пунктам что добавил Озверин, ты должен решить задачу написав функцию, которая принимает на вход int(число элементов в массиве) и вычисляет другой int(количество элементов в партитишене), учитывая коээфициенты -
1) количество потоков в системе
2) CPU или IO-bound таск. При CPU-bound коэффийиент должен быть строго 1, при IO - от 2-5 обычно, но надо мерять на реальной нагрузке
3) минимальное количество элементов на один таск, ибо если у тебя мало элементов, то нету особого смысла параллелить.
17 июн 19, 16:47    [21909993]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7994
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
17 июн 19, 16:53    [21910007]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Мозговой_слизень
Member

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


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

Зачем подниматься на 3-ий этаж и спускаться на первый, если по условиям задачи нужно быть на первом. Можно просто не подниматься.
21 июн 19, 04:23    [21912564]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
Мозговой_слизень
Member

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


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


Нельзя ли уточнить. А то так придешь к врачу, он тебе так неявно не то лекарство даст и неявно откинешься.
21 июн 19, 04:24    [21912565]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
chpasha
Member

Откуда:
Сообщений: 8593
офигенный пример того, почему на любой заданный вопрос нужно отвечать вопросом "объясни, зачем это нужно"
21 июн 19, 10:59    [21912743]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Java Ответить