2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Чем плох массив ячеек в MATLAB?
Сообщение15.11.2015, 22:31 
Заслуженный участник


29/12/14
504
В MATLAB, как известно, существует такой тип хранения данных, как массив ячеек. Его плюсы мне очевидны, а вот минусы - нет. Помню, кто-то из более-менее активно работающих в этой среде говорил мне, что к массивам ячеек нужно прибегать, когда других вариантов уже нет. Но вот причины не указал. Не нашёл ничего путного и в Интернете. Может быть, здесь кто-нибудь подскажет?

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение16.11.2015, 00:21 
Заслуженный участник
Аватара пользователя


11/04/08
2736
Физтех
Ячейки -- это нечто среднее между обычными массивами чисел/символов и стуктурами. Поэтому минусами ячеек можно назвать как раз то, что отличает их от структур -- отсутствие полей, по которым можно обращаться к конкретным данным. Если данных в массиве ячеек нужно хранить много, и они разные и/или очень похожие, то чтобы не запутаться можно использовать именно структуры. С другой стороны, обращение к элементам ячеек происходит так же, как к элементам обычных массивов -- через индексы, поэтому возможность воспользоваться оператором двоеточия, чтобы легко пробежаться по элементам ячейки. Аналога у структур я вроде не встречал...

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение16.11.2015, 00:44 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Gickle в сообщении #1073826 писал(а):
Но вот причины не указал.

Сравните время доступа... и затраты памяти.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение16.11.2015, 00:51 
Заслуженный участник


29/12/14
504
Geen
У меня, собственно говоря, и была мысль, что время доступа у ячеек сильно выше должно быть. А вот по поводу второго хотел бы уточнить. Вот нам нужно, например, как-то хранить информацию о $M$ векторах разной длины (пусть максимальная длина вектора равна $N$). Если мы хотим это сделать в рамках обычных массивов, то нам придётся задать массив $(M,N)$, что займёт у нас в стандартной ситуации $M\cdot N\cdot8$ байт памяти. А в случае ячеек $8 \cdot K$ байт памяти, где $K$ - общее число элементов. Разве нет?

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение16.11.2015, 01:04 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Gickle в сообщении #1073860 писал(а):
хранить информацию о $M$ векторах разной длины

Обычно, это не типичная ситуация, всё же.

Gickle в сообщении #1073860 писал(а):
А в случае ячеек $8 \cdot K$ байт памяти, где $K$ - общее число элементов. Разве нет?

Нет. Каждая ячейка имеет "накладные расходы" (равные обычной переменой).

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

По скорости, впрочем, тоже есть особенности (в случае частого изменения размеров, например).

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение16.11.2015, 01:10 
Заслуженный участник


29/12/14
504
Geen
Даже так. Спасибо за информацию, надо будет изучить этот вопрос плотнее. Я почему-то был убеждён, что массив ячеек - наиболее экономный способ хранить информацию о массивах разной длины.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение16.11.2015, 01:22 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Gickle в сообщении #1073865 писал(а):
надо будет изучить этот вопрос плотнее.

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

Gickle в сообщении #1073865 писал(а):
массив ячеек - наиболее экономный способ хранить информацию

Если много мелких массивов, то это не так. А если их, скажем, три, то может и не быть смысла хранить их вместе (особенно если учесть, что передача аргумента в функцию это всегда копирование).

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение18.11.2015, 19:07 
Заслуженный участник


29/12/14
504
Geen
извините, не могли бы вы помочь ещё раз с хранением данных в MATLAB? У меня вот какая ситуация: область, по ней разбросаны точки, эту область я разбиваю на ячейки и хочу узнать (а затем и хранить), в какой ячейке какие находятся точки. При этом важно, чтобы доступ к этим данным был максимально быстрым, а памяти занимало по возможности немного. Я до этого пользовался как раз массивом ячеек, но, как вы заметили выше, это далеко не самый экономичный во всех смыслах способ. В общем, хотел перейти на разрежённые матрицы. Но тут следующие проблемы. Во-первых, формат разреженных матриц в MATLAB есть только для, как это ни странно, матриц (то есть массивов размерности 2), а у меня трёхмерный массив. Или я не прав и есть возможность работать с многомерными разреженными массивами? Во-вторых, я, вообще говоря, заранее не могу знать размер своего массива (поскольку не знаю изначально, сколько максимально точек будет в ячейках). Здесь я, по сути, могу сделать некоторые оценки изначально и с высокой долей вероятности не ошибиться, но хотелось бы всё-таки, чтобы неожиданности не могли ничего испортить. Наконец, при заполнении очередным элементом (точкой) в рамках работы с массивом ячеек я могу сделать что-нибудь вроде S{i,j,k} = [S{i,j,k} p], а вот при работе с матрицами - нет. Не знаете, есть ли какой-нибудь простой способ постепенного заполнения изначально нулевых векторов (думаю, понятно, что имеется в виду). То есть без всяких проверок перед каждым добавлением элементов.

