Разреженные матрицы Опции

[Tribunal]

У меня появилась задача следующего содержания:

нужно вводить элементы разреженной матрицы и
произвести рациональное хранение этих элементов...

ну это я предполагаю можно сделать так:
CIP: Индекс начала 1-ой строки в массивах PI и YE || Индекс начала 2-ой Строки || ... || Индекс начала N-ой Строки
PI: Номер столбца || Номер столбца || Номер столбца || ... || Номер столбца || 0
YE: Значение || Значение || Значение || ... || Значение

ИЛИ

в массив JA записывать номера столцов,в которых находятся ненулевые эл-ты по порядку;
в массив AN записывать собственно значения этих ненулевых значений;
а в массив IA записывать номера , с которых начинается описание эл-тов в массивах JA и AN(<---вот это мне не очень понятно=/)

но,честно говоря,вся проблема состоит в том,что я не очень представляю,как это должно
выглядеть в делфи...в том числе и визуально-на форме=/

поэтому в этом состоит вся проблема...не очень понимаю,как начать

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

большая просьба помочь=)с делфи пока на вы=(

[hiv]

Может проще заархивировать твою матрицу, а перед извлечением эелемента - разархивировать (архив будет сидеть в ОЗУ).
Но думаю лучше всего использовать динамические структуры типа списка, но только эффект от них будет только если матрица заполнена менее чем на 20%-25%

[Tribunal]

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

[Lapp]

ну это я предполагаю можно сделать так:
CIP: Индекс начала 1-ой строки в массивах PI и YE || Индекс начала 2-ой Строки || ... || Индекс начала N-ой Строки
PI: Номер столбца || Номер столбца || Номер столбца || ... || Номер столбца || 0
YE: Значение || Значение || Значение || ... || Значение

ИЛИ

в массив JA записывать номера столцов,в которых находятся ненулевые эл-ты по порядку;
в массив AN записывать собственно значения этих ненулевых значений;
а в массив IA записывать номера , с которых начинается описание эл-тов в массивах JA и AN(<---вот это мне не очень понятно=/)

но,честно говоря,вся проблема состоит в том,что я не очень представляю,как это должно
выглядеть в делфи...в том числе и визуально-на форме=/

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

большая просьба помочь=)с делфи пока на вы=(

Я честно пытался разобраться с твоими способами, но ни один не понял до конца. Предлагаю свой - простой и ясный (как мне кажется ).

P - массив (из integer) координат позиций, где стоят отличные от нуля элементы (от слова Position).
Устроен так:
Номер столбца С1 (от слова column)
номер строки (то есть элемента в этом столбце) R11 (от row)
номер строки R12
номер строки R13
...........
Ноль (разделитель)
Номер столбца C2
номер строки R21
номер строки R22
........
Ноль
Номер столбца
номер строки
номер строки
........
Ноль
Ноль (в конце два нуля)

Это можно записать проще в строчку:
CRRRRR..R0CRR...R0CRR..R0C.........CRR..R00

И массив самих значений (того типа, который нужен):
A(C1,R11)
A(C1,R12)
....
A(C2,R21)
....
A(Cn,Rnm)

Чтобы достать значение i,j , проходимся по Р, считая номер. Если C=i и R=j (в секции этого C) присутствует - вынимаем значение из А по номеру.

Для ускорения доступа можно иметь маленький массив из позиций С в массиве Р (но это факультативно).

Если тебе мой способ не понравился - скажи, попробую еще раз разобраться в твоих.
Далее, тебе пока не нужно лезть в Дельфи и формы. Это потом приложишь. Пока сделай прогу на паскале, которая осуществляет сжатие матрицы и доступ к ней. Этот код потом вставишь в Дельфи. Все надо делать по очереди.

[hiv]

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

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

[volvo]

Tribunal, твой метод, случаем, не отсюда:
Представление разреженных матриц
?

[Гость]

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

По-моему, задача стоит не совсем о минимуме, а о некотором оптимуме: при достаточно малом потреблении памяти получить достаточно хорошую производительность. Я домаю, что можно изобрести метод, использующий меньше памяти, чем мой (например, развернув двумерный массив в одномерный). Но почему ты думаешь, что я слишком щедро я базарю память? Ведь у меня на каждый непустой элемент матрицы идет память, требующаяся для этого элемента (предположительно, double) плюс размер одного целого числа (2 байта) плюс еще некоторые накладные расходы в размере четырех байт на строку матрицы. Естественно (я не упомянул это, но это подразумевается), память для двух упомянутых массивов берется динамически, поблочно (размер блока я бы положил равным примерно четверти среднего требующегося размера).

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

Не знаю, нужны ли авторы темы все эти тонкости.. Короче, пусть она сама выбирает

[Lapp]

Последнее сообщение - мое. Извиняюсь.
Никак не могу понять, в какой момент система вдруг меня забывает!

[Tribunal]

ну вообще-то первый метод предложил преподаватель

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

По-моему, задача стоит не совсем о минимуме, а о некотором оптимуме:
....
Не знаю, нужны ли авторы темы все эти тонкости.. Короче, пусть она сама выбирает

я не умею работать со списками=(не научилась ещё=)

[Lapp]

ну вообще-то первый метод предложил преподаватель

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

[Atos]

я не умею работать со списками=(не научилась ещё=)

В Дельфи уже есть списки - см. класс TList


А отображать матрицу на экран проще всего таблицей TStringGrid. А если у неё изменить значение всего одного свойства cfalse на true в Инспекторе(забыл, какое именно...), то пользователю будет разрешено тут же, пря мо на экране заполнять и редактировать таблицу, как в Excel

Сообщение отредактировано: Atos - 1.03.2006 7:26

[Tribunal]

lapp, а вот если пользоваться твоим способом...(честно говоря,он мне больше понятен)....то как сделать так,чтобы номер строки и столбца вводимого ненулевого элемента записывался в нужное место массива P-координат позиций?

Сообщение отредактировано: Tribunal - 1.03.2006 7:38

[Tribunal]

или объясните,пожалуйста,мне поподробнее,по какому принципу записывается массив IA во втором способе?

[volvo]

Tribunal, вопросы задаются, чтобы на них отвечали, или ты думаешь, что мне просто нечего было делать, и я пришел сюда, нашел тебе ссылку на алгоритм и его реализацию, а ты продолжишь изобретать велосипед заново?

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

[Tribunal]

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

[Tribunal]

я хочу разобраться с тем,как премножать двет разреженные матрицы.
для начала я хотела бы сделать алгоритм для перемножения матриц,
которые заданы довольно простым способом:
an,bn-одномерные массивы ненулевых значений разреженных матриц;
ia,ib-соотвествующие им строки,так же занесенные в одномерный массив;
ja,jb- ---''--- столбцы ---''--- ;
k,c-это получившееся кол-во полученных элементов после ввода соотв-но для матриц a и b;

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

в качестве при мера приведу алгоритм для солжения таких матриц:

Код

var
   i,j,x:integer;
begin
   h:=k;
   for i:=1 to k do
   begin
   cn[i]:=an[i];
   ic[i]:=ia[i];
   jc[i]:=ja[i];end;

   for i:=1 to c do
   begin
   x:=-1;
   for j:=1 to h do
   if (ib[i]=ic[j]) and (jb[i]=jc[j]) then x:=j;
   If x<>-1 then cn[x]:=bn[i]+cn[x]
   else begin
   h:=h+1;
   cn[h]:=bn[i];
   ic[h]:=ib[i];
   jc[h]:=jb[i];end;
   end;
end;