Общие

Утилита индексации N-мерного массива

Я создал приведенный ниже класс, чтобы помочь работать с массивами ND, отображая на основе этот вопрос. Это поможет в реализации кода для обработки извилины.

Как я могу улучшить это? Есть ли что-то существенное, чего мне не хватает в интерфейсе?

заголовок:

class NDArrayIndex{
public:
  NDArrayIndex(
    std::initializer_list<std::uint32_t> dimensions, std::int32_t padding = 0, 
    std::initializer_list<std::uint32_t> position = {}
  );

  NDArrayIndex& set(const std::vector<std::uint32_t>& position);
  NDArrayIndex& step();
  NDArrayIndex& step(std::uint32_t dimension, std::int32_t delta);
  const std::vector<std::uint32_t>& position() const{
    return m_position;
  }
  std::optional<std::uint32_t> calculate_mapped_position(const std::vector<std::uint32_t>& position) const;
  std::optional<std::uint32_t> mapped_position() const{
    return m_mappedIndex;
  }
  bool inside_bounds(const std::vector<std::uint32_t>& position, std::uint32_t dimension = 0u, std::int32_t delta = 0) const;
  bool inside_bounds(std::uint32_t dimension = 0u, std::int32_t delta = 0) const{
    return inside_bounds(m_position, dimension, delta);
  }
  bool inside_bounds(const NDArrayIndex& index, std::uint32_t dimension = 0u, std::int32_t delta = 0) const{
    return inside_bounds(index.position(), dimension, delta);
  }
  bool inside_content(const std::vector<std::uint32_t>& position, std::uint32_t dimension = 0u, std::int32_t delta = 0) const;
  bool inside_content(std::uint32_t dimension = 0u, std::int32_t delta = 0) const{
    return inside_content(m_position, dimension, delta);
  }
  bool inside_content(const NDArrayIndex& index, std::uint32_t dimension = 0u, std::int32_t delta = 0) const{
    return inside_content(index.position(), dimension, delta);
  }

  using IntervalPart = std::pair<std::uint32_t, std::uint32_t>;
  std::vector<IntervalPart> mappable_parts_of(std::uint32_t dimension, std::int32_t delta) const{
    return mappable_parts_of(m_position, dimension, delta);
  }
  std::vector<IntervalPart> mappable_parts_of(
    const std::vector<std::uint32_t>& position, std::uint32_t dimension, std::int32_t delta
  ) const;

  std::uint32_t buffer_size(){
    return m_bufferSize;
  }

private:
  const std::vector<std::uint32_t> m_dimensions;
  const std::int32_t m_padding;
  const std::vector<std::uint32_t> m_strides;
  const std::uint32_t m_bufferSize;
  std::vector<std::uint32_t> m_position;
  std::optional<std::uint32_t> m_mappedIndex;
};

источник:


NDArrayIndex::NDArrayIndex(
  std::initializer_list<std::uint32_t> dimensions, std::int32_t padding, 
  std::initializer_list<std::uint32_t> position
)
: m_dimensions(dimensions)
, m_padding(padding)
, m_strides(init_strides(dimensions, m_padding))
, m_bufferSize(std::accumulate(m_dimensions.begin(), m_dimensions.end(), 1.0, 
  [](const std::uint32_t& partial, const std::uint32_t& element){ return partial * element; }
))
, m_position(init_position(m_dimensions, position))
, m_mappedIndex(calculate_mapped_position(m_position))
{
  assert(0 == std::count(m_dimensions.begin(), m_dimensions.end(), 0));
  assert(inside_bounds(m_position));
}

NDArrayIndex& NDArrayIndex::set(const std::vector<std::uint32_t>& position){
  assert(position.size() == m_position.size());
  assert(inside_bounds(position));
  m_position = position;
  m_mappedIndex = calculate_mapped_position(m_position);
  assert( (!m_mappedIndex.has_value())||(m_mappedIndex.value() < m_bufferSize) );
  return *this;
}

NDArrayIndex& NDArrayIndex::step(){
  std::uint32_t dim = 0;
  bool changed = false;
  while(dim < m_dimensions.size()){
    if(inside_bounds(dim, 1)){
      step(dim, 1);
      break;
    }else{
      changed = true;
      m_position[dim] = 0;
    }
    ++dim;
  }
  if(dim >= m_dimensions.size()){
    m_mappedIndex = 0; /* Overflow happened, start from the beginning */
  }else{
    if(changed)m_mappedIndex = calculate_mapped_position(m_position);
    assert(m_mappedIndex < m_bufferSize);
  }
  return *this;
}

