Имя шаблона для гибкой структуры данных? - PullRequest
3 голосов
/ 29 октября 2008

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

Вот ситуация:

Я создаю научное приложение, в котором одна из центральных структур данных имеет три фазы: 1) накопление, 2) анализ и 3) выполнение запроса.

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

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

API будет выглядеть примерно так (код на Java, но это не очень важно; для ясности код разделен на три раздела):

// SECTION 1:
// Create the aggregation object, and get the zillion objects to insert...
ContinuousScalarField field = new ContinuousScalarField();
Collection<Measurement> measurements = getMeasurementsFromSomewhere();

// SECTION 2:
// Add all of the zillion objects to the aggregation object...
// Each measurement contains its xyz location, the quantity being measured,
// and a numeric value for the measurement. For example, something like
// "68 degrees F, plus or minus 0.5, at point 1.23, 2.34, 3.45"
foreach (Measurement m : measurements) {
   field.add(m);
}

// SECTION 3:
// Now the user wants to ask the model questions about the interpolated
// state of the model. For example, "what's the interpolated temperature
// at point (3, 4, 5)
Point3d p = new Point3d(3, 4, 5);
Measurement result = field.interpolateAt(p);

Для моей конкретной проблемной области будет возможно выполнить небольшую дополнительную работу (разделив точки на сбалансированное KDTree) во время РАЗДЕЛА 2.

И будет небольшая работа (выполнение некоторых линейных интерполяций), которая может произойти во время РАЗДЕЛА 3.

Но есть огромный объем работы (создание оценщика плотности ядра и выполнение быстрого преобразования Гаусса с использованием рядов Тейлора и функций Эрмита, но это совершенно не относится к делу), которые должны быть выполнены между разделами 2 и 3.

Иногда в прошлом я просто использовал ленивую оценку для построения структур данных (в данном случае это было бы при первом вызове метода "interpolateAt"), но затем, если пользователь вызывает " field.add () "метод снова, я должен полностью отбросить эти структуры данных и начать все заново.

В других проектах я потребовал, чтобы пользователь явно вызвал метод "object.flip ()", чтобы переключиться из "режима добавления" в "режим запроса". Приятно то, что в таком дизайне пользователь лучше контролирует точный момент, когда начинаются сложные вычисления. Но для потребителя API может быть неприятно отслеживать текущий режим объекта. И, кроме того, в стандартном случае использования вызывающая сторона никогда не добавляет другое значение в коллекцию после начала выдачи запросов; агрегация данных почти всегда полностью предшествует подготовке запроса.

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

Предпочитаете ли вы, чтобы объект лениво выполнял тяжелый анализ, отбрасывая промежуточные структуры данных при поступлении новых данных в коллекцию? Или вы требуете, чтобы программист явно перевернул структуру данных из режима добавления в режим запроса?

А вам известно какое-либо соглашение об именах для таких объектов? Есть ли образец, о котором я не думаю?


В режиме редактирования:

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

Вы можете получить довольно хорошее представление о том, о чем я говорю, прочитав эти страницы википедии:

Допустим, вы хотели создать топографическую карту (это не моя точная проблема, но концептуально она очень похожа). Таким образом, вы проводите тысячи измерений высоты на площади в одну квадратную милю, но у вашего съемочного оборудования есть предел погрешности плюс-минус 10 метров по высоте.

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

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

Что касается вопроса о том, должен ли один класс отвечать за добавление и обработку запросов, я не уверен на 100%, но я так думаю.

Вот аналогичный пример: классы HashMap и TreeMap позволяют добавлять и запрашивать объекты. Нет отдельных интерфейсов для добавления и запроса.

Оба класса также похожи на мой пример, потому что внутренние структуры данных должны поддерживаться на постоянной основе для поддержки механизма запросов. Класс HashMap должен периодически выделять новую память, повторно хэшировать все объекты и перемещать объекты из старой памяти в новую память. TreeMap должен постоянно поддерживать баланс дерева, используя структуру данных красно-черного дерева.

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

