Распределение элементов по корзинам с собственным локом

  • 14
  • Недоступна
В синхронизированных блоках используй нужный лок.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (123)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Алексей
Уровень 27, Phonky Town
28 июля, 10:25
Ничего не понял, скажите что почитать.
Flexo Bending Unit #3370318
8 июля, 20:36
принимается ответ только определённого вида - используйте уже имеющуюся локальную переменную, вместо метода - для вычисления хеша - не используйте константу размера контейнера блоков, а используйте метод самого контейнера для нахождения своего размера ненужные ограничения, не влияющие на работу, но как есть
Татьяна Мацеонжек
Уровень 31, Москва, Россия
28 апреля, 10:20
Не, ну спасибо за очередную технологию, но она вообще не ложится в ряд. Без предисловий и контекста задача вообще бесполезна. Я не требую теории под каждую задачу, но вот так отрывками подавать, тоже не вариант
ЕП
Уровень 29, Санкт-Петербург
7 апреля, 09:42
Поправьте, если не правильно понял. Здесь раскрывается механика работы конкурирующего списка. В частности, создаётся связный список из элементов Node, каждый из которых хранит ссылку на следующий узел и какую-то пару данных (ключ-значение). При этом список разделён на n-ное количество очередей. Начало каждой очереди мы записываем в массив buckets[n] и при добавлении нового элемента в связный список мы определяем его в одну из очередей. То, в какую очередь он попадёт, зависит от хеша ключа нового элемента. С помощью key.hashCode() % buckets.length мы разделяем все возможные хеши ключей на n вариантов. Теперь, если нам нужно выполнить поиск по этому списку, не обязательно листать весь список, достаточно пройти по одной из наших n очередей. По какой именно, определяется хешем ключа искомого элемента. При этом, реализована возможность работы с этим списком из нескольких нитей. Чтобы обезопасить данные, создаётся массив из нескольких объектов (по числу нитей, разрешённых для работы, в нашем случае -12) для выполнения работы в качестве замков. Поскольку число очередей и число замков различные, каждый замок может запирать от нуля до нескольких очередей (зависит от числа очередей). Прописывая "i%NUMBER_LOCKS", мы равномерно распределяем очереди между замками, что позволяет одновременно блокировать не весь список, а только некоторые очереди, среди которых имеется занятая. Это позволит другим нитям, например, параллельно выполнить поиск в списке, если искомый элемент находится в незаблокированной очереди.
Kes Чайник в Банк
2 июня, 03:47
Спасибо. Только после твоей росписи понял, как тут всё устроено. Получается, что метод clear() зачищает не весь список, а просто заглавия очередей. Именно этот метод смущал.
ЕП
Уровень 29, Санкт-Петербург
12 июня, 20:26
Остальные элементы списка съедает сборщик мусора, поскольку они теряют удерживающую их связь
Kes Чайник в Банк
15 июня, 04:27
ЕП Спасибо
Даниил Александрович
Уровень 35, Тамбов , Россия
17 марта, 15:26
Странная задача. со странным ТЗ. на 100 или 1000000 объектов если такое количество локов, программа тупа будет в холостую постоянно висеть... плевать, done. и поехали дальше... лочим не объект, переменную. а какую и с каким индексом комменты ниже в помощь.
Булат
Уровень 37, Москва
18 февраля, 12:04
Класс, голова перегрузилась даже при осознании готового решения! Как я понял мы тут руками реализовали hash table (или же bucketing в sql таблицах) - типа поделили массив на рабочие куски, т.е. hashcode i-го объекта в массиве задали в пределах [0-12] при помощи
key.hashCode() % buckets.length
Далее представим, что целевой массив buckets уже заполнен миллионом значений каждому из которых сопоставлен свой хеш. При выборке методом get() берем очередной key, смотрим для него хеш, и берем только ту часть buckets которая соответствует нашему хешу, и далее внутри этого подмножества сравниваем конкретные key значения equals'ом, ПРИ ЭТОМ ГОВОРЯ, ЧТО ВСЕ ЭТИ ОПЕРАЦИИ ДОСТУПНЫ ДЛЯ ОДНОГО ПОТОКА НА ОДИН БАКЕТ. Т.е. как я понял, якобы в 12 потоков (именно столько локов) можно будет обрабатывать наш Node[] buckets. В случае с clear до конца не понял, обязательно и юзать код как в решении, или было бы достаточно:
synchronized (locks[i])
В общем такой ход рассуждений на основе решения, хз как до этого с нуля дойти. Поправьте, если заблуждаюсь.
Юрий
Уровень 30, Калининград, Россия
11 декабря 2020, 12:50
Ну как тут понять что ЗАВИСИМОСТЬ ОБЪЕКТА И ЛОКОВ это %(остаток от деления)????? Ну как?
Sasha Motorin
Уровень 35, Кострома, Россия
12 марта, 21:44
ну просто хэш же может быть больше чем locs.length. Компилятор не найдёт такой объект в массиве
Davilalexius
Уровень 34, Москва, Россия
1 декабря 2020, 20:04
Вот тоже интересно:
locks[(i+NUMBER_LOCKS)%NUMBER_LOCKS]
Чем не удовлетворяет:"используй lock из массива locks в зависимости от индекса элемента и количества лок объектов"? Посмотрим реализацию без i+NUMBER_LOCKS и увидим, что первые 12 итераций i приводят нас к lock=0. Т.е. мы, гарантированно, 12 раз подряд лочим одним lock объектом. Чем моя реализация не устроила Валидатор, кто знает?)
Sergey
Уровень 29, Минск, Беларусь
5 декабря 2020, 16:03
Ты видимо не до конца понимаешь как работает остаток от деления: 0 % 12 == 0 1 % 12 == 1 2 % 12 == 2 и т.д. Хотя твоё решение даст точно такой же результат. Просто избыточно прибавлять к i количество локов.
Davilalexius
Уровень 34, Москва, Россия
5 декабря 2020, 20:43
Да, уж) Было поздно -мозг устал)
Алексей Потапахин
Уровень 29, Россия
4 сентября 2020, 15:37
это очень странная штука
vitalii Sili
Уровень 35, Münich, Германия
4 августа 2020, 13:41
Тупо методом тыка. А что дальше будет ?