Заранее спасибо.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение18.11.2015, 20:32 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Gickle в сообщении #1074664 писал(а):
по ней разбросаны точки, эту область я разбиваю на ячейки и хочу узнать (а затем и хранить), в какой ячейке какие находятся точки.

Разбросаны равномерно? Сколько ячеек, сколько точек? (порядок)

Gickle в сообщении #1074664 писал(а):
доступ к этим данным был максимально быстрым

Приведите, пожалуйста, примеры типичных обращений (добавление/удаление/получение чего?) с примерной частотой.

Gickle в сообщении #1074664 писал(а):
Или я не прав и есть возможность работать с многомерными разреженными массивами?

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

Gickle в сообщении #1074664 писал(а):
сделать что-нибудь вроде S{i,j,k} = [S{i,j,k} p]

а что такое $p$ в данном примере?

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение18.11.2015, 21:20 
Заслуженный участник


29/12/14
504
Geen
Цитата:
Разбросаны равномерно? Сколько ячеек, сколько точек? (порядок)

Разбросаны равномерно (точнее сказать, случайным образом). Плотность точек на ячейку $n \approx 0.76$ ($84303$ точки на $48^3$ ячеек); вообще, это зависит от некоторого параметра, но по порядку всегда одинаково (более того, вряд ли больше $2$ будет, например). Понятно, что число точек в ячейке по Пуассону распределено. И что плохо, так это то, что для достаточно большого числа точек нельзя будет сказать что-нибудь в духе "да больше 10 в одну точно не упадёт уж". Мало ли...

Цитата:
Приведите, пожалуйста, примеры типичных обращений (добавление/удаление/получение чего?) с примерной частотой.

Обращение у меня следующего характера: прогоняя цикл по всем точкам, мне нужно выделить массив (я его indx обзываю), в котором будут номера тех точек, которые лежат в пределах ближайшей окрестности (то есть в окрестности Мура + собственной ячейке). Выглядит примерно так:
Используется синтаксис Matlab M
indx = [grid{K_1+1,K_2+1,K_3+1} ... ];
,
где $K$ - номер ячейки, в которой лежит текущая точка.
Тут я просто, чтобы побыстрее работало, вместо использования цикла для перебора всей окрестности вбил всё вручную (всю окрестность уж не перечислял, мысль понятна, я думаю). Такая вещь у меня появляется на каждой итерации, которых довольно много (в перспективе система размерами побольше, а потому и точек сильно побольше). Кроме того, подобную процедуру мне надо будет проделать не один раз, поэтому хотелось бы по возможности минимизировать затраты по времени на это.

Цитата:
а что такое $p$ в данном примере?

Номер точки, которую я хочу добавить ячейку. Ну, то есть, например, точку под номером $26034$ добавить в ячейку номер $(12,23,11)$. В рамках работы с массивом ячеек это делает так, как я написал. В рамках работы с обычными массивами же для того, чтобы сделать из [1 2 4 0 0], например, [1 2 4 7 0], нужно понять, где стоит ближайший ноль, то есть либо держать счётчик, либо каждый раз проверку делать. А хотелось бы в одно действие, если честно.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение19.11.2015, 01:55 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Gickle в сообщении #1074694 писал(а):
$84303$ точки

Вообще-то, это не выглядит слишком объёмным (по памяти)...

Gickle в сообщении #1074694 писал(а):
И что плохо, так это то, что для достаточно большого числа точек нельзя будет сказать что-нибудь в духе "да больше 10 в одну точно не упадёт уж". Мало ли...

