Разреженный массив в C! Как это сделать? Могу ли я выделить только части массива?

Question

Первый вопрос: «Как создать простой разреженный массив в C (только с одним измерением)?» {своими руками, без библиотек.}

И последнее: «Могу ли я выделить только части массива?»

как * массив;

затем используйте malloc для выделения некоторого mem для этого; Итак, мы освобождаем индекс, который нам не нужен.

Могу ли я это сделать?

Большое спасибо!

Answer 1

Нет, вы не можете это сделать.

Что вы можете сделать, так это распределить блоки, но вы должны тщательно их спроектировать.

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

struct SparseBlock
{
  void *blockData;
  int beginIndex;
  int endIndex;
  struct SparseBlock *next;
}

очевидно, если endIndex - beginIndex = 0 у вас есть одна ячейка (которая изолирована внутри массива), в противном случае у вас есть блок ячеек, позволяющий вам выделить для нее нужное количество памяти.

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

• реструктуризация блоков при заполнении или создании отверстия
• просто хранить отдельные ячейки

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

Решений много, просто проявите свое творчество! :)

Answer 2

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

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