Простые, эффективные в пространстве реализации ассоциативной коллекции в C?

Я ищу ассоциативную коллекцию, которая поддерживает как поиск, так и вставку значений по ключу (удаление не важно), по крайней мере, за время O (Log (N)), и которая имеет очень низкую нагрузку на память как с точки зрения кода Размер и потребление памяти во время выполнения.

Я делаю это для небольшого встроенного приложения, написанного на C, поэтому я стараюсь минимизировать объем требуемого кода и объем используемой памяти.

структура данных с разреженным хешем Google может быть возможной если это не было написано на C ++, и было проще.

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

В настоящее время я использую массив пар ключ /значение, который отсортирован, но вставка O (N). Я не могу помочь, но думаю, что должен быть умный способ улучшить амортизированное время выполнения вставки, например, делая вставки в группах, но у меня нет никакого успеха.

Я думаю, что это должно быть относительно известной проблемой в определенных кругах, поэтому, чтобы сделать это не слишком субъективным, мне интересно, каково наиболее распространенное решение проблемы, указанной выше?

[EDIT:]

Дополнительная информация, которая может иметь отношение к теме:

  • Ключи являются целыми числами
  • Количество значений может быть крошечным от 1 до 2 ^ 32.
  • Шаблоны использования непредсказуемы.
  • Я надеюсь сохранить потребление памяти как можно ниже (например, удвоение требуемого объема памяти не будет идеальным)
4 голоса | спросил cdiggins 6 MarpmSun, 06 Mar 2011 23:37:06 +03002011-03-06T23:37:06+03:0011 2011, 23:37:06

3 ответа


0

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

Если вам нужна хорошая реализация бинарного дерева поиска, которое имеет отличные гарантии производительности и не слишком сложное для кодирования, подумайте о том, чтобы взглянуть на деревья сплайнов. Они гарантируют амортизированный O (lg n) поиск и требуют только двух указателей на узел. Шаг баланса также значительно проще, чем у большинства сбалансированных BST.

ответил templatetypedef 6 MarpmSun, 06 Mar 2011 23:53:29 +03002011-03-06T23:53:29+03:0011 2011, 23:53:29
0

Посмотрите на дерево бинарного поиска и найдите наихудший случай (в котором есть O (n) сложность как для поиска, так и для вставки) используйте сбалансированное дерево .

ответил INS 6 MarpmSun, 06 Mar 2011 23:44:11 +03002011-03-06T23:44:11+03:0011 2011, 23:44:11
0

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

Редактировать: если вы хотите изменить то, что вы делаете сейчас, одна из возможностей - обрабатывать вставки в кластеры: сохранять отсортированный массив и отдельную коллекцию новых вставок. Когда коллекция новых вставок становится слишком большой, объедините эти элементы в основную коллекцию.

Для вторичной коллекции у вас есть несколько вариантов. Вы можете просто использовать несортированный массив и выполнить линейный поиск - и просто ограничить его размер, скажем, log (M), где M - размер основного массива. В этом случае общий поиск остается O (log N), не накладывает никаких накладных расходов на память и сохраняет большинство вставок достаточно быстрыми. Когда вы объединяете коллекции вместе, вы (обычно) хотите отсортировать вторичную коллекцию, а затем объединить с первичной. Это позволяет амортизировать линейное слияние по количеству элементов во вторичной коллекции.

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

ответил Jerry Coffin 6 MarpmSun, 06 Mar 2011 23:54:05 +03002011-03-06T23:54:05+03:0011 2011, 23:54:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132