ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Получение всех цепочек ключей дерева
9 сообщений из 9, страница 1 из 1
Получение всех цепочек ключей дерева
    #39648262
G.Collector
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
G.Collector
Участник
Строю дерево произвольной ширины и глубины. Узел дерева:

Код: java
1.
2.
3.
4.
5.
6.
7.
public class Node {

	@Getter private Object key;
	@Getter @Setter private Object value;

	@Getter private Set<Node> childs;
	...



Корнем дерева является узел с ключом (key) == topNode

Начиная от childs корневого узла необходимо получить все цепочки ключей, например

key1 - key12
key1 - key13 - key123
key1 - key13 - key234
key2 - key22 - key277

итд.

Вот как я это делаю:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
private Set<List> keys = new HashSet<>();

public Set keySet() {

	keys.clear();

	for (Node child : topNode.getChilds())
		recurseCollectKeys(child, new LinkedList());

	return keys;
}

private void recurseCollectKeys(Node node, LinkedList k) {
	LinkedList l = new LinkedList(k);

	l.add(node.getKey());

	if (node.getChilds().size() > 0)
		node.getChilds().forEach(child -> recurseCollectKeys(child, l));

	else
		keys.add(l);
}



Но это потоконебезопасно. Если кто запустит keySet() пока работает другой keySet() результат будет не предсказуем.

Можно лочить keys, но это в нагруженной системе будет узким местом.

Можно ли как-то еще получить цепочки ключей? Спасибо.
...
Рейтинг: 0 / 0
22.05.2018, 18:04
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648265
забыл ник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
забыл ник
Участник
Что касается многопоточности то тут скорее проблема в том, что другой поток может изменить саму структуру данных, а не ваш keySet, который фиксится банальным выносом private Set<List> keys = new HashSet<>(); из вне метода внутрь. Нет шаринга данных - нет проблем
...
Рейтинг: 0 / 0
22.05.2018, 18:18
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648270
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
G.Collector,

Рекурсию всегда можно развернуть в цикл.
По поводу многопоточности не понятно что именно вы хотите. Синглтон? Или параллельное вычисление? Каждому потоку дать свой экземпляр во время поиска ключей. Можно это разными способами делать. Можно keys сделать аргументом метода. Можно отделить объект дерева от объекта поиска ключей.
Можно создать структуру в которой поиск не понадобится а список будет сформирован вместе с формированием дерева
...
Рейтинг: 0 / 0
22.05.2018, 18:32
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648276
G.Collector
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
G.Collector
Участник
BlazkowiczG.Collector,

Рекурсию всегда можно развернуть в цикл.
По поводу многопоточности не понятно что именно вы хотите. Синглтон? Или параллельное вычисление? Каждому потоку дать свой экземпляр во время поиска ключей. Можно это разными способами делать. Можно keys сделать аргументом метода. Можно отделить объект дерева от объекта поиска ключей.
Можно создать структуру в которой поиск не понадобится а список будет сформирован вместе с формированием дерева Вот мне кажется, что это самый лучший вариант
...
Рейтинг: 0 / 0
22.05.2018, 18:46
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648287
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
«Лучший» вариант зависит от того как и когда вы этот список будете использовать. Фактически может оказатся что такой список вам и не нужен вовсе. Просто нужна дополнительная информация в узлах чтобы обойти их нужным вам образом.
...
Рейтинг: 0 / 0
22.05.2018, 19:02
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648346
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
G.CollectorМожно лочить keys, но это в нагруженной системе будет узким местом.

Мы сейчас говорим о том чего нет и проектируем структуру данных под неизвестный юзкейс.

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

Для структур данных с минимальной конкуренцией обычно делают страничную память
и для каждой страницы фиксируют серийный номер версии. Потоки работают атомарно
с номером версии а со страницей эксклюзивно. Если поток писатель хочет писать то он
создают свою версию страницы. Потоки читатели - читают безопасно страницу с учотом
версии. Вобщем все как в базах данных. Как вы разложите дерево в страничную память
это та еще дилемма.

Вобщем версионные структуры очень сложны. И может быть проще пересмотреть
ваш алгоритм чем подпиливать дерево под универсальный случай которого мы не знаем.
...
Рейтинг: 0 / 0
23.05.2018, 00:46
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648377
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
G.CollectorМожно ли как-то еще получить цепочки ключей?расшарить в базе. Там и запрос для цепочки уже есть. И лочить не надо)).
...
Рейтинг: 0 / 0
23.05.2018, 07:15
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648383
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
Мне кажется что если каждая нода дерева будет знать не только своих детей, но и количество всех листьев в потомках, то используя эту информацию можно по индексу пути вычислить полный путь к листу.
Если я правильно понял пример, то нужны пути только к листьям. Соответсвенно, зная количество дочерних листьев и индекс пути, всегда можно вычислить какой из детей находится в этом пути.
Это и будет той дополнительной информацией о которой я говорил ранее.
Если эту информацию обновлять во время построения дерева, то задача вычисления путей отсутсвует в принципе. Список уже будет доступен в самом дереве.
...
Рейтинг: 0 / 0
23.05.2018, 07:33
| Ответить | Цитировать | Написать  
Получение всех цепочек ключей дерева
    #39648627
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
G.Collector,

Очень похоже на файловую систему. В современных ФС (Ntfs, Ext4) используются сбалансированные бинарные деревья, может стоит от них прыгать?
...
Рейтинг: 0 / 0
23.05.2018, 13:03
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Получение всех цепочек ключей дерева
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=39648270&tid=2122035]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 159ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 50ms
get tp. blocked users:
 2ms
others: 235ms
total:  492ms
созд. / загр.: 492ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]