Эффективно go через значения из вектора - PullRequest
Новая
       10

Эффективно go через значения из вектора

1 голос
/ 31 марта 2020

У меня есть вектор пар, который на самом деле просто хранит информацию о том, активны ли ячейки в 2D-сетке. 

vector<pair <int,int>> cellsActive;

Теперь я пытаюсь напечатать произвольную часть всей 2D-сетки, в которой все неактивные клетки представлены ., а активные клетки представлены #.

Я реализовал это следующим образом:

  1. Создайте массив myGrid размером с 2D-сетку и установите для каждого символа .
  2. Итерируйте по вектор cellsActive и получите каждую активную ячейку: activeCell
  3. Измените сетку так, чтобы каждое местоположение activeCell (pair <int int>) теперь представлялось #; myGrid[activeCell.first][activeCell.second] = "#"
  4. Теперь, когда myGrid правильно содержит значения всех ячеек; l oop через произвольную часть myGrid и распечатайте его.

Однако я чувствую, что смогу сделать это более эффективно, просто распечатав произвольную часть, которую я хочу напечатать как ., за исключением соответствующих activeCell местоположений, которые должны быть напечатан в виде #. Если я найду способ сделать это таким образом, мне не нужно будет создавать всю двумерную сетку, а затем l oop через нее снова, чтобы напечатать ее. Но с другой стороны, я не знаю, как эффективно go через список cellsActive и найти соответствующие ячейки, которые мне нужно представить с помощью #.

Т.е. я мог бы сделать это: 

for (int y=0; y<arbitrary_y;y++) {
    for (int x=0; x<arbitrary_x;x++) {
        pair <int int> j = make_pair(y, x);
        vector<intpair>::iterator it = find(cellsActive.begin(), cellsActive.end(), j);
        if (it != cellsActive.end()) {
            cout << "#";
        }
        else {
            cout << ".";
        }
    }
}

, но тогда мне придется каждый раз искать по всему вектору cellsActive, что кажется вычислительно неэффективным, если cellsActive и arbitrary_x и arbitrary_y большие.

Мой вопрос: какой вычислительный самый эффективный способ распечатать эти . и # на C ++?

1 Ответ

1 голос
/ 31 марта 2020

Я вижу 2 интересных способа:

  • создать буферный результат и заполнить его: 

    std::vector<std::vector<char>> chars(arbitrary_x, std::vector<char>(arbitrary_y, '.'));
// or even better std::vector<char> chars(arbitrary_x * arbitrary_y, '.');

for (auto [x, y] : cellsActive) {
    if (x < arbitrary_x && y < arbitrary_y) { chars[x][y] = '#'; }
}

// display chars.
    • Сложность: max(O(N), O(arbitrary_x * arbitrary_y))
    • Дополнительная память: arbitrary_x * arbitrary_y

  • Или отсортировать cellsActive и выполнить код, подобный слиянию. 

    auto comp = [](const auto& lhs, const auto& rhs){
    return std::tie(lhs.second, lhs.first) < std::tie(rhs.second, rhs.first);
};
std::sort(cellsActive.begin(), cellsActive.end(), comp);
auto it = cellsActive.begin();

for (int y = 0; y < arbitrary_y; y++) {
    for (int x = 0; x < arbitrary_x; x++) {
        const std::pair p{x, y};

        while (it != cellsActive.end() && comp(*it, p)) {
            ++it;
        }
        if (it != cellsActive.end() && *it == p) {
            std::cout << '#';
        } else {
            std::cout << '.';
        }
    }
}
// You can even break the loops when `it` reaches the end and print remaining '.'.
    • Сложность: max(O(N log N), O(arbitrary_x * arbitrary_y))
    • Нет дополнительной памяти.
...