Чем плох массив ячеек в MATLAB?

[Gickle]

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

[ShMaxG]

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

[Geen]

Gickle в сообщении #1073826 писал(а):

Но вот причины не указал.

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

[Gickle]

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

[Geen]

Gickle в сообщении #1073860 писал(а):

хранить информацию о $M$ векторах разной длины

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

Gickle в сообщении #1073860 писал(а):

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

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

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

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

[Gickle]

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

[Geen]

Gickle в сообщении #1073865 писал(а):

надо будет изучить этот вопрос плотнее.

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

Gickle в сообщении #1073865 писал(а):

массив ячеек - наиболее экономный способ хранить информацию

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

[Gickle]

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

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

[Geen]

Gickle в сообщении #1074664 писал(а):

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

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

Gickle в сообщении #1074664 писал(а):

доступ к этим данным был максимально быстрым

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

Gickle в сообщении #1074664 писал(а):

Или я не прав и есть возможность работать с многомерными разреженными массивами?

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

Gickle в сообщении #1074664 писал(а):

сделать что-нибудь вроде S{i,j,k} = [S{i,j,k} p]

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

[Gickle]

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], нужно понять, где стоит ближайший ноль, то есть либо держать счётчик, либо каждый раз проверку делать. А хотелось бы в одно действие, если честно.

[Geen]

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], нужно понять, где стоит ближайший ноль, то есть либо держать счётчик, либо каждый раз проверку делать.

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

[Gickle]

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. Как это сделать без того, чтобы каждый раз проверять, где там следующий нуль, или без какого-нибудь дополнительного массива счётчиков, я себе плохо представляю.

[Skeptic]

Gickle в сообщении #1074664 писал(а):

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

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

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

[Gickle]

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

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

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

[Skeptic]

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

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