Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера

Лекция



Привет, Вы узнаете о том , что такое разреженные массивы, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое разреженные массивы, методы хранения разреженных данных, разреженная матрица, полная матрица, хэширование для получения индекса, выбор метода для хранения разреженных данных , настоятельно рекомендую прочитать все из категории Структуры данных.

Разреженный массив

Одна из наиболее интересных задач программирования — реализация разреженных массивов. Разреженный массив, или разреженная матрица (sparse array), — это массив, в котором не все элементы используются, имеются в наличии или нужны в данный момент. разреженные массивы полезны в тех случаях, когда выполняются два условия: размер массива, который требуется приложению, достаточно большой (возможно, превышает объем доступной памяти), и когда не все элементы массива используются. Таким образом, разреженный массив — это, как правило, большой, но редко заполненный массив. Как будет показано далее, есть несколько способов реализации разреженных массивов. Но перед тем как приступить к их рассмотрению, давайте уделим внимание задачам, которые решаются с помощью разреженных массивов.

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера

  • Зачем нужны разреженные массивы?
  • Представление разреженного массива в виде связного списка
  • Представление разреженного массива в виде двоичного дерева
  • Представление разреженного массива в виде массива указателей
  • Хэширование
  • Выбор метода

Зачем нужны разреженные массивы?

Чтобы понять, зачем нужны разреженные массивы, вспомните следующие два факта:

  • При описании обычного массива в языке С вся память, требуемая для размещения массива, выделяется сразу после его создания.
  • Большие массивы, особенно многомерные, могут занимать огромные объемы памяти.

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

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

Существуют многочисленные примеры приложений, требующих обработки разреженных массивов. Многие из них относятся к работе с матрицами или к научным и инженерным задачам, которые понятны лишь экспертам в соответствующих областях. Однако есть одно очень популярное приложение, в котором обычно применяется разреженный массив — электронная таблица. Несмотря на то, что матрица в средней электронной таблице очень большая, в любой момент времени используется лишь некоторая ее часть. В ячейках электронных таблиц хранятся формулы, значения и строки. При использовании разреженного массива память для каждого элемента выделяется только при необходимости. Поскольку фактически используется лишь небольшая часть элементов массива, весь он (то есть электронная таблица) кажется очень большим, но занимает минимально необходимую память.

В этой главе будут часто повторяться два термина: логический массив и физический массив. Логический массив — это массив, который мыслится как существующий в системе. Например, если матрица электронной таблицы имеет размер 1`000x1`000, то логический массив, реализующий матрицу, также будет иметь размер 1`000x1`000 — даже несмотря на то, что физически такой массив не существует в компьютере. Физический массив — это массив, который реально существует в памяти компьютера. Так, если используются только 100 элементов матрицы электронной таблицы, то для хранения физического массива требуется память, необходимая для хранения лишь этих 100 элементов. Методы обработки разреженных массивов, раскрытые в данной главе, обеспечивают связь между логическими и физическими массивами.

Ниже будут рассмотрены четыре различных способа создания разреженного массива: связанный список, двоичное дерево, массив указателей и хеширование. Несмотря на то, что программа работы с электронными таблицами не разрабатывается целиком, все примеры ориентируются на матрицу электронной таблицы, показанную на рис. 23.1. На этом рисунке элемент X расположен в ячейке В2.

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера

Рис. 23.1. Организация простой электронной таблицы

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера

Представление разреженного массива в виде связного списка

При реализации разреженного массива с помощью связанного списка первым делом необходимо создать структуру, содержащую следующие элементы:

  • Хранимые в ячейке данные
  • Логическая позиция ячейки в массиве
  • Ссылки на предыдущий и следующий элементы

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

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

struct cell {
  char cell_name ;  /* имя ячейки, напр., A1, B34 */
  char  formula[128]; /* информация, напр., 10/B2 */
  struct cell *next;  /* указатель на следующую запись */
  struct cell *prior; /* указатель на предыдущую запись */
} ;

Поле cell_name содержит строку, соответствующую имени ячейки, например, А1, В34 или Z19. Строковое поле formula хранит формулу (данные) из соответствующей ячейки таблицы.

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

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

struct cell *start = NULL; /* первый элемент списка */
struct cell *last = NULL;  /* последний элемент списка */

В большинстве электронных таблиц при вводе формулы в ячейку создается новый элемент разреженного массива. Если электронная таблица построена на основе связанного списка, этот элемент вставляется в список с помощью функции, аналогичной функции dls_store(), приведенной в главе 22. Помните, что список упорядочен по именам ячеек; например, А12 предшествует А13 и т.д.

