LINUX.ORG.RU

[C] хэш списков в линейный список

 


0

1

Есть массив ~4000 списков(sys/queue.h). Данные добавляются на основе хэш функции. Это все вполне прилично работает для добавления\удаления и поиска по конкретному значению. Теперь мне надо выводить табличку значений, причем в отдельном треде. Как бы мне не ломая уже работающий код пришпандорить линейную структуру, чтобы она не долго лочила основную структуру.

★★★★★

тоесть 4000 списков - каждый список в ней элементы один и тотже ХЕШ имеют ? так ?

а чтоб долго нелочила - лочить нужно имхо только при удалении элемента - все остальное может и так работать

ae1234 ★★
()
Ответ на: комментарий от ae1234

~4000 списков, в какой конкретно список добавлять элемент определяет хэш функция, сейчас я тупо прогоняю два вложенных цикла и вывожу результаты, при большом кол-ве элементов может занимать существенное время

хм, может не мучатся преждевременной оптимизацией и посмотреть что получится в результате :-)

hizel ★★★★★
() автор топика
Ответ на: комментарий от ae1234

собственно это libalias
и там lock-и используются, когда оно крутится в ядре FreeBSD, буду раскруивать, зачем они лочат при поиске

hizel ★★★★★
() автор топика

Я не знаю, что там у вас во FreeBSD, но наши люди для поиска по конкретному значению используют сбалансированные деревья.

unnamed
()
Ответ на: комментарий от unnamed

для поиска по конкретного значения - лучше хеша трудно чтото представить

сбалансированное дерево - это и есть своеобразный хеш :)

ae1234 ★★
()
Ответ на: комментарий от ae1234

сбалансированное дерево - это и есть своеобразный хеш :)

Ну-ну. Только вот находит дерево за O(log n) в противовес O(n)

4000 — это не так уж и мало.

unnamed
()
Ответ на: комментарий от unnamed

находиться дерево ? вообщето в хеще - нахождения дерева независит от колва деревьев
O(1) иль как там

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

ae1234 ★★
()
Ответ на: комментарий от unnamed

как чувствовал, что про FreeBSD не надо было упоминать

наши люди это кернел-девелоперы? вы так толсто намекаете посмотреть в nf_nat\nf_conntrack мм?

hizel ★★★★★
() автор топика
Ответ на: комментарий от hizel

дак :) уж название сайт то какое


кстати интересно - чтото более сложное чем хеш и очереди - используються ли в ядрах ?
балансированные деревья и так далее

(reiserfs там то на деревьях вся она) а еще ?

ae1234 ★★
()
Ответ на: комментарий от ae1234

в линуксе, например для таблиц маршрутизации можно выбирать структуру хранения маршрутов, это я на nag.ru как-то прочитал

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

hizel ★★★★★
() автор топика
Ответ на: комментарий от hizel

Про FreeBSD была шутка :)

Я не кернел девелопер, просто действительно линейный поиск при немалом объёме данных режет глаза. Если я чего-то не понимаю, объясни, зачем в ядре неоптимальный медленный код?

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

Занесение данных — да, log n в противовес единицы. Зато поиск и удаление быстрее. На порядок.

unnamed
()
Ответ на: комментарий от unnamed

какой линейный список, хм, может я слишком многословен
данные хранятся в хэше и хэш функция распределяет на ~4k элементов
где линейная структура?
вы как теоретик или практик спрашиваете? а то, теоретики придя на конкретную программную платформу встречаются с суровой реальностью, знаете ли

hizel ★★★★★
() автор топика
Ответ на: комментарий от hizel

Предлагаю начать всё же с теории.

Хэш-функция ставит объекту в соответствие целое число, так? Далее: оно хранится в списке. Это линейный список или хэш-таблица?

unnamed
()
Ответ на: комментарий от unnamed

>Хэш-функция ставит объекту в соответствие целое число, так? Далее: оно хранится в списке. Это линейный список или хэш-таблица?

да, это линейный список
теория меня сейчас мало волнует, хотя если вы предложите относительно простой способ улучшить эту структуру, я не против 8-)

hizel ★★★★★
() автор топика
Ответ на: комментарий от hizel

Если интересно, можно посмотреть в сторону красно-чёрных, например, деревьев.

unnamed
()
Ответ на: комментарий от unnamed

хеш функция - дает значение от 0 до 3999
есть массив обьемом 4 тонны указателей - указатели ведут на заголовок линейной очереди(списка)

хеш + список - самое простое и эффективное решение

ae1234 ★★
()

Гм, читал вопрос и комментарии, но так и не понял задачу.
Может, приведешь псевдокод? Что сейчас есть и чего хочешь добиться?

Vamp
()
Ответ на: комментарий от ae1234

указатели ведут на заголовок линейной очереди(списка)

4000 указателей, ведущих на один и тот же элемент. Их вполне можно было заменить одним.

unnamed
()
Ответ на: комментарий от unnamed

>4000 указателей, ведущих на один и тот же элемент. Их вполне можно было заменить одним.

откуда это :-(
что-то я видимо совсем объяснять не умею

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

hizel ★★★★★
() автор топика
Ответ на: комментарий от unnamed

Анто́н Па́влович? Вы!? В чем проблема?

hizel ★★★★★
() автор топика
Ответ на: комментарий от unnamed

каждый указатель ведет на свой список - если для этого хеша нет элементов - то указатель показывает в нуль
стандартная схема

ae1234 ★★
()
Ответ на: комментарий от ae1234

вопрос отошел на один шаг назад в цепочке моих рассуждений
что предпочтительней использовать лочить основную структуру или как то извернутся и не лочить :-)
так как операция «вывода на экран» значительно менее приоритетная чем поиск\добавление\удаление

hizel ★★★★★
() автор топика

Как только хэш-таблицу с цепочками коллизий не обзывают.
Может лучше использовать открытую адресацию или вообще отказаться от хэш в пользу других структур данных?

Goblin
()
Ответ на: комментарий от Goblin

страшно, продукт рабочий, просто сверху прилаживаю нашлепку
там есть mutex но они сразу на всю хэш-таблицу, что мне кажется не очень ок, при чтении не будет основной и более приоритетный процесс :-(

hizel ★★★★★
() автор топика
Ответ на: комментарий от hizel

думаю завести массив мутексов, вся-ко полегче будет :-)
или может есть близкая по духу структура легкая в синхронизации, когда есть более приоритетные писатели и менее приоритетные читатели для которых не особенно важна полнота информации, ну и поиск\добавление\удаление, чтобы ок

hizel ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.