Не переживайте Вы так об ограничениях (преждевременно).... (А может Вы уже знаете быстрый способ, но с ограничением? ;-))

Gickle в сообщении #1074694 писал(а):
в котором будут номера тех точек, которые лежат в пределах ближайшей окрестности

Я правильно понимаю, что Вы хотите быстро находить точки, "близкие" к заданной?

Gickle в сообщении #1074694 писал(а):
Номер точки, которую я хочу добавить ячейку. Ну, то есть, например, точку под номером $26034$ добавить в ячейку номер $(12,23,11)$.

А сколько ещё информации хранится под номером точки? Может накладными расходами на ячейки можно пренебречь??

Gickle в сообщении #1074694 писал(а):
Кроме того, подобную процедуру мне надо будет проделать не один раз

Вот поэтому я и спрашивал про "частоты"... Пока что всё равно не понятно, каково соотношение добавления точек к поиску ближайших, например.
Особенно важно поведение этих "частот" с ростом "размеров".

Gickle в сообщении #1074694 писал(а):
А хотелось бы в одно действие, если честно

"Вам шашечки или ехать?" (с) ;-)


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

P.S.
Gickle в сообщении #1074694 писал(а):
Ну, то есть, например, точку под номером $26034$ добавить в ячейку номер $(12,23,11)$. В рамках работы с массивом ячеек это делает так, как я написал. В рамках работы с обычными массивами же для того, чтобы сделать из [1 2 4 0 0], например, [1 2 4 7 0], нужно понять, где стоит ближайший ноль, то есть либо держать счётчик, либо каждый раз проверку делать.

Честно говоря, не понял.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение19.11.2015, 09:43 
Заслуженный участник


29/12/14
504
Geen
Видимо, я несколько сумбурно излагал свои мысли, сейчас попробую обрисовать свою цель в целом.

У меня есть некоторое число $N$ (оно определяется размерами и параметром пористости системы; в перспективе $N$ может быть сильно большим, поэтому хотелось бы быть поэкономнее с памятью) случайным образом разбросанных сфер разного радиуса. Все эти сферы у меня пронумерованы, и я хочу найти кластеры этих сфер (сферы принадлежат одному кластеру, если они пересекаются). Для этого есть несколько алгоритмов, каждый из которых, разумеется, предполагает обход по всем сферам и знание, кто является соседями данной сферы. Ну, для облегчения задачи я изначально разбиваю всю свою систему на ячейки со стороной $2R_\max$ и смотрю, сферы с какими номерами там сидят. А потому для проверки соседей у каждой сферы нужно будет смотреть только ближайшее окружение, что быстрее.

Вот, в общем, с операцией разделения системы на ячейки у меня сейчас и проблемы. То есть через массив ячеек я сделал, но мне в рамках поиска кластеров нужно будет на каждой итерации обращаться к данным из этого массива, что замедляет работу вроде как. Кроме того, по ряду причин мне нужно будет проводить операцию поиска кластеров в течение всей работы не один раз, а столько раз, сколько время позволит. Поэтому я хочу сделать операцию поиска кластеров как можно быстрее. Для этого есть ещё мысль всё это дело распараллелить весь процесс поиска кластеров. Для этого опять же помогут ячейки: просто разобью всю систему на несколько подсистем, проведу всю эту операцию для каждой из подсистем в отдельности, а потом пройдусь по граничным ячейкам, "сшивая" решение.

Вообще, есть ещё два варианта:

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

Надеюсь, в этот раз я смог яснее обрисовать суть задачи.

Цитата:
Вообще-то, это не выглядит слишком объёмным (по памяти).

В теории хорошо было бы иметь $\sim 10^7 - 10^8$ точек. А тут уже пора задумываться о памяти.

Цитата:
А сколько ещё информации хранится под номером точки? Может накладными расходами на ячейки можно пренебречь??

Не совсем понял вопрос, если честно. Под номером точки скрывается 7-8 полей структуры (координаты, радиус и ещё ряд специфических).

Цитата:
Честно говоря, не понял.

