Форум "Delphi"

Паскаль, Делфи

#0 nomadminded 28.12.06 18:46:31 - 03.11.07 04:52:28

структура большой матрицы

доброго времени суток всем! подскажите пожалуйста, как лучше в делфи работать с больщой матрицей (500 000 х 20 000 при заполненности менее 2%). решила создать массив записей типа "нр.строки", "нр.колонки", "значение", но даже тогда получается больше 700мб. а хотелось бы оперативности, поэтому собираюсь этот массив засунуть в память. какие процедуры можете посоветовать для быстрого обращения к нему? лучше делать просто динамический массив и функцией setlength ему выделять нужное кол-во памяти или как-то с пойнтерами работать? что удобнее будет?
спасибо.

#1 VictorT © 28.12.06 19:54:27

какие операции будут проводится над матрицей?

#2 nomadminded 29.12.06 10:25:52

в основном поиск нужного значения, но для начала сортировка по строкам и сортировка по колоннам.

#3 Паша © 29.12.06 10:48:50

> "нр.строки", "нр.колонки", "значение"

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

setlength(arr, 500 000 * 20 000) - может тормозить на больших объемах. слышал, но не пробовал. попробуй по времени ее и GetMem(arr, 500 000 * 20 000* 8). в принципе, какая разница, ну указатели будут, делов. кстати, 8 - если массив типа double, тут размер типов надо помнить

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

зы. вроде, существуют библиотеки для работы с большими матрицами, но я этим не занимался.

#4 nomadminded 29.12.06 11:07:11

что-то я не понимаю, как у тебя 78 метров получилось, объясни пожалуйста.
число до 500 000 это integer = 4 байта, до 20 000 word = 2 байта, ну и значение 1 байт.
то есть 700 метров в любом случае при примерном кол-ве в 100 000 000 записей. нр.строки и нр.колонки решила хранить, потому что заполненность только 1 с лишним %, так что не вижу смысла в сохранении >98% пустых ячеек.

#5 Паша © 29.12.06 11:24:12

я считал двухмерную матрицу, как у тебя было написано в условии, для типа double 8 байт
500000*20000*8/1024=78125000

теперь оказываецца, шо у тебя трехмерная матрица, такь? квадрат 500000*20000 и еще в высоту 100 лимонов? нифига не пойму.

тогда сколько всего значений предполагаецца и какого типа они будут?

#6 Паша © 29.12.06 11:33:26

тьфу. а с какого это бодуна я в килобайты перевел? торможу непадецки! гыгы

#7 nomadminded 29.12.06 11:34:24

я уже сама запуталась, не могу понять, где ошибаюсь. попробую еще раз сначала описать задачу.
допустим в строках у нас id клиента (всего клиентов 500 000), в колонках - id продукта (всего 20 000), на пересечении, т.е. в ячейке - оценка клиентом продукта, допустим от 1 до 5.
из всей этой информации имеется менее 2% (на самом деле где-то 1,2%), то есть около 120 000 000 ячеек заполнены.
вот и как лучше хранить эти 120 000 000 ячеек?
и почему ты я считал двухмерную матрицу, как у тебя было написано в условии, для типа double 8 байт
500000*20000*8/1024=78125000 делишь на 1024?

#8 Паша © 29.12.06 11:41:29

так. вот тут мне подсказали метр - 2^20, т.е.: 500000*20000*8/1048576= 76 метров. в принципе, не очень я и ошибся

#9 nomadminded 29.12.06 11:51:15

ну хорошо, как тогда будет выглядеть эта структура на 76 метров??
array [1..500000] of array [1..20000] of byte? такое занимает больше 2гб.
не понимаю, как ты хочешь запихнуть ее в 76мб.. объясни!

#10 Паша © 29.12.06 11:52:09

> id клиента (всего клиентов 500 000)

integer = 4 байта

> id продукта (всего 20 000)

integer = 4 байта

