У меня есть DataTable, который хранит очень скудные данные, что-то вроде:Что является наиболее эффективным способом реализации таблица, в которой хранятся редкие данные в C#
P1 P2 P3 P4 P5 ...
J1 1 1
J2 1 1
J3 1
.
.
.
Число строк и столбцов может достигать более 10^8 ,
Как сохранить эти данные более эффективным способом?
Во-первых, избавитесь от DataTable для этих данных. Его использование памяти здесь огромно.
Если ваши данные всегда равны 0/1, наиболее эффективным способом может быть бит-маска.
Если ваши данные не только 0/1, создайте структуру, которая будет абстрагировать все ваши столбцы.
Вот концептуальный прототип этой структуры данных.
class MyData {
public MyData(int[] columns, object[] data) {
_columns = columns;
_data = data;
}
int[] _columns;
object[] _data;
public object this[int column] {
get {
int index = IndexOf(column);
return index != -1 ? _data[index] : null;
}
}
private int IndexOf(int column) {
for (int i = 0; i < _columns.Length; i++)
if (_columns[i] == column)
return i;
return -1;
}
}
Вы также можете сохранить память для _columns, применив шаблон flyweight.
Надеется, что это помогает
Бит-маски будут более полезными до ~ 12% плотности (игнорируя накладные расходы, связанные с книгами других подходов и имеющие дело только с булевыми). То есть они могут быть хорошими для уплотнения, но сами по себе застревают в O (n), где n - количество столбцов. – 2010-07-22 07:06:34
Если файл на диске система поддерживает Sparse files вы можете создать пустой файл, отметьте его разреженным, а затем изменить его rows * colums * datasize.
Тогда это вопрос о доступе к данным по [строка] [столбец], где смещение может быть рассчитана с:
offset = ((columns.length * (row-1)) + column) * datasize
Существует некоторые накладные расходы с разреженными файлами, а также в отношении распределения, где она, как правило, выделяемых страниц 16-64kb, но в зависимости от того, как ваши кластеры данных могут работать очень хорошо.
Существует много prior art в эффективном хранении запасных матриц.
Общепринятый подход известен как «Список списков». Например, Python имеет эффективный способ хранения запасных матриц как «Row-based linked list sparse matrix».
Вы только сохраняете 1 или другие данные и как вам нужно получить данные после этого? Агрегация, прямой поиск? –
Какая плотность ожидается? Похоже, что это большая матрица со значениями, идущими вниз по диагонали? Может ли он быть оптимизирован для особого случая (например, разрешен ли он?) Или он должен оставаться достаточно общим для «не разреженной» матрицы? – 2010-07-22 07:23:02