Методы хранения сильно разреженных матриц

← →
Xandr001 (2008-09-08 09:19) [0]

В общем такая ситуация. Есть массив
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 09:32) [1]

Если приведенный способ или его вариации не нравятся, используй другую структуру данных, а не массив, например - хэш-таблицу.

← →
brother © (2008-09-08 09:33) [2]

может к БД присмотришься?

← →
palva © (2008-09-08 09:33) [3]

Если нужен только доступ, то обычно используют базу данных с индексами.

← →
Vlad Oshin © (2008-09-08 09:38) [4]

как-то файлы использовал. число и индекс. соотв. остальное =0.

← →
Xandr001 (2008-09-08 09:42) [5]

> Если приведенный способ или его вариации не нравятся, используй
> другую структуру данных, а не массив, например - хэш-таблицу.
>

Вы вообще можете вообразить себе какого размера получится хеш-таблица??? Мне кажется что много я не выиграю.

> может к БД присмотришься?

← →
Сергей М. © (2008-09-08 09:46) [6]

> Xandr001 (08.09.08 09:42) [5]

СУБД как раз и предназначина в т.ч. для такого рода задач

← →
Xandr001 (2008-09-08 09:47) [7]

> может к БД присмотришься?

> Если нужен только доступ, то обычно используют базу данных
> с индексами.

Думал об этом. Но я ни разу не сталкивался с БД. Даже не в курсах что там к чему. Вот скажите мне: если будет таблица из 6 полей. долго ли будет выполняться sql запрос на поиск строки по 5 ограничивающим полям? Или как там правильно говорить... кароче условие проверяющее на соответствие 5 полей.

← →
Xandr001 (2008-09-08 09:56) [8]

Или есть возможность делать n-мерные таблицы???

← →
Медвежонок Пятачок © (2008-09-08 09:57) [9]

быстро. не успеешь зевнуть.

← →
Сергей М. © (2008-09-08 09:59) [10]

> долго ли будет выполняться sql запрос

Это зависит от многих факторов.
Но у тебя вряд ли есть выбор)

← →
Xandr001 (2008-09-08 10:04) [11]

> Но у тебя вряд ли есть выбор)

:)

Дело в том, что из этой бд нужно заполнять выходную табличку, в которой около 70 тысяч записей. и это нужно выполнять для разного набора выходных таблиц. ограничение по времени - максимум 2 минуты на 1 выходную таблицу...

← →
MBo © (2008-09-08 10:11) [12]

>Вы вообще можете вообразить себе какого размера получится хеш-таблица???

Примерно в полтора-два раза больше, чем данных фактически имеется ;)
Однако с БД проще.

← →
Сергей М. © (2008-09-08 10:12) [13]

И что ?

← →
Xandr001 (2008-09-08 10:34) [14]

> И что ?

Это видимо мне... Извините. Просто не договорил.
Вот что: для каждой строки выходной таблицы нужно найти строку в справочнике, потом 2 операции присвоения, следущая строка. Мне интересно будет ли работа с БД укладываться в эти временные рамки

← →
Сергей М. © (2008-09-08 10:36) [15]

> будет ли работа с БД укладываться в эти временные рамки

При грамотном подходе - да.

← →
Xandr001 (2008-09-08 10:59) [16]

> При грамотном подходе

Ну значит буду искать этот грамотный подход.

← →
Anatoly Podgoretsky © (2008-09-08 11:58) [17]

> Вы вообще можете вообразить себе какого размера получится
> хеш-таблица???

200 000 * размер хеша - короче немного.

1..99 - 1
0..99 - 1
0..99 - 1
1..99 - 1
1..9999 - 2

Итого шесть байт = 1.2 мб

← →
han_malign © (2008-09-08 13:47) [18]

> Итого шесть байт

10^12(980001990000) - это пять байт...

← →
Anatoly Podgoretsky © (2008-09-08 13:56) [19]

> han_malign (08.09.2008 13:47:18) [18]

У тебя двоичный хеш, у меня строковый

← →
Xandr001 (2008-09-08 14:57) [20]

Товарищи! Есть мнение что мне не так преподавали теорию хеш таблиц...
Можно в двух словах о том, что вы понимаете под хешем и хеш таблицей?

← →
int64 (2008-09-08 15:09) [21]

Xandr001 (08.09.08 09:19)

Непонятно, что ты подразумеваешь под "прямой доступ к каждому элементу".

← →
MBo © (2008-09-08 15:11) [22]

Хэш таблица - строка "05:01 03 45:0567" или набор индексов 5,1,3,45,567 отображается на число в небольшом диапазоне (например для 200 тыс записей - 0..262143, или побольше, чтобы уменьшить число конфликтов), это число и будет индекс в массиве хэш-таблицы (без учета конфликтов, которых будет немного, полностью их избежать можно с использованием идеального хэширования, что здесь допустимо, поскольку таблица статичная)

