1

I have a vector of pairs, which really just store whether cells in a 2D grid are active.

vector<pair <int,int>> cellsActive; 

Now I'm trying to print an arbitrary part of the whole 2D grid, in which all non-active cells are represented with a . and the active cells are represented by a #.

I implemented this is as following:

  1. Create an array myGrid as big as the 2D grid and set every character to .
  2. Iterate through the cellsActive vector and get each active cell: activeCell
  3. Change the grid so that every activeCell location (pair <int int>) is now represented by a #; myGrid[activeCell.first][activeCell.second] = "#"
  4. Now that myGrid correctly holds the values of all cells; loop through the arbitrary part of the myGrid and print it.

However, I feel like I should be able to do this more efficiently by just printing the arbitrary part that I want to print as . except for the relevant activeCell locations that needs to be printed in the form of a #. If I find a way to do it like that, I do not have to construct the whole 2D grid and then loop through it again to print it. But on the other hand, I do not know how to efficiently go through the cellsActive list and find the relevant cells that I need to represent by a #.

I.e. I could do this:

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 << ".";
        }
    }
}

but then I have to search through the whole cellsActive vector every time, which seems to be computationally inefficient if the cellsActive and arbitrary_x and arbitrary_y are large.

My question is, what is the computationally the most efficient way to print these . and # in C++?

8
  • FYI: Sparse matrix. Though, I'm not quite sure about the "most efficient" way in your case - sparse matrix is the general term worth to research for. Mar 31, 2020 at 7:57
  • Iterate over cellsActive and test if (it->first < arbitrary_y && it->second < arbitrary_x) to get the #s?
    – mch
    Mar 31, 2020 at 7:57
  • 2
    Given no further conditions. Your first method is quite efficient in terms of clock cycles. But if cellsActive are presorted in the y then x axis. You could do a O(n) iteration through the vector to determine if the current cell is on by having a pointer/index that only increments if the cell it points to is the current cell.
    – Mary Chang
    Mar 31, 2020 at 8:01
  • 1
    Can you sort CellsActive?
    – Jarod42
    Mar 31, 2020 at 8:04
  • @Jarod42 Yes, I could, but then I have to sort the vector first. I thought about that, but I wonder whether it actually reduces complexion or not. I guess it all depends really. Because the sorting algorithm also depends on how the vector is indexed before sorting etc. Maybe I should do benchmarking. Mar 31, 2020 at 8:15

1 Answer 1

1

I see 2 interesting ways:

  • create buffer result, and fill it:

    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.
    
    • Complexity: max(O(N), O(arbitrary_x * arbitrary_y))
    • Extra memory: arbitrary_x * arbitrary_y
  • Or sort cellsActive and do a merge-like code.

    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 '.'.
    
    • Complexity: max(O(N log N), O(arbitrary_x * arbitrary_y))
    • No extra memory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.