Думаю, многим хорошо знаком класс DataTable. Вычитывая из БД на клиент большие таблицы через ADO.NET, иногда приходится продлевать время жизни экземпляров этого класса на продолжительное время. Например, если нужна обработка и анализ полученных данных, не прибегая к ORM материализации. Когда объём данных невелик, то особой проблемы с этим не возникает. Однако на широких таблицах с большим числом строк можно получить довольно толстые объекты в памяти. Сопоставив объём данных, приходящих из БД, и размер получаемого DataTable, можно прийти к двум выводам:
- При больших объёмах varchar данных, среди которых есть дублирование, можно попробовать организовать некое подобие интернирования строковых данных внутри DataTable;
- DataTable содержит довольно увесистую внутреннюю инфраструктуру. Манипулируя с типами данных и числом строк в таблице, удалось установить, что процент накладных расходов составляет 15-20% для таблиц от 100 тыс. записей. Большая часть инфраструктуры обеспечивает корректное редактирование и прочий функционал таблицы. В случае, когда вам требуется, чтобы DataTable был простым контейнером для данных, полученных из БД, то можно написать лёгкий выпотрошенный аналог этого класса.
Вопрос замены DataTable на внутреннюю структуру рассмотрим в следующей статье, если будет интересно. А сейчас рассмотрим первый пункт. Как известно, интернирование строк заключается в устранении дубликатов string в памяти (подробнее можно почитать тут). Использовать встроенный механизм интернирования мы не будем, чтобы строки не висели в памяти процесса после того, как они перестанут быть нам нужны.
Идея состоит в том, чтобы обойти все varchar-колонки в таблице, и в каждой колонке все дубликаты заменить на ссылку из временного словаря, в котором строки будут лежать в единственном экземпляре. Состояние кучи до и после будут такими:
Стоит отметить, что данные в DataTable хранятся в колонках, а не в строках, как можно было бы предположить. Это обусловлено меньшими затратами по памяти – т.к. в колонках все значения одного типа, и можно использовать для хранения обычные массивы с постоянным временем доступа по индексу. Для скорости, будем читать напрямую из этих массивов через отражение (FieldInfo).
// Приватные поля, используемые для оптимизации потребления таблицей памяти и быстрого доступа к данным private static readonly FieldInfo StorageField = typeof (DataColumn).GetField("_storage", BindingFlags.Instance | BindingFlags.NonPublic); private static readonly FieldInfo ValuesField = typeof (DataTable).Assembly.GetType("System.Data.Common.StringStorage") .GetField("values", BindingFlags.Instance | BindingFlags.NonPublic); Как я упомянул выше, для хранения экземпляров строк в единственном экземпляре в памяти будем использовать Dictionary.
var exclusiveStrings = new Dictionary<string, string>(); Key нужен будет только для хэша, Value – для ссылки на единственный экземпляр в памяти. Стоит отметить, что возникающие коллизии Dictionary разруливает с помощью метода корзин.
Полный код метода:
/// <summary> /// Оптимизация таблицы по использованию памяти. По сути делает интернирование строк в рамках таблицы. /// </summary> /// <param name="table">Таблица.</param> /// <returns>Ссылка на себя.</returns> public static DataTable Compact(this DataTable table) { if (table.Rows.Count == 0) return table; var exclusiveStrings = new Dictionary<string, string>(); for (int column = 0; column < table.Columns.Count; ++column) { if (table.Columns[column].DataType == typeof(string)) { // Прямой доступ к массиву (вертикальное хранилище) var values = (string[])ValuesField.GetValue(StorageField.GetValue(table.Columns[column])); int rowCount = table.Rows.Count; for (int row = 0; row < rowCount; ++row) { var value = values[row]; if (value != null) { string hashed; if (!exclusiveStrings.TryGetValue(value, out hashed)) // строка встречается впервые exclusiveStrings.Add(value, value); else // дубликат values[row] = hashed; } } exclusiveStrings.Clear(); } } return table; } Оценим сложность получившегося алгоритма для конкретной колонки. Сложность в данном случае складывается из двух основных частей: обход всех n значений и поиска в Dictionary по ключу. С первой частью всё понятно, а вот с поиском чуть интереснее. В самом фантастически плохом случае, когда все n значений приведут к коллизии и лягут в одну корзину, сложность поиска сведётся к линейной. Но, учитывая реализацию хэш-функции для строки в .NET, ничего кроме улыбки эта мысль вызвать не может. Так же решили и разработчики Dictionary, т.к. в документации для TryGetValue заявлена сложность O(1). Таким образом, в рамках одной колонки ожидаемая сложность сводится к O(n). Для всей таблицы – O(mn), где m – число строковых колонок.
Рассмотрим скорость на реальных данных:
Как видно сложность линейная, как и следовало из анализа алгоритма. Касательно затрат памяти, то для алгоритма на каждом шагу, наполняя словарь, создаёт новый указатель и удаляет ссылки на строки, если находит дубликат.
Несложно заметить, что эффективность алгоритма зависит от входных данных: если дубликатов много, то и памяти освободится больше. В моих задачах память сокращалась на 30-50%. Но, повторюсь, у вас может быть иначе.
Надеюсь, кому-то это решение окажется таким же полезным, как и мне.
ссылка на оригинал статьи http://habrahabr.ru/post/259069/
Добавить комментарий