NDArrayIndex& NDArrayIndex::step(std::uint32_t dimension, std::int32_t delta){
  const std::int32_t new_position = static_cast<std::int32_t>(m_position[dimension]) + delta;
  assert(0 <= new_position);
  assert((m_dimensions[dimension] + (2 * std::max(0, m_padding))) > static_cast<std::uint32_t>(new_position));

  m_position[dimension] = new_position;

  bool new_position_is_inside_content = inside_content(m_position);
  if(m_mappedIndex.has_value() && new_position_is_inside_content){ /* m_mappedIndex has a value if the previous position was valid */
    m_mappedIndex.value() += m_strides[dimension] * delta;
    assert(m_mappedIndex < m_bufferSize);
  }else if(new_position_is_inside_content){ /* if the new position is inside bounds, then the mapped index can be caluclated */
    m_mappedIndex = calculate_mapped_position(m_position);
  }else m_mappedIndex = {}; /* No mapped index for positions inside the padding */
  return *this;
}

std::optional<std::uint32_t> NDArrayIndex::calculate_mapped_position(const std::vector<std::uint32_t>& position) const{
  assert(position.size() == m_strides.size());
  if(!inside_content(position))
    return {};

  std::uint32_t result_index = 0u;
  for(std::uint32_t dim = 0; dim < position.size(); ++dim){
    result_index += (position[dim] - std::max(m_padding, -m_padding)) * m_strides[dim];
  }
  return result_index;
}

bool NDArrayIndex::inside_bounds(const std::vector<std::uint32_t>& position, std::uint32_t dimension, std::int32_t delta) const{
  std::uint32_t dimension_index = 0;
  return std::all_of(position.begin(), position.end(), 
    [this, &dimension_index, dimension, delta](const std::uint32_t& pos){
      std::int32_t position = static_cast<std::int32_t>(pos);
      if(dimension_index == dimension) position += delta;
      return( (0 <= position)&&(position < static_cast<int32_t>(2 * std::max(0, m_padding) + m_dimensions[dimension_index++])) );
    }
  );
}

bool NDArrayIndex::inside_content(const std::vector<std::uint32_t>& position, std::uint32_t dimension, std::int32_t delta) const{
  std::uint32_t dimension_index = 0;
  return std::all_of(position.begin(), position.end(), 
    [this, &dimension_index, dimension, delta](const std::uint32_t& pos){
      std::int32_t actual_position = static_cast<std::int32_t>(pos);
      if(dimension_index == dimension) actual_position += delta;
      return( 
        (std::max(m_padding, -m_padding) <= actual_position)
        &&(actual_position < static_cast<std::int32_t>(m_dimensions[dimension_index++] + m_padding)) 
      );
    }
  );
}

std::vector<NDArrayIndex::IntervalPart> NDArrayIndex::mappable_parts_of(
  const std::vector<std::uint32_t>& position, std::uint32_t dimension, std::int32_t delta
) const{
  std::vector<NDArrayIndex::IntervalPart> result;
  bool part_in_progress = false;
  for(std::int32_t delta_index = 0; delta_index < delta; delta_index += std::copysign(1, delta)){
    const bool current_position_in_inside_content = inside_content(position, dimension, delta_index);
    if(current_position_in_inside_content && part_in_progress){
      assert(0 < result.size());
      ++std::get<1>(result.back()); /* Increase the size of the current part of the interval */
    }else if(current_position_in_inside_content){ /* If the interval iteration became inside bounds */
      result.push_back({(position[dimension] + delta_index), 1}); /* Add the new part as a result */
      part_in_progress = true;
    }else part_in_progress = false;
  }
  return result;
}

и со следующими тестами:

