Задачка такая:
На входе имеем достаточно большой 3хмерный массив флоатов (допустим 600x600x600), после его получения необходимо иметь возможность максимально быстро отвечать на внешние запросы, в качестве параметров которых приходят срезы в этом массиве, и надо возвращать минимум и максимум в заданном срезе.
Если каждый раз перебирать все элементы массива в заданном срезе, получается больно уж медленно.
Пока все что приходит в голову это сделать некую пирамиду из подмассивов с предварительно вычисленными значениями (для всех кубов 2х2х2, 4x4x4, 8x8x8 итд), по аналогии с префильтерингом изображений, но может быть есть какие-то более умные решения этой задачи?

Здравствуйте, Михаил Лёсин, Вы писали:

МЛ>Задачка такая:
МЛ>На входе имеем достаточно большой 3хмерный массив флоатов (допустим 600x600x600), после его получения необходимо иметь возможность максимально быстро отвечать на внешние запросы, в качестве параметров которых приходят срезы в этом массиве, и надо возвращать минимум и максимум в заданном срезе.
МЛ>Если каждый раз перебирать все элементы массива в заданном срезе, получается больно уж медленно.
МЛ>Пока все что приходит в голову это сделать некую пирамиду из подмассивов с предварительно вычисленными значениями (для всех кубов 2х2х2, 4x4x4, 8x8x8 итд), по аналогии с префильтерингом изображений, но может быть есть какие-то более умные решения этой задачи?

Может ли изменяться этот массив между запросами?
Что представляет собой срез?

Здравствуйте, Михаил Лёсин, Вы писали:

МЛ>На входе имеем достаточно большой 3хмерный массив флоатов (допустим 600x600x600), после его получения необходимо иметь возможность максимально быстро отвечать на внешние запросы, в качестве параметров которых приходят срезы в этом массиве, и надо возвращать минимум и максимум в заданном срезе.

Самый быстрый отклик — это если заранее найти минимумы и максимумы для всех возможных срезов. То есть, 6 массивов по 600*600 и 6 массивов по 600.
Массивы заполняются за один проход по кубу.

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

Здравствуйте, _DAle_, Вы писали:

_DA>Может ли изменяться этот массив между запросами?
_DA>Что представляет собой срез?

Нет, массив не меняется
Срез это некий куб, заданный минимумальными и максимальными значениями по каждой из координат, например для массива 600x600x600 одним из срезов может быть значения от x=200 y=200 z=200 до x=300 y=250 z=400

Здравствуйте, Кодт, Вы писали:

К>Самый быстрый отклик — это если заранее найти минимумы и максимумы для всех возможных срезов. То есть, 6 массивов по 600*600 и 6 массивов по 600.
К>Массивы заполняются за один проход по кубу.
Боюсь количество всевозможных срезов выйдет за все разумные границы при таком массиве, это далеко не 6*600*600 и 6*600

К>А вот если массив меняется, то это будет дорогое удовольствие — поддерживать таблицу в соответствии.
К>Тут, пожалуй, какие-то деревянные структуры пригодятся.
Массив не меняется

Здравствуйте, Михаил Лёсин, Вы писали:

Могу предложить относительно простой способ ускорения:
Если объем среза не велик то поиск минимума и максимума и так достаточно быстр (например для срезов со сторонами не более 2 нада перебрать не более 8 элементов)
Будем оптимизить для случая более больших срезов.
Разобьем наш массив на срезы фиксированного размера (допустим примерно по KхKхK элементов) и вычислим в каждом из них минимум и максимум, делается это за линейное количество операций (1 проход), памяти потребуется (600/K)x(600/K)x(600/K) элементов.
Теперь все просто, при поступлении запроса нужно перебирать не все элементы среза, а элементы нашего массива, используя свойства min{A}=min{min{P},min{Q}}, где P U Q = A. И придется перебрать примерно в K^3 меньше элементов. Отдельно нужно только обработать случай попадания края среза на ячейки нашего нового массива.
Выбор К осуществляется в зависимости от статистики запросов.

Здравствуйте, Михаил Лёсин, Вы писали:

МЛ>Здравствуйте, _DAle_, Вы писали:

_DA>>Может ли изменяться этот массив между запросами?
_DA>>Что представляет собой срез?

МЛ>Нет, массив не меняется
МЛ>Срез это некий куб, заданный минимумальными и максимальными значениями по каждой из координат, например для массива 600x600x600 одним из срезов может быть значения от x=200 y=200 z=200 до x=300 y=250 z=400

Я бы построил дерево, хранящее минимумы для подкубов, можно Octree, а можно обычное бинарное дерево, просто на первом уровне делим пополам куб по x, на втором получившиеся параллелепипеды по y, на третьем по z, на четвертом опять по x и т.д. Дерево строим до каких-то разумных пределов в зависимости от объема доступной памяти. Можно построить полностью, а можно, например, до кубов вроде 8*8*8, в них придется уже искать минимум перебором попадающих в нашу область ячеек. Само дерево я бы строил в обычном массиве. Если бинарное, то переходя к i*2+1 и i*2+2 ячейкам, если octree, то соответственно, i*8+1, ..., i*8+7.

МЛ>Срез это некий куб

Интересное у вас понятие о срезах.

Здравствуйте, Михаил Лёсин, Вы писали:
судя по описанию задачи вам нужно kd-tree, в частности min/max kd-tree

Здравствуйте, Тролль зеленый и толстый, Вы писали:

МЛ>>Срез это некий куб
ТЗИ>Интересное у вас понятие о срезах.
Может это срез в 4-х мерном (или более) пространстве

Здравствуйте, Михаил Лёсин, Вы писали:

МЛ>На входе имеем достаточно большой 3хмерный массив флоатов (допустим 600x600x600), после его получения необходимо иметь возможность максимально быстро отвечать на внешние запросы, в качестве параметров которых приходят срезы в этом массиве, и надо возвращать минимум и максимум в заданном срезе.
МЛ>Если каждый раз перебирать все элементы массива в заданном срезе, получается больно уж медленно.

Можно попробовать старый древний симплекс-метод. Ключевые слова — опримизация симплекс-методом. Не знаю, насколько поможет.