Эффективный способ управления 100 предметами в Си с небольшими накладными расходами

Question

Я нахожусь в системе с только приблизительно 512 КБ, доступными для моего приложения (остальное используется для буферов). Мне нужно быть максимально эффективным.

У меня есть около 100 предметов, которые быстро добавляются / удаляются из списка. Какой эффективный способ хранить их в C и есть ли библиотека (с хорошей лицензией), которая поможет? Список никогда не превышает 256 пунктов, а его средний размер составляет 15 пунктов.

• Должен ли я использовать бинарное дерево поиска?
• красное черное дерево

Answer 1

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

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

Answer 2

Я бы использовал двусвязный список.Когда речь идет о десятках или сотнях элементов, поиск не намного медленнее, чем в массиве, и он имеет преимущество в том, что занимает только столько места, сколько ему абсолютно необходимо.Добавление и удаление элементов очень простое и требует очень мало дополнительных затрат.

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

Answer 3

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

Answer 4

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

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

Answer 5

15 элементов, BST должно быть хорошо, если вы можете сохранить их отсортированными, не будучи уверенным, будут ли накладные расходы намного лучше, чем связанный список или массив, если элементы довольно малы. Для многих вставок / удалений я рекомендую связанный список, потому что единственное, что вам нужно сделать, - это указатели исправлений.