TEST_CASE("Testing NDArray Indexing with a 2D array without padding", "[NDArray]"){
  std::uint32_t width = rand()%100;
  std::uint32_t height = rand()%100;
  NDArrayIndex idx({width, height});

  for(std::uint32_t variant = 0; variant < 5; ++variant){
    std::uint32_t x = rand()%width;
    std::uint32_t y = rand()%height;
    idx.set({x,y});
    REQUIRE(idx.inside_bounds());
    REQUIRE(idx.mapped_position().has_value());
    REQUIRE(idx.mapped_position().value() == (x + (y * width)));
    std::uint32_t elements_after_x_row = width - x;
    REQUIRE(1 == idx.mappable_parts_of(0,width).size());
    REQUIRE(x == std::get<0>(idx.mappable_parts_of(0,width)[0]));
    REQUIRE(elements_after_x_row == std::get<1>(idx.mappable_parts_of(0,width)[0]));
    /*!Note: using width in the above interfaces because it is guaranteed
     * that an interval of that size spans over the relevant dimension
     * */
  }

  REQUIRE(idx.buffer_size() == (width * height));
  idx.set({0,0});
  for(std::uint32_t i = 0; i < idx.buffer_size(); ++i){
    REQUIRE(idx.inside_bounds());
    REQUIRE(idx.inside_content());
    REQUIRE(idx.mapped_position().has_value() == true);
    REQUIRE(idx.mapped_position().value() == i);
    idx.step();
  }
}

TEST_CASE("Testing NDArray Indexing with a 2D array with positive padding", "[NDArray][padding]"){
  std::uint32_t width = 1 + rand()%20;
  std::uint32_t height = 1 + rand()%20;
  std::int32_t padding = 5;
  NDArrayIndex idx({width, height}, padding);

  for(std::uint32_t variant = 0; variant < 5; ++variant){
    std::uint32_t x = padding + rand()%(width);
    std::uint32_t y = padding + rand()%(height);
    idx.set({x,y});
    REQUIRE(idx.inside_bounds());
    REQUIRE(idx.mapped_position().has_value());
    REQUIRE( idx.mapped_position().value() == (x - padding + ((y - padding) * width)) );
    std::uint32_t elements_after_x_row = padding + width - x;
    REQUIRE(1 == idx.mappable_parts_of(0,width).size());
    REQUIRE(x == std::get<0>(idx.mappable_parts_of(0,width)[0]));
    REQUIRE(elements_after_x_row == std::get<1>(idx.mappable_parts_of(0,width)[0]));
  }

  REQUIRE(idx.buffer_size() == (width * height));
  std::uint32_t x = 0u;
  std::uint32_t y = 0u;
  std::uint32_t reference_mapped_position = 0u;
  idx.set({0,0});
  for(std::uint32_t i = 0; i < idx.buffer_size(); ++i){
    if(
      (padding <= static_cast<std::int32_t>(x) && x < (padding + width))
      &&(padding <= static_cast<std::int32_t>(y) && y < (padding + height))      
    ){
      REQUIRE(idx.inside_bounds());
      REQUIRE(idx.inside_content());
      REQUIRE(idx.mapped_position().has_value() == true);
      REQUIRE(idx.mapped_position().value() == reference_mapped_position);
      ++reference_mapped_position;
    }else{
      REQUIRE(idx.inside_bounds());
      REQUIRE(idx.mapped_position().has_value() == false);
    } 
    idx.step();
    if(x < padding + width + padding - 1){
      ++x;
    }else{
      x = 0;
      ++y;
    }
  }
}