/* Вставка ячеек в упорядоченный список. */
void dls_store(struct cell *i, /* указатель на вставляемую ячейку */
               struct cell **start, 
               struct cell **last) 
{
  struct cell *old, *p;

  if(!*last) { /* первый элемент в списке */
    i->next = NULL;
    i->prior = NULL;
    *last = i;
    *start = i;
    return;
  }

  p = *start; /* начать с головы списка */

  old = NULL;
  while(p) {
    if(strcmp(p->cell_name, i->cell_name) < 0){
      old = p;
      p = p->next;
    }
    else { 
      if(p->prior) { /* это элемент из середины */
        p->prior->next = i;
        i->next = p;
        i->prior = p->prior;
        p->prior = i;
        return;
      }
      i->next = p; /* новый первый элемент */
      i->prior = NULL;
      p->prior = i;
      *start = i;
      return;
    }
  }
  old->next = i; /* вставка в конец */
  i->next = NULL;
  i->prior = old;
  *last = i;
  return;
}

В приведенной выше функции параметр i — указатель на новую вставляемую ячейку. Параметры start и last являются соответственно указателями на указатели на начало и конец списка.

Нижеследующая функция deletecell() удаляет из списка ячейку, имя которой передается в качестве параметра.

void deletecell(char *cell_name,
            struct cell **start,
            struct cell **last)
{
  struct cell *info;

  info = find(cell_name, *start);
  if(info) {
    if(*start==info) {
      *start = info->next;
      if(*start) (*start)->prior = NULL;
      else *last = NULL;
    }
    else {
      if(info->prior) info->prior->next = info->next;
      if(info != *last)
          info->next->prior = info->prior;
      else
        *last = info->prior;
    }
    free(info); /* освободить системную память */
  }
}

Последняя функция, которая понадобится для реализации разреженного массива на основе связанного списка — это функция find(), находящая указанную ячейку. Для нахождения ячейки данной функции приходится выполнять линейный поиск, но, как было показано в главе 21, среднее количество сравнений при линейном поиске равно n/2, где n — количество элементов в списке. Ниже приведен текст функцииfind():

struct cell *find(char *cell_name, struct cell *start)
{
  struct cell *info;

  info = start;
  while(info) {
    if(!strcmp(cell_name, info->cell_name)) return info;
    info = info->next; /* перейти к следующей ячейке */
  }
  printf("Ячейка не найдена.\n");
  return NULL; /* поиск неудачный */
}

Анализ метода представления в виде связного списка

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

Многие пользователи шутят, что сама Microsoft не знает, сколько же точно занимает ее Excel. Конечно, это только шутка, но лично я иногда думаю, что в ней 100 % правды.

Представление разреженного массива в виде двоичного дерева

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

Чтобы использовать двоичное дерево для реализации электронной таблицы, необходимо изменить структуру cell следующим образом:

struct cell {
  char cell_name ;  /* имя ячейки, напр., A1, B34 */
  char  formula[128]; /* данные, напр., 10/B2 */
  struct cell *left;  /* указатель на левое поддерево */
  struct cell *right; /* указатель на правое поддерево */
} list_entry;

Функцию street() из главы 22 можно модифицировать так, чтобы она строила дерево на основании имени ячейки. В следующем коде предполагается, что параметр n является указателем на вставляемый элемент дерева.

struct cell *stree(
        struct cell *root,
        struct cell *r,
        struct cell *n)
{
  if(!r) {    /* первая вершина поддерева */
    n->left = NULL;
    n->right = NULL;
    if(!root) return n;  /* первый вход в дерево */
    if(strcmp(n->cell_name, root->cell_name) < 0)
      root->left = n;
    else
      root->right = n;
    return n;
  }

  if(strcmp(r->cell_name, n->cell_name) <= 0)
    stree(r, r->right, n);
  else
    stree(r, r->left, n);

  return root;
}

При вызове функции stree() ей необходимо передавать указатели на корень дерева в качестве первых двух параметров и указатель на новую ячейку в качестве третьего. Функция возвращает указатель на корень.

Чтобы удалить ячейку электронной таблицы, можно воспользоваться показанной ниже модифицированной функцией dtree(), принимающей в качестве ключа имя ячейки:

struct cell *dtree(
        struct cell *root,
        char *key)
{
  struct cell *p, *p2;

  if(!root) return root; /* элемент не найден */

  if(!strcmp(root->cell_name, key)) { /* удаление корня */
    /* это означает пустое дерево */
    if(root->left == root->right){
      free(root);
      return NULL;
    }
    /* или если одно из поддеревьев пустое */
    else if(root->left == NULL) {
      p = root->right;
      free(root);
      return p;
    }
    else if(root->right == NULL) {
      p = root->left;
      free(root);
      return p;
    }
    /* или если оба поддерева непустые */
    else {
      p2 = root->right;
      p = root->right;
      while(p->left) p = p->left;
      p->left = root->left;
      free(root);
      return p2;
    }
  }
  if(strcmp(root->cell_name, key)<=0)
    root->right = dtree(root->right, key);
  else root->left = dtree(root->left, key);
  return root;
}

Наконец, для быстрого поиска ячейки электронной таблицы по ее имени можно воспользоваться модифицированной версией функцииsearch().

struct cell *search_tree(
        struct cell *root,
        char *key)
{
  if(!root) return root;  /* пустое дерево */
  while(strcmp(root->cell_name, key)) {
    if(strcmp(root->cell_name, key) <= 0)
      root = root->right;
    else root = root->left;
    if(root == NULL) break;
  }
  return root;
}

Анализ метода представления в виде двоичного дерева

Применение двоичного дерева значительно уменьшает время вставки и поиска элементов по сравнению со связанным списком. Об этом говорит сайт https://intellect.icu . Следует помнить, что последовательный поиск требует в среднем n/2 сравнений, где n — количество элементов списка. По сравнению с этим двоичный поиск требует только log2n сравнений (если дерево сбалансировано). Кроме того, двоичные деревья так же экономно расходуют память, как и связанные списки. Тем не менее, в некоторых ситуациях есть лучшие альтернативы, чем двоичные деревья.

Представление разреженного массива в виде массива указателей

Допустим, что электронная таблица имеет размер 26x100 (от А1 до Z100), то есть состоит из 2`600 элементов. Теоретически можно хранить элементы таблицы в следующем массиве структур:

struct cell {
  char cell_name ;
  char  formula[128];
} list_entry[2600];   /* 2600 ячеек */

Ho 2`600, умноженное на 137 байтов (размер этой структуры в байтах), равняется 356`200 байтов памяти. Это слишком большой объем памяти, чтобы тратить его на не полностью используемый массив. Тем не менее, можно создать массив указателей (pointer array) на структуры типа cell. Для хранения массива указателей требуется намного меньше памяти, чем для массива структур. При каждом присвоении ячейке логического массива данных под эти данные выделяется память, а соответствующему указателю в массиве указателей присваивается адрес выделенного фрагмента. Такая схема позволяет добиться более высокой производительности, чем при связанном списке или двоичном дереве. Описание массива указателей выглядит следующим образом:

struct cell {
  char cell_name ; 
  char formula[128];
} list_entry;

struct cell *sheet[2600]; /* массив из 2600 указателей */

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

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера

Рис. 23.2. Представление разреженного массива в виде массива указателей

Перед использованием массива указателей каждый его элемент необходимо проинициализировать нулем (NULL), что означает отсутствие данной записи. Ниже показана функция инициализации массива:

void init_sheet(void)
{
  register int t;

  for(t=0; t < 2600; ++t) sheet[t] = NULL;
}

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

void store(struct cell *i)
{
  int loc;
  char *p;

  /* вычисление индекса по заданному имени */
  loc = *(i->cell_name) - 'A'; /* столбец */
  p = &(i->cell_name );
  loc += (atoi(p)-1) * 26; /* количество строк * ширина строки +
                              столбец */

  if(loc >= 2600) {
    printf("Ячейка за пределами массива.\n");
    return;
  }
  sheet[loc] = i; /* поместить указатель в массив */
}

При вычислении индекса в функции store() предполагается, что все имена ячеек начинаются с прописной буквы, за которой следует целое число, например, В34, С19 и т.д. Поэтому в результате вычислений по формуле, запрограммированной в функции store(), имя ячейки А1 соответствует индексу 0, имя В1 соответствует индексу 1, А2 — 26 и т.д. Поскольку имена ячеек уникальны, индексы также уникальны и указатель на каждую запись хранится в соответствующей позиции массива. Если сравнить эту процедуру с версиями, использующими связанный список или двоичное дерево, становится понятно, насколько она проще и короче.

Функция удаления ячейки deletecell() также становится очень короткой. При вызове она просто обнуляет указатель на элемент и возвращает системе память.

void deletecell(struct cell *i)
{
  int loc;
  char *p;

  /* вычисление индекса по заданному имени ячейки */
  loc = *(i->cell_name) - 'A'; /* столбец */
  p = &(i->cell_name );
  loc += (atoi(p)-1) * 26; /* количества строк * ширина строки + 
                              столбец */

  if(loc >= 2600) {
    printf("Ячейка за пределами массива.\n");
    return;
  }
  if(!sheet[loc]) return; /* не освобождать, если указатель нулевой
                             (null) */

  free(sheet[loc]);  /* освободить системную память */
  sheet[loc] = NULL;
}

Этот код также намного быстрее и проще, чем в версии со связанным списком.

Процесс поиска ячейки по имени прост, поскольку имя ячейки однозначно определяет индекс в массиве указателей. Поэтому функция поиска принимает следующий вид:

struct cell *find(char *cell_name)
{
  int loc;
  char *p;

  /* вычисление индекса по заданному имени ячейки */
  loc = *(cell_name) - 'A'; /* столбец */
  p = &(cell_name );
  loc += (atoi(p)-1) * 26; /* количества строк * ширина строки + 
                              столбец */

  if(loc>=2600 || !sheet[loc]) { /* эта ячейка пустая */
    printf("Ячейка не найдена.\n");
    return NULL;  /* поиск неуспешный */
  }
  else return sheet[loc];
}

Анализ метода представления разреженного массива в виде массива указателей

Метод реализации разреженного массива на основе массива указателей обеспечивает намного более быстрый доступ к элементам, чем методы на основе связанного списка и двоичного дерева. Если массив не очень большой, выделение памяти для массива указателей лишь незначительно уменьшает объем свободной памяти системы. Тем не менее, в массиве указателей для каждой ячейки выделяется некоторый объем памяти независимо от того, используется она или нет. В некоторых приложениях это может быть ограничением, хотя в общем случае это не является проблемой.

хэширование для получения индекса

Хэширование (hashing) — это процесс получения индекса элемента массива непосредственно в результате операций, производимых над ключом, который хранится вместе с элементом или даже совпадает с ним. Генерируемый индекс называется хэш-адресом (hash). Традиционно хэширование применяется к дисковым файлам как одно из средств уменьшения времени доступа. Тем не менее, этот общий метод можно применить и с целью доступа к разреженным массивам. В предыдущем примере с массивом указателей использовалась специальная форма хэширования, которая называется прямая адресация. В ней каждый ключ соответствует одной и только одной ячейке массива . Другими словами, каждый индекс, вычисленный в результате хэширования, уникальный. (При представлении разреженного массива в виде массива указателей хэш-функция не должна обязательно реализовывать прямую адресацию — просто это был очевидный подход к реализации электронной таблицы.) В реальной жизни схемы прямого хэширования встречаются редко; обычно требуется более гибкий метод. В данном разделе показано, как можно обобщить метод хэширования, придав ему большую мощь и гибкость.

В примере с электронной таблицей понятно, что даже в самых сложных случаях используются не все ячейки таблицы. Предположим, что почти во всех случаях фактически занятые ячейки составляют не более 10 процентов потенциально доступных мест. Это значит, что если таблица имеет размер 260x100 (2`600 ячеек), в любой момент времени будет использоваться лишь примерно 260 ячеек. Этим подразумевается, что самый большой массив, который понадобится для хранения всех занятых ячеек, будет в обычных условиях состоять только из 260 элементов. Но как ячейки логического массива сопоставить этому меньшему физическому массиву? И что происходит, когда этот массив переполняется? Ниже предлагается одно из возможных решений.

Когда пользователь вводит данные в ячейку электронной таблицы (т.е. заполняет элемент логического массива), позиция ячейки, определяемая по ее имени, используется для получения индекса (хэш-адреса) в меньшем физическом массиве. При выполнении хэширования физический массив называется также первичным массивом. Индекс в первичном массиве получается из имени ячейки, которое преобразуется в число, точно так, как и в примере с массивом указателей. Но затем это число делится на 10, в результате чего получается начальная точка входа в первичный массив. (Помните, что в данном случае размер физического массива составляет только 10 % размера логического массива.) Если ячейка физического массива по этому индексу свободна, в нее заносятся логический индекс и данные. Но поскольку 10 логических позиций соответствуют одной физической позиции, могут возникнуть коллизии при вычислении хэш-адресов . Когда это происходит, записи сохраняются в связанном списке, иногда называемом списком коллизий (collision list). С каждой ячейкой первичного массива связан отдельный список коллизий. Конечно, до возникновения коллизии эти списки имеют нулевую длину, как показано на рис. 23.3.

Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера
Рис. 23.3. Пример хэширования

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

В примере хэширования используется массив структур под названием primary:

#define MAX 260

struct htype {
  int index;   /* логический индекс */
  int val;     /* собственно значение элемента данных */
  struct htype *next; /* указатель на следующий элемент с таким же
                         хэш-адресом */
} primary[MAX];

Перед использованием этого массива необходимо его инициализировать. Следующая функция присваивает полю index значение -1 (значение, которое по определению никогда не будет сгенерировано в качестве индекса); это значение обозначает пустой элемент. Значение NULL в поле next соответствует пустой цепочке хэширования .

/* Инициализация хэш-массива. */
void init(void)
{
  register int i;

  for (i=0; i

 

Процедура store() преобразует имя ячейки в хэш-адрес в первичном массиве primary. Если позиция, на которую указывает значение хэш-адрес, занята, процедура автоматически добавляет запись в список коллизий с помощью модифицированной версии функции slstore() из предыдущей главы. Логический индекс также сохраняется, поскольку он понадобится при извлечении элемента. Данные функции показаны ниже:

/* Вычисление хэш-адреса и сохранение значения. */
void store(char *cell_name, int v)
{
  int h, loc;
  struct htype *p;

  /* Получение хэш-адреса */
  loc = *cell_name - 'A'; /* столбец */
  loc += (atoi(&cell_name )-1) * 26; /* строка * ширина + столбец */
  h = loc/10; /* hash */

  /* Сохранить в полученной позиции, если она не занята
     либо если логические индексы совпадают - то есть, при обновлении.
  */
  if(primary[h].index==-1 || primary[h].index==loc) {
    primary[h].index = loc;
    primary[h].val = v;
    return;
  }

  /* в противном случае, создать список коллизий
     либо добавить в енго элемент */
  p = (struct htype *) malloc(sizeof(struct htype));
  if(!p) {
    printf("Не хватает памяти\n");
    return;
  }
  p->index = loc;
  p->val = v;
  slstore(p, &primary[h]);
}

/* Добавление элементов в список коллизий. */
void slstore(struct htype *i,
             struct htype *start)
{
  struct htype *old, *p;

  old = start;
  /* найти конец списка */
  while(start) {
    old = start;
    start = start->next;
  }
  /* связать с новой записью */
  old->next = i;
  i->next = NULL;
}

Для того чтобы получить значение элемента, программа должна сначала вычислить хэш-адрес и проверить, совпадает ли с искомым логический индекс, хранящийся в полученной позиции физического массива. Если совпадает, возвращается значение ячейки; в противном случае — производится поиск в списке коллизий. Функция find(), выполняющая эти задачи, показана ниже:

/* Вычисление хэш-адреса и получение значения. */
int find(char *cell_name)
{
  int h, loc;
  struct htype *p;

  /* получение значения хэш-адреса */
  loc = *cell_name - 'A'; /* столбец */
  loc += (atoi(&cell_name )-1) * 26; /* строка * ширина + столбец */
  h = loc/10;

  /* вернуть значение, если ячейка найдена */
  if(primary[h].index == loc) return(primary[h].val);
  else { /* в противном случае просмотреть список коллизий */
    p = primary[h].next;
    while(p) {
      if(p->index == loc) return p->val;
      p = p->next;
    }
    printf("Ячейки нет в массиве\n");
    return -1;
  }
}

Создание функции удаления оставлено читателю в качестве упражнения. (Подсказка: Просто обратите процесс вставки.)

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

Анализ метода хэширования

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

Иными словами, хэш-функция является биекцией.

Т.е. ситуации, когда разным ключам k1≠k2 соответствует один и тот же хэш-адрес: h(k1)=h(k2) (здесь h — хэш-функция).

Цепочка хэширования (hash chain) — цепочка, соединяющая элементы хэш-таблицы с одним и тем же хэш-кодом. Ранее автор назват ее списком коллизий (collision list). Иногда она называется также пакетом переполнения.

Разреженная матрица

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

Разреженная матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевые, матрица считается плотной.

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разреженной. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов :

  • есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
  • в каждой строке не превышает 10 в типичном случае;
  • ограничено Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера, где Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера.
  • таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей .

Огромные разреженные матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.

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

Представление

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

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

Словарь по ключам(DOK - Dictionary of Keys)

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

Список списков(LIL - List of Lists)

строится как список строк, где строка это список узлов вида (столбец, значение).

Список координат(COO - Coordinate list)

хранится список из элементов вида (строка, столбец, значение).

Сжатое хранение строкой(CSR - compressed sparse row, CRS - compressed row storage, Йельский формат)

Мы представляем исходную матрицу Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера, cодержащую Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера ненулевых значений в виде трех массивов:

  • массив значений - массив размера Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера, в котором хранятся ненулевые значения взятые подряд из первой непустой строки, затем идут значения из следующей непустой строки и т.д.
  • массив индексов столбцов - массив размера Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера и хранит номера столбцов, соответствующих элементов из массива значений.
  • массив индексации строк - массив размера Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера(кол_во_строк + 1), для индекса Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера хранит количество ненулевых элементов в строках до Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера включительно, стоит отметить что последний элемент массива индексации строк совпадает с Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера, а первый всегда равен Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера.первой

Примеры:

Пусть Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера, тогда

массив_значений          = {1, 2, 4, 2, 6}
массив_индексов_столбцов = {0, 1, 1, 1, 2}
массив_индексации_строк  = {0, 2, 3, 5} -- в начале хранится 0, как запирающий элемент

Пусть Разреженные массивы и матрицы. Назначение, методы хранения в памяти компьютера, тогда

массив_значений          = {1, 2, 3, 4, 1, 11}
массив_индексов_столбцов = {0, 1, 3, 2, 1,  3}
массив_индексации_строк  = {0, 3, 4, 6} -- в начале хранится 0, как запирающий элемент

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

void smdv(const crsm *A, double *b, const double *v) // b += Av
{
    // crsm это структура {int n, int m, int nnz, double aval[], double aicol[], double airow[]};
	for(int row = 0; row < n; ++row)
		for(int i = A->airow[row]; i < A->airow[row+1]; ++i)
			b[row] += A->aval[i] * v[A->aicol[i]];
}

Сжатое хранение столбцом(CSС - compressed sparse column, CСS - compressed column storage)

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

выбор метода для хранения разреженных данных

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

Если логический массив заполнен очень редко, самыми эффективными по использованию памяти оказываются связанные списки и двоичные деревья, поскольку в них память выделяется только для тех элементов, которые действительно используются. Для самих связей требуется очень небольшой дополнительный объем памяти, которым обычно можно пренебречь. Представление в виде массива указателей предполагает создание целиком всего массива из указателей, даже если некоторые элементы не используются. При этом в памяти должен не только поместиться весь массив, но еще должна остаться свободная память для работы приложения. В некоторых случаях это может быть серьезной проблемой. Обычно можно заранее оценить примерный объем свободной памяти и решить, достаточен ли он для вашей программы. Метод хэширования занимает промежуточное место между представлениями с помощью массива указателей и связанного списка или двоичного дерева. Несмотря на то, что весь первичный массив, даже если он не используется, должен находиться в памяти, этот массив все равно будет меньше, чем массив указателей.

Если логический массив будет заполнен довольно плотно, ситуация существенно меняется. В этом случае создание массива указателей и хэширование становятся более приемлемыми методами. Более того, время поиска элемента в массиве указателей постоянно и не зависит от степени заполнения логического массива. Хотя время поиска при хэшировании и не постоянно, оно ограничено сверху некоторым небольшим значением. Но в случае связанного списка и двоичного дерева среднее время поиска увеличивается по мере заполнения массива. Это следует помнить, если время доступа является критическим фактором.

Библиотеки программ для работы с разреженными данными

Для вычислений с разреженными матрицами создан ряд библиотек для различных языков программирования, среди них:

  • SparseLib++ (C++)
  • uBLAS (C++, в составе Boost)
  • SPARSPAK (Фортран)
  • CSparse (Си)
  • Модуль Sparse из библиотеки SciPy (Python

Вау!! 😲 Ты еще не читал? Это зря!

  • Матричное представление
  • Принцип Парето
  • Рваная матрица (нерегулярная матрица)
  • Однократная матрица
  • Матрица горизонта
  • Код разреженного графа
  • Разреженный файл
  • Формат файлов Harwell-Boeing
  • Форматы обмена Matrix Market
  • Матрица переменной полосы
  • ленточная матрица

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

создано: 2016-05-01
обновлено: 2023-06-11
132732



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Структуры данных

Термины: Структуры данных