← →
Anatoly Podgoretsky © (2008-09-08 15:15) [23]

> Xandr001 (08.09.2008 14:57:20) [20]

Хеш элемент хеш таблицы - одна строка

← →
int64 (2008-09-08 15:16) [24]

И опять же все зависит от разряженности. Может достаточно будет хранить тем 1 способом, что ты нашел в сети: "координаты: значение"

← →
Xandr001 (2008-09-08 15:50) [25]

"05:01 03 45:0567" - входящее значение.

> "прямой доступ к каждому элементу":

i:=Kad_number[5,1,3,45,567];

← →
int64 (2008-09-08 16:30) [26]

Xandr001 (08.09.08 15:50) [25]

> > "прямой доступ к каждому элементу":
>
> i:=Kad_number[5,1,3,45,567];

И что я должен понять?
След. код, в твоем понимании, прямой или кривой доступ?

TDefault = class private function GetKad_number(Index1, Index2, Index3, Index4, Index5: Integer): Integer; procedure SetKad_number(Index1, Index2, Index3, Index4, Index5: Integer; const Value: Integer); public property Kad_number[Index1, Index2, Index3, Index4, Index5: Integer]: Integer read GetKad_number write SetKad_number; end; implementation function TDefault.GetKad_number(Index1, Index2, Index3, Index4, Index5: Integer): Integer; begin Result := // не "прямой доступ к каждому элементу" end; procedure TDefault.SetKad_number(Index1, Index2, Index3, Index4, Index5: Integer; const Value: Integer); begin // и здесь не "прямой доступ к каждому элементу" end;

← →
Anatoly Podgoretsky © (2008-09-08 16:41) [27]

> int64 (08.09.2008 16:30:26) [26]

> И что я должен понять?
> След. код, в твоем понимании, прямой или кривой доступ?

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

← →
int64 (2008-09-08 17:14) [28]

Anatoly Podgoretsky © (08.09.08 16:41) [27]
Я знаю, что такое массив и что такое ассоциативный массив. Спасибо.

Я хочу убедиться знает ли автор, что такое прямой доступ.
У меня есть подозрение, что ему нужна лишь синтаксическая конструкция вида: Kad_number[5,1,3,45,567]. Т.к., в противном случае, вопрос стоял бы так:
"У меня есть тип данных, превышающий 2Гб, но я связан по рукам использовать другой тип данных, и использовать другой доступ кроме прямого итд"

← →
Xandr001 (2008-09-09 10:20) [29]

> Я хочу убедиться знает ли автор, что такое прямой доступ.

да. я знаю.

> вопрос стоял бы так: ...

у меня скил "искусство задавать правильные вопросы" не прокачан...

> у меня скил "искусство задавать правильные вопросы" не прокачан...

у нас скилл телепатора тож)

В моем понимании "прямой доступ к элементу массива" это, когда я получаю указатель на этот элемент, и за этим элементом лежит следующий, если он имеется. В этом случае я не теряю время на определение координат этого следующего элемента. Всё это имеет смысл, когда массив непрерывный. В случае же "разреженного", может быть даже упакованного по сути массива (ассоциативного) иметь такой прямой доступ не вижу смысла.

← →
Xandr001 (2008-09-09 15:37) [32]

> Всё это имеет смысл, когда массив непрерывный

Массив заполняется блоками.

какими блоками? Блоками по 4 байта? :)
Вот у тебя элемент [5,1,3,45,567]. Какими блоками мы чего заполняем? Давай на пальцах

← →
Xandr001 (2008-09-12 06:08) [34]

давай.
1) непрерывный линейный массив arr[0..14]: 1,2,5,9,8,3,5,7,88,6,3,6,8,2,8
2) разреженный линейный массив arr[0..14]: 0,0,5,0,0,0,0,7,0,0,3,0,0,0,8
3) линейный массив arr[0..14] заполняется блоками: 2,5,5,4,7,0,0,0,0,0,3,6,7,9,8

Длинна блоков и пустых элементов между ними не известна заранее, но постоянна после загрузки массива, т.е. в процессе выполнения программы массив статичен.

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

← →
Xandr001 (2008-09-12 11:05) [36]

> столь фиксированных параметрах

Это Вы про какие такие параметры????????????

про размер данных.

Покурите:
http://www.robosoft.info/knowledge/articles/detail.php?ID=886

← →
Xandr001 (2008-09-12 14:14) [39]

> про размер данных

Всё так, но только в идеальных условиях. дело в том, что входная строка может иметь различные виды:
"05:01 03 45:0567", " 05 :01 03 45:0567", "05:0103 45:0567", "05:0103 45:0 5 6 7"," 05:010345: 0567", "05:01:03:45:0567", " 05 :0 1 0 3 4 5:0567 ", " 05 :000 1 0 3 4 5:0567 "...

а при чем здесь входная строка?
как будет она обрабатываться, дело десятое.

Методы хранения сильно разреженных матриц Найти похожие ветки