Предположим, мы описываем ячейки, на которые разбиваем всю систему, обычным массивом. Соответственно массив должен быть четырёхмерным - 3 из размерности пространства, 4 под номера точек, которые в ячейке находятся. Нужно, значит, задать этот массив. Пусть мы сделали оценку сверху и думаем, что больше 10 точек в одну ячейку не упадёт, и пусть длина ячейки составляет $1/50$ длины системы. Тогда нужно будет объявить массив:
Используется синтаксис Matlab M
grid = zeros(50,50,50,10);

Теперь мы, например, узнали, что в ячейку (11,21,7) нужно добавить точку (сферу) с номером 26034. Как это сделать без того, чтобы каждый раз проверять, где там следующий нуль, или без какого-нибудь дополнительного массива счётчиков, я себе плохо представляю.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение19.11.2015, 10:02 


01/12/11

1047
Gickle в сообщении #1074664 писал(а):
У меня вот какая ситуация: область, по ней разбросаны точки, эту область я разбиваю на ячейки и хочу узнать (а затем и хранить), в какой ячейке какие находятся точки. При этом важно, чтобы доступ к этим данным был максимально быстрым, а памяти занимало по возможности немного.


Если я правильно понял, что вам нужно из области выбрать только значащие элементы и записать их компактно. Если вам после выбора данных не нужна исходная область, то выбранные данные можно разместить в ней. В этом случае никакой дополнительной памяти не понадобится. Задача сведётся к упорядочению данных в области.

Что такое область? Как она описана?

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение19.11.2015, 12:50 
Заслуженный участник


29/12/14
504
Skeptic
Нет, не совсем правильно, видимо. Ситуация следующая:

1. Область есть некий куб со стороной $L$, которая задаётся мной.
2. Исходя из размеров системы, задаваемого распределения сфер по радиусам и задаваемого же параметра пористости системы, определяется число сфер, которые затем будут разбросаны.
3. Совокупность сфер представляет собой массив структур, полями которых в том числе являются координаты и радиус. Координаты сфер задаются случайным образом, радиусы - в соответствии с некоторым заданным распределением.
4. Мне нужно теперь определить, какие кластеры из сфер есть в системе. Для этого, очевидно, нужно как минимум пройтись по всем сферам, зная при этом на каждом шаге всех соседей текущей сферы.
5. Для упрощения задачи я изначально хочу разбить всю свою область (куб со стороной $L$) на ячейки со стороной $2R_\max$. А затем записать, какие сферы в каждой ячейке лежат. Это мне позволит затем, во-первых, искать соседей текущей сферы только из ближайшего окружения (окружение Мура + собственная ячейка), а во-вторых, довольно просто распараллелить процесс. Для этого нужно будет просто разделить опять же область на несколько (сколько есть ядер) подобластей, в каждую из которых попадут какие-то ячейки. Провести параллельно разделение на кластеры в каждой из подобластей, а потом по граничным ячейкам провести "сшивку".

Теперь встаёт вопрос: а как организовать хранение информации о том, какие сферы лежат в данной ячейке, так, чтобы это занимало по возможности как можно меньше памяти, а доступ к информации при этом был максимально быстрым? Обсуждению этого вопроса и посвящены сообщения выше.

 Профиль  
                  
 
 Re: Чем плох массив ячеек в MATLAB?
Сообщение19.11.2015, 15:29 


01/12/11

1047
Gickle
Есть двумерный массив описания сфер. Строка массива - число параметров сферы (символьные значения можно предварительно закодировать числами). Количество строк - число сфер. Для размещения сфер нужно задать их число. Если матлаб допускает динамическое распределение памяти, то проблем нет, в противном случае задаём максимально возможное. Для номера кластера строку массива дополняем одним элементом, или описываем новый массив, что, практически, одно и тоже. Для построения кластеров перебираем все пары сфер, и не один раз. Условие принадлежности двух сфер одному кластеру: расстояние между центрами сфер меньше суммы радиусов.
Я бы решал как-то так.

Массив - плотное размещение данных с возможностью единой их обработки. Что-то другое увеличит время работы и потребует больше памяти. Размерность массива - данность из вне. Размещением его в памяти пусть разбирается система и матлаб. Если размер заданного массива не пропускает матлаб или система, тогда надо думать. Скорее всего придётся переходить на другой язык.
Вообще, серьёзную оптимизацию делают для работающей программы.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group