TEST_CASE("Testing NDArray Indexing with a 2D array with negative padding", "[NDArray][padding]"){
  std::uint32_t width = 11 + rand()%20;
  std::uint32_t height = 11 + rand()%20;
  std::int32_t padding = -5;
  NDArrayIndex idx({width, height}, padding);

  for(std::uint32_t variant = 0; variant < 5; ++variant){
    std::uint32_t x = -padding + rand()%(width + 2 * padding);
    std::uint32_t y = -padding + rand()%(height + 2 * padding);
    idx.set({x,y});

    REQUIRE(idx.inside_bounds());
    REQUIRE(idx.mapped_position().has_value());
    REQUIRE( idx.mapped_position().value() == (x + padding + ((y + padding) * (width + 2 * padding))) );
    std::uint32_t elements_after_x_row = padding + width - x;
    REQUIRE(1 == idx.mappable_parts_of(0,width).size());
    REQUIRE(x == std::get<0>(idx.mappable_parts_of(0,width)[0]));
    REQUIRE(elements_after_x_row == std::get<1>(idx.mappable_parts_of(0,width)[0]));
  }

  REQUIRE(idx.buffer_size() == (width * height));
  std::uint32_t x = 0u;
  std::uint32_t y = 0u;
  std::uint32_t reference_mapped_position = 0u;
  idx.set({0,0});
  for(std::uint32_t i = 0; i < idx.buffer_size(); ++i){
    if(
      (-padding <= static_cast<std::int32_t>(x) && x < (padding + width))
      &&(-padding <= static_cast<std::int32_t>(y) && y < (padding + height))      
    ){
      REQUIRE(idx.inside_bounds());
      REQUIRE(idx.inside_content());
      REQUIRE(idx.mapped_position().has_value() == true);
      REQUIRE(idx.mapped_position().value() == reference_mapped_position);
      ++reference_mapped_position;
    }else{
      REQUIRE(idx.inside_bounds());
      REQUIRE(idx.mapped_position().has_value() == false);
    } 
    idx.step();
    if(x < (width - 1)){
      ++x;
    }else{
      x = 0;
      ++y;
    }
  }
}

2 ответа
2

Добавить документацию Doxygen

Мне трудно понять, какова цель всех этих функций-членов. Добавление Доксиген документация по классу и всем его членам очень поможет.

Вам нужно переменное количество измерений?

Обычно при работе с данными вы уже знаете их размерность. Тогда было бы разумнее сделать NDArrayIndex быть шаблоном с параметром шаблона, являющимся количеством измерений, а затем использовать std::array вместо std::vector для хранения вещей, которые сейчас хранятся в std::vectorс. Это позволит компилятору намного лучше оптимизировать код и избежать выделения памяти.

Даже если вы не знаете количество измерений заранее, возможно, вы можете сделать параметр шаблона максимальным количеством измерений, чтобы вы все равно могли использовать std::arrayс. Учтите, что по крайней мере в Linux на AMD64 размер пустой std::vector составляет 24 байта, что соответствует размеру std::array<uint32_t, 6>.

Почему заполнение скаляром?

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

Предпочитаю объявить struct вместо использования std::pair

Пока std::pair а также std::tuple иногда полезны в универсальном коде, если вы можете просто объявить struct вместо этого предпочитайте последнее. Это позволяет вам давать имена двум элементам пары и избегает уродливых вызовов std::get<>():

struct IntervalPart {
    std::uint32_t start;
    std::uint32_t size;
};

Небезопасные преобразования между знаковыми и беззнаковыми целыми числами

API создает впечатление, что любое беззнаковое 32-битное значение безопасно для использования, но приведение к std::int32_t внутри inside_bounds() делает большие значения небезопасными. Вы должны справиться с этим как-то.

Рассмотрите возможность добавления итераторов

Мне кажется, что в конце концов вы хотите перебрать отображаемую часть многомерного массива. Теперь вам нужно вызвать смесь mappable_parts_of(), step() а также mapped_position(). Но все это медленно; если у вас есть отображаемые части, вам не нужно причудливость step()и вам не нужна проверка границ, выполняемая mapped_position(). Я думаю, что интерфейс, который предоставляет итератор для эффективного перебора отображаемой части, был бы лучшим. Например:

NDArray array = ...;
NDArrayIndex index = ...;

for (auto position: index.mappable_parts_range(...)) {
    do_something_with(array[position]);
}

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

NDArray array1, array2;
float sum = {};
...
for (auto& [el1, el2]: overlapping_range(array1, array2, ...)) {
    sum += el1 * el2;
}

Вам действительно нужно в яблочко 32 бита, где вы используете std::uint32_t? Это предотвращает компиляцию вашего кода там, где 32-битный тип недоступен. Возможно std::uint_fast32_t был бы лучший выбор?

Делиться

Улучшить этот ответ

Похожие записи:

  1. C ++ 20: я — матрица, вещание, np.dot () и np.matmul ()
  2. Функция batch_recursive_count_if с уровнем распаковки для произвольной вложенной итерируемой реализации произвольного типа в C ++
  3. Решатель небоскребов для размера NxN, версия 4
  4. Простая консольная шахматная игра C ++
  5. Программа расчета небоскребов для размера NxN, версия 2 (с использованием функции отслеживания с возвратом)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *