какой из них использовать связанный список или статические массивы?

Question

У меня есть структура на C, которая напоминает структуру таблицы базы данных. Теперь, когда я запрашиваю таблицу, используя select, я не знаю, сколько записей я получу. Я хочу сохранить все возвращенные записи из запроса select в массиве с типом данных моей структуры.

Какой метод лучше?

Метод 1: найти размер массива и выделить

1. сначала получите количество записей, выполнив команду select count (*) из таблицы
2. выделить статический массив
3. запустить select * from table и затем сохранить каждую запись в моей структуре в цикле.

Способ 2: использовать один связанный список

while ( records returned )
{
    create new node 
    store the record in node 
}

Какая реализация лучше?

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

Спасибо

Answer 1

И я забыл вариант № 4. Выделите массив фиксированного размера. Когда этот массив заполнен, выделите другой. Вы можете отслеживать массивы, связывая их в связанном списке или имея массив более высокого уровня, который сохраняет указатели на массивы данных. Эта двухуровневая схема хороша, когда вам нужен произвольный доступ, вам просто нужно разбить ваш индекс на две части.

Answer 2

Вы забыли вариант 3, он немного сложнее, но может быть лучше для вашего конкретного случая. Так обычно делают в C ++ std :: vector.

Выделите массив любого удобного размера. Когда этот массив заполнен, выделите новый больший массив от 1,5x до 2x размера заполненного, затем скопируйте заполненный массив в этот. Освободите исходный массив и замените его новым. Вспенить, промыть, повторить.

Answer 3

Проблема с 'select count (*)' заключается в том, что значение может изменяться между вызовами, поэтому ваш "реальный" выбор будет иметь количество элементов, отличное от ожидаемого количества.

Я думаю, что лучшим решением является ваша "2". Вместо связанного списка, я бы лично выделил массив (перераспределяя при необходимости). Это проще в языках, которые поддерживают растущие массивы (например, std::vector<myrecord> в C ++ и List<myrecord> в C #).

Answer 4

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

Это выглядит как решение по проекту, которое может измениться по мере развития вашего приложения, поэтому вам определенно следует скрыть представление за подходящим API . Если вы еще не знаете, как это сделать, код Хансона даст вам несколько хороших примеров.

Answer 5

while(record = get_record()) {
  records++;
  records_array = (record_struct *) realloc(records_array, (sizeof record_struct)*records);
  *records_array[records - 1] = record;
}

Это строго пример & mdash; пожалуйста, не используйте realloc () в производстве.

Answer 6

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

Это способ, которым Java и другие языки делают это. Внутренне, это даже, как Perl реализован в C.

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

Answer 7

Есть много возможных критических замечаний, которые следует сделать.

1. Вы вообще не говорите о статическом массиве - статический массив будет иметь заранее определенный размер, фиксированный во время компиляции, и локальный для исходного файла или локальный для функции. Вы говорите о динамически размещаемом массиве.

2. Вы не даете никаких указаний ни на размер записи, ни на количество записей, ни на то, насколько динамичной является база данных внизу (то есть любой другой процесс может изменить какие-либо данные во время работы вашей). Информация о размерах не очень важна, но есть и другой фактор. Если вы делаете какой-то отчет, тогда загрузка данных в память - это нормально; Вы не собираетесь изменять базу данных, и данные являются точным снимком. Однако, если другие люди могут изменять записи, когда вы изменяете записи, ваше схематичное решение является важным примером того, как можно потерять обновления других людей. Это ПЛОХАЯ вещь!

3. Зачем вам все данные в памяти одновременно? Не обращая внимания на ограничения по размеру, что именно дает преимущество по сравнению с обработкой каждой соответствующей записи один раз в правильной последовательности? Видите ли, СУБД приложила много усилий для того, чтобы иметь возможность выбирать соответствующие записи (предложения WHERE) и соответствующие данные (списки SELECT) и позволять вам указать последовательность (предложения ORDER BY), и у них есть лучшие системы сортировки, которые они могут позволить себе (лучше, чем те, которые вы или я, вероятно, произведем).

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

5. Массовое извлечение (также упомянутое Марком Рэнсомом) также полезно. Вы хотели бы предварительно выделить массив, в который извлекается массовая выборка, чтобы вам не пришлось делать дополнительное копирование. Это просто линейное поведение, поэтому оно менее серьезно.