ну и флаг - байт
итого: (500000*4)*(20000*4)*4/2^20=610 метров. некритично, но многовато. да и гемор с выборкой будет. а оно надо для такой тривиальной задачи?

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

#11 Паша © 29.12.06 11:58:04

блин! ну я и дурак! пить надо меньше.
это у тебя будет массив 500000*20000 типа байт

500000*20000*4/2^20=38 метров. id хранить не нужно. просто первый клиент и первый товар в твоих базах имеют координату в матрице 0х0, первый клиент и второй товар - 0х1 и т.д.

но нафига? в базу все суй с полями "клиент", "товар", "значение" и индексируй по "значение". тупо и фанатично

#12 Vlad © 29.12.06 14:30:04

a=
1,2
3,4

b=1,2,3,4

a[i,j]= b[i*(numRow)+j]

b: file of (чего);

#13 Зашел © 02.11.07 11:19:33

Ну и счет
500 000 * 20 000 = 10 000 000 000
2% - 200 000 000

Как из этого числа элементов умудриться получить 78 метров - для меня загадка.

#14 Deep © 02.11.07 11:37:11

тема старовата, но решил вставить своих 5 коп.
Почему-то кажется что с такими массивами надо работать как с базой данных.
Тот же Firebird с таким массивом на ура отработает: и найдет, и отсортирует.
Что и требовалось.

#15 Паша © 02.11.07 11:41:19

археологи раскопали Последний День Помпеи! гыгы

#16 Зашел © 02.11.07 11:47:12

Дык. Не я придумал чтобы старые темы всплывали в шапке новых. Иногда вот и вылавливается забавное.

#17 Deep © 02.11.07 12:11:06

дык, а разве это (показывать случайную/старую тему) плохо?
По крайней мере эта ветка прошла тогда мимо меня, а счас почитал -- интересно. Отметился. Автору мой совет наверное не поможет, но тем кто зайдет сюда в поисках решения схожей задачи -- очень даже может быть.

#18 Зашел © 02.11.07 12:23:25

>#17 Deep © 02.11.07 12:11:06

Дык, я и не против. Это Пашу на гыг-гы пробило.

А я бы хранил по другому, наверное, - смотря чего надо вообще. Для чего будет нужна эта матрица и как применяться. Ибо неквадратная - отсюда и вопросы.

#19 Паша © 02.11.07 12:29:40

>#18 Зашел ©

да и трехмерную матрицу можно свести к плоской структуре, хранить x,y,z. а с учетом малого заполнения - тем более.

#20 Зашел © 02.11.07 12:33:30

>#19 Паша © 02.11.07 12:29:40

Один параметр лишний для хранения с элементом. Лучше отдельно хранить массив смещений строк.

#21 Andrey © 02.11.07 15:42:28

>#19 Паша
Когда-то, во времена бурной молодости, я таким образом пытался вообразить себе пятимерное пространство - сломал моск. Больше не пытаюсь )

#23 Mystic © 02.11.07 16:03:33

> #21 Andrey © 02.11.07 15:42:28

А что его представлять? Представь N-мерное пространство, потом представь, что N=5

#24 Юрий Федоров © 02.11.07 16:55:14

>#22 Паша ©

Бывало попьешь попьешь, и не то что пятимерное, а и трехмерное как то с трудом представляется
1-2 максимум

ТОлько это путь в никуда.

#26 Зашел © 03.11.07 04:52:28

В связи с размерностями и т.п рекомендую книгу Фоменко(того самого) "Наглядная геометрия и топология".

А представить даже 4-х мерное... Ну для начала представить, что железные правая и левая перчатки суть одинаковы и получаются друг из друга без деформаций, а обычным движением. Или представить бутылку Клейна.
Это вряд ли получится, но тем не менее в каком-то смысле мы это представляем, ибо можем работать с этими объектами и делать относительно них некоторые рассуждения и утверждения. Можем даже расставлять в реале коней на "шахматной" доске, которая эквивалента бутылке Клейна.

Написать ответ