Вопрос о структуре данных
У меня есть таблица базы данных с большим количеством строк и одним числовым столбцом, и я хочу представить эти данные в памяти. Я мог бы просто использовать один большой целочисленный массив, и это было бы очень быстро, но количество строк могло быть слишком большим для этого.
Большинство строк (более 99%) имеют нулевое значение. Есть ли эффективная структура данных, которую я мог бы использовать, которая выделяла бы память только для строк с ненулевыми значениями и была бы почти такой же быстрой, как массив?
Обновление: в качестве примера я попробовал создать Hashtable, читая исходную таблицу и добавляя любые ненулевые значения с ключом по номеру строки в исходной таблице. Я получил значение с помощью функции, которая вернула 0, если запрошенный индекс не был найден, или значение в Hashtable. Это работает, но медленно, как грязь, по сравнению с обычным массивом - возможно, я делаю это неправильно.
Обновление 2: вот пример кода.
private Hashtable _rowStates;
private void SetRowState(int rowIndex, int state)
{
if (_rowStates.ContainsKey(rowIndex))
{
if (state == 0)
{
_rowStates.Remove(rowIndex);
}
else
{
_rowStates[rowIndex] = state;
}
}
else
{
if (state != 0)
{
_rowStates.Add(rowIndex, state);
}
}
}
private int GetRowState(int rowIndex)
{
if (_rowStates.ContainsKey(rowIndex))
{
return (int)_rowStates[rowIndex];
}
else
{
return 0;
}
}
Мне нужно иметь доступ к данным по индексу исходной строки (т.е. номеру строки в таблице). Поэтому мне нужно что-то, к чему можно получить доступ, например, к массиву. GetNum (индекс строки).
Как насчет хеша для ненулевых значений?
См. Выше. Я пробовал, но медленно.
Ответы 8
Это пример структуры данных редкий, и есть несколько способов реализовать такие разреженные массивы (или матрицы) - все зависит от того, как вы собираетесь их использовать. Две возможные стратегии:
- Храните только ненулевые значения. Для каждого элемента, отличного от нуля, хранится пара (индекс, значение), все остальные значения по умолчанию равны нулю. Вам также нужно будет сохранить общее количество элементов.
- Сжимайте последовательные нулевые значения. Сохраните количество пар (количество, значение). Например, если у вас в строке 12 нулей, за которыми следуют 200 и еще 22 нуля, сохраните (12, 0), (1, 200), (22, 0).
Как именно вы не хотите это реализовывать, зависит от ваших требований, это компромисс между памятью и скоростью. Чистый целочисленный массив является самым быстрым с поиском постоянной сложности.
Использование коллекции на основе хэшей, такой как Hashtable или Dictionary (Hashtable кажется медленнее, но потокобезопасным - как указывали другие), даст вам очень низкое использование памяти для такой разреженной структуры данных, как ваша, но может быть несколько дороже, когда выполнение поисков. Вы храните пару "ключ-значение" для каждого индекса и ненулевого значения.
Вы можете использовать ContainsKey, чтобы узнать, существует ли ключ, но гораздо быстрее использовать TryGetValue для проверки и получения данных за один раз. Для плотных данных может быть полезно перехватить исключения для отсутствующих элементов, поскольку это повлечет за собой затраты только в исключительном случае, а не при каждом поиске.
Отредактировал очередной раз, так как я запутался - это научит меня публиковать сообщения, когда мне нужно спать.
Ключом может быть то, что Dictionary не является потокобезопасным. Попробуйте заменить его на свой Hashtable.
ContainsKey просматривает всю коллекцию? Звучит неправильно.
Хех, я немного запутался ... но я обнаружил, что вам действительно стоит использовать TryGetValue, так как это намного быстрее.
Создайте целочисленный массив для ненулевых значений и индикаторов хранения битового массива, если конкретная строка содержит ненулевое значение.
Затем вы можете найти необходимый элемент в первом массиве, суммируя биты во втором массиве, начиная с 0 до позиции индекса строки.
Я ожидал, что карта / словарь / хеш-таблица ненулевых значений должна быть быстрым и экономичным решением.
В Java использование класса Hashtable приведет к блокировке, поскольку предполагается, что он является потокобезопасным. Возможно, что-то подобное замедлило вашу реализацию.
--- обновление: использование Google-fu предполагает, что C# Hashtable делает несет накладные расходы на безопасность потоков. Вместо этого попробуйте словарь.
Спасибо за гугл фу. По иронии судьбы, я изменил свою коллекцию со словаря на Hashtable, потому что думал, что это ускорит процесс. Хорошо, что я делал то, где проблема со скоростью была очевидна.
Однако мне пришлось выбросить словарь и вернуться к простому массиву. Я не мог заставить его работать достаточно быстро.
Трудно понять, как использование Hashtable повлечет за собой накладные расходы, которых нет в Dictionary, поскольку базовая коллекция Dictionary является является Hashtable.
@Robert: если вы протестируете приведенный выше образец, а затем измените его для использования словаря, вы увидите, что он значительно ускоряется (если я не облажался с тестированием).
Я думаю, что они оба используют базовую хеш-таблицу, но и Hashtable, и Dictionary обертывают ее, причем первый так, что делает его поточно-ориентированным, но более медленным.
Я не уверен в эффективности этого решения, но вы можете попробовать. Так что это зависит от того, в каком сценарии вы будете его использовать, но я напишу здесь два из них, которые я имею в виду. Первое решение: если у вас есть только одно поле целых чисел, вы можете просто использовать общий список целых чисел:
List<int> myList = new List<int>();
Второй почти такой же, но вы можете создать список своего типа, например, если у вас есть два поля, счетчик и ненулевое значение, вы можете создать класс, который будет иметь два свойства, а затем вы можете создать список ваш класс и хранить в нем информацию. Но вы также можете попробовать общие связанные списки. Итак, код для решения два может быть таким:
public class MyDbFields
{
public MyDbFields(int count, int nonzero)
{
Count = count;
NonZero = nonzero;
}
public int Count { get; set; }
public int NonZero { get; set; }
}
Затем вы можете создать такой список:
List<MyDbFields> fields_list = new List<MyDbFields>();
а затем заполните его данными:
fields_list.Add(new MyDbFields(100, 11));
Я не уверен, что это полностью поможет вам решить вашу проблему, но это всего лишь мое предложение.
Если я правильно понимаю, вы не можете просто выбрать ненулевые строки, потому что для каждого индекса строки (также известного как значение PK) ваша структура данных должна будет сообщать не только значение, но и то, есть ли оно вообще. Поэтому предположение 0, если вы не найдете его в своей структуре данных, может быть не очень хорошей идеей.
Просто чтобы убедиться - сколько именно строк мы здесь говорим? Миллионы? Миллион целых чисел займет всего 4 МБ ОЗУ в качестве массива. На самом деле не так уж и много. Я думаю, это должно быть не менее 100 000 000 строк.
В принципе, я бы предложил отсортированный массив пар целых чисел для хранения ненулевых значений. Первым элементом в каждой паре будет значение PK, и именно по нему будет сортироваться массив. Вторым элементом будет значение. Конечно, вы можете сделать выборку БД, которая возвращает только эти ненулевые значения. Поскольку массив будет отсортирован, вы сможете использовать двоичный поиск, чтобы найти свои значения.
Если в значениях PK нет «дыр», то единственное, что вам может понадобиться, помимо этого, - это минимальное и максимальное значения PK, чтобы вы могли определить, принадлежит ли данный индекс вашему набору данных.
Если между использованными значениями PK есть неиспользуемые, то вам нужен другой механизм, чтобы определить, какие значения PK действительны. Возможно, битовая маска или другой массив действительных (или недопустимых, в зависимости от того, что меньше) значений PK.
Если вы выберете способ битовой маски, есть другая идея. Используйте два бита для каждого значения PK. Первый бит покажет, действительно ли значение PK. Второй бит покажет, равен он нулю или нет. Сохраните все ненулевые значения в другом массиве. Однако это будет иметь недостаток, заключающийся в том, что вы не будете знать, какой элемент массива соответствует какой записи битовой маски. Чтобы выяснить это, вам придется считать с самого начала. Это можно смягчить с помощью некоторых индексов. Скажем, для каждых 1000 записей в массиве значений вы сохраняете другое целое число, которое сообщает вам, где эта запись находится в битовой маске.
Я нацелился на пару миллионов. 4-8 МБ - это немного для ПК, но для Windows Mobile (я не упомянул WM в вопросе, потому что здесь это не совсем актуально), у которого есть ограничение в 32 МБ на процесс.
Вы платите штраф за бокс, используя Hashtable. Попробуйте переключиться на Dictionary<int, int>. Кроме того, о скольких строках идет речь - и как быстро это вам нужно?
Возможно, вы ищете неправильную область - все, что вы сохраняете для каждого значения, - это номер строки в строке базы данных, что говорит о том, что, возможно, вы просто используете это для извлечения строки? Почему бы не попробовать проиндексировать вашу таблицу по числовому столбцу - это обеспечит молниеносный доступ к строкам таблицы для любого заданного числового значения (что, кажется, является конечной целью здесь?) Если это все еще слишком медленно, вы можете переместить сам индекс в память и т. д. Я хочу сказать, что ваша база данных может решить эту проблему более элегантно, чем вы.
Извините, на самом деле здесь нет базы данных - я вставил это, пытаясь объяснить проблему. Это чисто проблема структуры данных в памяти.
Почему вы не можете просто выбрать строки из базы данных, которые имеют ненулевое значение, и сохранить их в массиве?