| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Методы хранения сильно разреженных матриц
Xandr001 © (2008-09-08 09:19:00)В общем такая ситуация. Есть массив
var
Kad_number: Array[1..99, 0..99, 0..99, 1..99, 1..9999] of Integer;
Он очень разрежен (ок 200 000 записей), но сохранить размерность необходимо. Загружается динамически при открытии файла - справочника. Всё это жрёт больше 2х гигов памяти. Не компилирутся даже...
вот вопрос: есть ли какие-то способы хранения этого добра не выделяя память под весь массив, а только под заполненные ячейки?
Нашёл в сети 1 способ, там создаются отдельные массивы/строки для каждого из измерений массива, в которых записываются индексы ненулевых элементов, и 1 массив/строка в кот. хранятся сами значения ненулевых элементов.
Этот способ мне не подходит, потому что мне необходим прямой доступ к каждому элементу. То есть при поступлении на вход строки типа: "05:01 03 45:0567" мне нужно сразу узнать значение элемента Kad_number[5,1,3,45,567].
MBo (2008-09-08 15:11:00) [21]Хэш таблица - строка "05:01 03 45:0567" или набор индексов 5,1,3,45,567 отображается на число в небольшом диапазоне (например для 200 тыс записей - 0..262143, или побольше, чтобы уменьшить число конфликтов), это число и будет индекс в массиве хэш-таблицы (без учета конфликтов, которых будет немного, полностью их избежать можно с использованием идеального хэширования, что здесь допустимо, поскольку таблица статичная)
int64 (2008-09-08 15:09:00) [22]Xandr001 (08.09.08 09:19)
Непонятно, что ты подразумеваешь под "прямой доступ к каждому элементу".
Xandr001 (2008-09-08 14:57:00) [23]Товарищи! Есть мнение что мне не так преподавали теорию хеш таблиц...
Можно в двух словах о том, что вы понимаете под хешем и хеш таблицей?
Anatoly Podgoretsky (2008-09-08 13:56:00) [24]> han_malign (08.09.2008 13:47:18) [18]
У тебя двоичный хеш, у меня строковый
han_malign (2008-09-08 13:47:00) [25]
> Итого шесть байт
10^12(980001990000) - это пять байт...
Anatoly Podgoretsky (2008-09-08 11:58:00) [26]
> Вы вообще можете вообразить себе какого размера получится
> хеш-таблица???
200 000 * размер хеша - короче немного.
1..99 - 1
0..99 - 1
0..99 - 1
1..99 - 1
1..9999 - 2
Итого шесть байт = 1.2 мб
Xandr001 (2008-09-08 10:59:00) [27]
> При грамотном подходе
Ну значит буду искать этот грамотный подход.
Сергей М. (2008-09-08 10:36:00) [28]
> будет ли работа с БД укладываться в эти временные рамки
При грамотном подходе - да.
Xandr001 (2008-09-08 10:34:00) [29]
> И что ?
Это видимо мне... Извините. Просто не договорил.
Вот что: для каждой строки выходной таблицы нужно найти строку в справочнике, потом 2 операции присвоения, следущая строка. Мне интересно будет ли работа с БД укладываться в эти временные рамки
Сергей М. (2008-09-08 10:12:00) [30]И что ?
MBo (2008-09-08 10:11:00) [31]>Вы вообще можете вообразить себе какого размера получится хеш-таблица???
Примерно в полтора-два раза больше, чем данных фактически имеется ;)
Однако с БД проще.
Xandr001 (2008-09-08 10:04:00) [32]
> Но у тебя вряд ли есть выбор)
:)
Дело в том, что из этой бд нужно заполнять выходную табличку, в которой около 70 тысяч записей. и это нужно выполнять для разного набора выходных таблиц. ограничение по времени - максимум 2 минуты на 1 выходную таблицу...
Сергей М. (2008-09-08 09:59:00) [33]
> долго ли будет выполняться sql запрос
Это зависит от многих факторов.
Но у тебя вряд ли есть выбор)
Медвежонок Пятачок (2008-09-08 09:57:00) [34]быстро. не успеешь зевнуть.
Xandr001 (2008-09-08 09:56:00) [35]Или есть возможность делать n-мерные таблицы???
Xandr001 (2008-09-08 09:47:00) [36]
> может к БД присмотришься?
> Если нужен только доступ, то обычно используют базу данных
> с индексами.
Думал об этом. Но я ни разу не сталкивался с БД. Даже не в курсах что там к чему. Вот скажите мне: если будет таблица из 6 полей. долго ли будет выполняться sql запрос на поиск строки по 5 ограничивающим полям? Или как там правильно говорить... кароче условие проверяющее на соответствие 5 полей.
Сергей М. (2008-09-08 09:46:00) [37]
> Xandr001 (08.09.08 09:42) [5]
СУБД как раз и предназначина в т.ч. для такого рода задач
Xandr001 (2008-09-08 09:42:00) [38]
> Если приведенный способ или его вариации не нравятся, используй
> другую структуру данных, а не массив, например - хэш-таблицу.
>
Вы вообще можете вообразить себе какого размера получится хеш-таблица??? Мне кажется что много я не выиграю.
> может к БД присмотришься?
Vlad Oshin (2008-09-08 09:38:00) [39]как-то файлы использовал. число и индекс. соотв. остальное =0.
palva (2008-09-08 09:33:00) [40]Если нужен только доступ, то обычно используют базу данных с индексами.
| |
Страницы: 