Ответы [ 6 ]

4 голосов
/ 29 октября 2008

Если объект имеет два режима, подобных этому, я бы предложил выставить клиенту два интерфейса. Если объект находится в режиме добавления, вы должны быть уверены, что клиент может использовать только реализацию IAppendable. Чтобы перейти в режим запроса, вы добавляете метод IAppendable, например, AsQueryable. Чтобы вернуться назад, вызовите IQueryable.AsAppendable.

Вы можете реализовать IAppendable и IQueryable для одного и того же объекта и внутренне отслеживать состояние одним и тем же способом, но наличие двух интерфейсов позволяет клиенту понять, в каком состоянии находится объект, и заставляет клиента сознательно выполнять (дорогой) выключатель.

2 голосов
/ 29 октября 2008

Я обычно предпочитаю иметь явное изменение, а не лениво пересчитывать результат. Такой подход делает производительность утилиты более предсказуемой и уменьшает объем работы, которую я должен выполнить, чтобы обеспечить хороший пользовательский опыт. Например, если это происходит в пользовательском интерфейсе, где я должен беспокоиться о появлении песочных часов и т. Д.? Какие операции будут блокироваться на переменное количество времени и должны выполняться в фоновом потоке?

Тем не менее, вместо явного изменения состояния одного экземпляра, я бы рекомендовал Pattern Builder для создания нового объекта. Например, у вас может быть объект-агрегатор, который выполняет небольшую работу при добавлении каждого образца. Тогда вместо предложенного вами метода void flip() у меня будет метод Interpolator interpolator(), который получает копию текущего агрегата и выполняет всю сложную математику. Ваш interpolateAt метод будет на этом новом объекте Интерполятора.

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

Такое разделение обязанностей может помочь создать более поддерживаемые и многократно используемые объектно-ориентированные программы. Объект, который может вернуть Measurement по запрошенному Point, является очень абстрактным, и, возможно, многие клиенты могут использовать ваш интерполятор как одну стратегию, реализующую более общий интерфейс.


Я думаю, что добавленная вами аналогия вводит в заблуждение. Рассмотрим альтернативную аналогию:

Key[] data = new Key[...];
data[idx++] = new Key(...); /* Fast! */
...
Arrays.sort(data); /* Slow! */
...
boolean contains = Arrays.binarySearch(data, datum) >= 0; /* Fast! */

Это может работать как набор, и на самом деле это дает лучшую производительность, чем Set реализации (которые реализованы с помощью хеш-таблиц или сбалансированных деревьев).

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

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

Чтобы ваша аналогия проводилась строго, вам придется "сортировать" (выполнять математическую обработку) свой агрегатор с каждой добавленной вами точкой. Но это звучит так, что это будет непозволительно дорого, и это приводит к шаблонам методов построения или фабрики. Это дает понять вашим клиентам, когда им нужно подготовиться к длительной операции «сортировки».

2 голосов
/ 29 октября 2008

Ваши объекты должны иметь одну роль и ответственность. В вашем случае ContinuousScalarField должен отвечать за интерполяцию?

Возможно, вам лучше сделать что-то вроде:

IInterpolator interpolator = field.GetInterpolator();
Measurement measurement = Interpolator.InterpolateAt(...);

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

1 голос
/ 29 октября 2008

«Я только что использовал ленивую оценку для построения структур данных» - Хорошо

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

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

Поскольку lazy eval подходит для вашего случая использования, придерживайтесь его. Это очень интенсивно используемая модель, потому что она восхитительно надежна и очень хорошо подходит для большинства случаев использования.

Единственной причиной переосмысления этого является (а) изменение варианта использования (смешанное добавление и интерполяция) или (б) оптимизация производительности.

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

Кроме того, метод flip с высоким состоянием (и не очень значимым) не очень полезен для клиентов вашего класса. Тем не менее, разделение интерполяции на две части может быть полезным для них - и помочь вам с оптимизацией и управлением состоянием.

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

