Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2      [все]
 Разбить 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

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

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

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

Откуда: Москва
Сообщений: 4005
Если количество частей заранее не определено, то в цикле делить длину большого массива на переменное число частей и смотреть дробную часть от полученного значения.
Если она близка к нулю или к единице, то найденное число делителя это подходящее значение.
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

Откуда:
Сообщений: 7989
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

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

Откуда:
Сообщений: 1653
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

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


я бы скорее подумал. что подразумевается кол-во частей 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

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

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

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

Откуда:
Сообщений: 3038
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

Откуда:
Сообщений: 3038
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

Откуда:
Сообщений: 7989
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]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
mayton
Member

Откуда: loopback
Сообщений: 42845
100 / 5 = 20 + 20 + 20 + 20 + 20
101 / 5 = 20 + 20 + 20 + 20 + 21
13 / 4 = 3 + 3 + 3 + 4

Тут - простой алгоритм. Целочисленного деления и остатка (%) достаточно.
21 июн 19, 11:53    [21912807]     Ответить | Цитировать Сообщить модератору
 Re: Разбить ArrayList на максимально равные по количеству элементов части  [new]
UScorp
Member

Откуда: Кыргызстан
Сообщений: 141
Кажется мне, что все же использовать пул потоков будет правильнее.

Разным потокам может быть выделено разное кол-во ресурсов и отработать они могут за разное время.

Допустим надо будет вставить 10к записей в 5 потоков, дадим каждому потоку по 2к записей и запустим их одновременно. Первый поток выполниться за 1мин, второй за 3 мин, третий за 2мин, четвертый за 2,5 мин, а пятому не повезло, его все кругом ущемляют и он выполнился за 10 мин.

Тогда получается, что 7-8 минут работал только один "ущербный" поток, а остальные потоки ему не помогали.
Если бы мы раздробили данные на более мелкие порции (допустим по 200 записей), то более быстро освободившийся поток мог бы взять следующую небольшую порцию. Тогда они бы завершили свою работу все более или менее равномерно.

Добавлю - это все ИХМО ))))
28 июн 19, 14:41    [21917095]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Java Ответить