LINUX.ORG.RU

Ассоциативный массив на С, где ключ-строка


0

1

Доброго всем дня!

Есть рабочая програмка, написанная на С. Со временем понадобилось добавление функции, которая требует построения массива с ключем-строкой. Очень уж не хочется перекладывать на С++ и использовать STL. Запросто можно накидать функцию сравнения строк, но массив очень большой-десятки тысяч элементов, и линейный поиск будет тормозным, похоже, нужно использовать деревья.
Есть ли какие-нибудь Сишные библиотеки алгоритмов?

Спасибо!

упомянутый уже glib и классический #include <search.h> с его hsearch tsearch :)

MKuznetsov ★★★★★ ()

Взять sys/tree.h из BSD.

Reset ★★★★★ ()

стандартнейшая задача
получаеш с строки - через какую нить функцию ее хеш
и по хешу заносиш ее в базу

а база - массив указателей на список элементов в один и темже хешом

ae1234 ★★ ()

Если lookup существенно преобладает над insert'ом, можно обойтись динамическим массивом с пузырьком и bsearch. А тащить glib ради хеша.. ну не знаю, есть варианты попроще.

anonymous ()

Про GLib на ibm гдето в статьях или где там ищи, там несколько статей

jeuta ★★★★ ()

Посмотрел здесь http://uthash.sourceforge.net/userguide.html и вроде все устраивает: сделано как *.h-файл, в котором прописан ряд макросов. Попробовал-никакой головной боли. Хэширует по строкам (не нужно самому заморачиваться с операциями сравнения), по целым числам и указателям.

Что можете сказать о надежности?
Мож кто использовал?

nitroxolyne ()

rtfm hashing, hash table и т.п.

anonymous ()

А что, уже нереально сложно написать красно-черное дерево, 2-3 дерево или хотя бы обычное несбалансированное бинарное дерево поиска?

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

Что можете сказать о надежности?
Мож кто использовал?

да вроде довольно таки стабильная либа, просто работает

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

А что, уже нереально сложно написать красно-черное дерево, 2-3 дерево или хотя бы обычное несбалансированное бинарное дерево поиска?

если не стоит задача научиться - это лишнее, проще взять проверенный вариант

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

Да. Но на то, чтобы получить достойный ответ на ЛОРе и использовать его на практике, уйдет намного больше времени, чем на написание меньше 50 строк кода обычного или рандомизированого бинарного дерева поиска. Поэтому в данном случае от уже написаного решения профита не будет.

PS. Решения данной задачи легко нагугливаются, а уже готовые реализации бинарных деревьев и хэшей легко ищутся в pastebin и gist.

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

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

А вообще вчем проблемма glib статиком вкомпитить и отстрипать потом?

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

Что можете сказать о надежности?

Мож кто использовал?

Там нужно круто извратится, чтобы сделать эту штуку ненадежной...

Deleted ()

Если массив редкоменяющийся - то тупо qsort и половинный поиск.

Второй вариант - считаем хеш (ну например, ксорим по 4 байта строки, затем берём остаток от деления на 1000). Соответственно, строим массив из 1000 элементов. в каждой ячейке - связанный список строк (в твоем варианте - несколько десятков строк).

Кароче, сильно зависит от задачи и требуемого быстродействия.

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

Да. Но на то, чтобы получить достойный ответ на ЛОРе и использовать его на практике, уйдет намного больше времени, чем на написание меньше 50 строк кода обычного или рандомизированого бинарного дерева поиска. Поэтому в данном случае от уже написаного решения профита не будет.

поэтому надо задавать вопрос заранее :) а пока заниматься текущими делами

просто иногда ломает велосипед писать, ну ладно там какое-нибудь хитро-специальное дерево, но когда 100500 раз реализованный велосипед.... короче, можно boost переписывать, но проще использовать :) хотя, это зависит

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

А вообще вчем проблемма glib статиком вкомпитить и отстрипать потом?

Это не ко мне, а к ТСу. Я бы тоже заюзал glib.

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

Раз критично к производительности в худшем случае, то зачем выбирать именно хэш-таблицы? Они не дают никакой гарантии производительности (в худшем случае сложность поиска O(N), что очень плохо). Я бы юзал красно-черные деревья или другие сбалансированные деревья (гарантируется, что в худшем случае сложность поиска O(log(N))).

Deleted ()

Как уже сказали - бинарный поиск. Посмотри реализацию. Это раз. Во вторых - хэшмапа. Тоже можно несложным образом сделать. В третьих - специально для тебя могу подсказать книгу: Исскуство программирования на C. Думаю там ты найдешь что тебе надо и в простом для понимания языке.

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

поэтому надо задавать вопрос...

Гуглу. На поиск готового кода в данном случае тратится меньше времени, чем, я думаю, ушло на написание первого поста. И вариант лучше любого велосипеда.

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

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

это означает что про hello world спрашивать неэффективно, но про что-то сложное могут и подсказать довольно таки ловко :)

а ещё есть «срач», в результате которого вообще самые невероятные штуки могут выясниться

shty ★★★★★ ()

Сделай биндинги к питону, там есть хеш-таблицы.

AST-PM-105 ()

чем Вас плюсы ты не устраивают?

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