public void interpolateAt( Point3d p );
public Measurement interpolatedMasurement();

Это заимствует реляционную базу данных Open и парадигмы Fetch. Открытие курсора может сделать большую предварительную работу и может начать выполнение запроса, вы не знаете. Извлечение первой строки может выполнить всю работу, или выполнить подготовленный запрос, или просто извлечь первую буферизованную строку. Вы действительно не знаете. Вы только знаете, что это операция из двух частей. Разработчики СУБД могут по своему усмотрению оптимизировать.

0 голосов
/ 21 ноября 2012

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

Я предпочитаю использовать структуры данных, которые позволяют мне постепенно добавлять к нему «немного больше работы» для каждого добавления и постепенно извлекать нужные мне данные «немного больше работы» для каждого извлечения.

Возможно, если вы выполните какой-нибудь вызов interpolate_at () в верхнем правом углу вашего региона, вам нужно будет только выполнить вычисления с использованием точек в этом верхнем правом углу, и ничто не помешает оставить остальные 3 сектора открытыми для новых дополнений. (И так далее по рекурсивному KDTree).

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

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

Если объект должен находиться в «состоянии после расчета» до получения из него данных, т.е. некоторая функция do_calculations () должна быть запущена до того, как функция interpolateAt () получит действительные данные, Я предпочитаю позволить функции interpolateAt () проверять, находится ли она уже в этом состоянии, запуск "do_calculations ()" и обновление состояния объекта, если необходимо, и затем возвращаю результаты, которые я ожидал.

Иногда я слышу, как люди описывают такую ​​структуру данных, как «замораживание» данных или «кристаллизация» данных или «компиляция» или «помещение данных в неизменную структуру данных». Одним из примеров является преобразование (изменяемого) StringBuilder или StringBuffer в (неизменяемое) String.

Я могу представить, что для некоторых видов анализа вы ожидаете, что все данных будут заблаговременно, и извлечение некоторого интерполированного значения до того, как все данные будут введены, даст неправильные результаты. В таком случае, Я бы предпочел настроить все так, чтобы функция add_data () не работала или генерировала исключение если он (неправильно) вызывается после любого вызова interpolateAt ().

Я бы рассмотрел определение лениво оцененного объекта "interpolated_point", который не на самом деле оценивает данные сразу, а только говорит той программе, что когда-нибудь в будущем эти данные потребуются , Коллекция на самом деле не заморожена, поэтому можно продолжать добавлять в нее больше данных, вплоть до точки что-то на самом деле извлекает первое реальное значение из некоторого объекта "interpolated_point", которая внутренне вызывает функцию do_calculations () и замораживает объект. Это может ускорить процесс, если вы знаете не только все данные, но и все точки, которые необходимо интерполировать, все заранее. Затем вы можете выбросить данные, которые «далеко» от интерполированных точек, и производите сверхпрочные расчеты только в областях, расположенных "вблизи" интерполированных точек.

Для других видов анализа вы делаете все возможное с имеющимися у вас данными, но когда больше данных поступает позже, вы хотите использовать эти новые данные в своем последующем анализе. Если единственный способ сделать это - отбросить все промежуточные результаты и пересчитать все с нуля, то это то, что вам нужно сделать. (И лучше, если объект автоматически это обрабатывает, вместо того, чтобы требовать, чтобы люди не забывали каждый раз вызывать некоторые функции clear_cache () и do_calculations ()).

0 голосов
/ 29 октября 2008

Вы можете иметь переменную состояния. Есть метод для запуска обработки высокого уровня, который будет работать, только если СОСТОЯНИЕ находится в РАЗДЕЛЕ-1. Он установит состояние на РАЗДЕЛ-2, а затем на РАЗДЕЛ-3, когда будет выполнено вычисление. Если есть запрос к программе для интерполяции заданной точки, она проверит, является ли состояние РАЗДЕЛОМ-3. Если нет, он запросит начало вычислений, а затем интерполирует данные.

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

...