3
\$\begingroup\$

I have a task where I need to write my own deque and to this code was executed for 1 second, I get a result of 1.09 sec. The max count of elements is 1000000. How can I optimize it for better performance? Where can it have a low part of code? I increased a buffer from 12 to 1000001, disabled the decrease function but it is still too slow.

#include <iostream>
#include <algorithm>

/**
 * @brief The operations enum to mark operation codes
 */
enum operations {
    PUSH_FRONT = 1,
    POP_FRONT = 2,
    PUSH_BACK = 3,
    POP_BACK = 4
};

/**
 * @brief The deque class that represents the double-ended queue
 */
class deque {
    const int INC_ARRAY = 1000001;

    int m_size;
    int m_capacity;
    int* m_head;

public:
    const int EMPTY_DEQUE = -1;

    /**
     * @brief Constructor
     */
    deque() : m_size{0}, m_capacity{INC_ARRAY} {
        m_head = new int[m_capacity];
    }

    /**
     * @brief Copy constructor (disabled)
     * @param that Instance for copy
     */
    deque(const deque& that) = delete;

    /**
     * @brief Move constructor
     * @param other Instance for moving
     */
    deque(deque&& other) {
        m_head = other.m_head;
        m_size = other.m_size;
        m_capacity = other.m_capacity;
        other.m_head = nullptr;
    }

    ~deque() {
        delete[] m_head;
    }

    /**
     * @brief The deque size
     * @return Size
     */
    int size() const
    {
        return m_size;
    }

    /**
     * @brief Checks if deque is empty
     * @return Is empty?
     */
    bool empty() {
        return m_size == 0;
    }

    /**
     * @brief Pushes a new item at the front of deque
     * @param value Item value
     */
    void push_front(int value) {

        if (!increase(1)) {
            shift();
        }

        m_head[0] = value;
        ++m_size;
    }

    /**
     * @brief Pushes a new item at the back of deque
     * @param value Item value
     */
    void push_back(int value) {
        increase();
        m_head[m_size++] = value;
    }

    /**
     * @brief Pops item from the front of deque
     * @return Item value (-1 if deque is empty)
     */
    int pop_front() {

        if (empty()) {
            return EMPTY_DEQUE;
        }

        auto value = m_head[0];
        shift(true);
        --m_size;
        //decrease();

        return value;
    }

    /**
     * @brief Pops item from the back of deque
     * @return Item value (-1 if deque is empty)
     */
    int pop_back() {

        if (empty()) {
            return EMPTY_DEQUE;
        }

        auto value = m_head[m_size - 1];
        --m_size;
        //decrease();

        return value;
    }

private:

    /**
     * @brief Increases a buffer size
     * @param offset Offset for free items
     * @return Was the buffer size increased?
     */
    bool increase(int offset = 0) {
        int required_size = offset + m_size;

        if (required_size < m_capacity) {
            return false;
        }

        do {
            m_capacity += INC_ARRAY;
        } while (required_size > m_capacity);

        auto tmp = new int[m_capacity];
        std::copy(m_head, m_head + m_size, tmp + offset);
        delete[] m_head;
        m_head = tmp;

        return true;
    }

    /**
     * @brief Decreases the buffer size when it is needed
     * @return Was the buffer size reduced?
     */
    bool decrease() {

        if (m_size > m_capacity - INC_ARRAY || m_capacity <= INC_ARRAY) {
            return false;
        }

        m_capacity -= INC_ARRAY;
        auto tmp = new int[m_capacity];
        std::copy(m_head, m_head + m_size, tmp);
        delete[] m_head;
        m_head = tmp;

        return true;
    }

    /**
     * @brief Shifts all elements to one position
     * @param inverse Will it be shifted at the end?
     */
    void shift(bool inverse = false) {

        if (inverse) {

            for (int i = 1; i <= m_size; ++i) {
                m_head[i - 1] = m_head[i];
            }
        } else {

            for (int i = m_size - 1; i >= 0; --i) {
                m_head[i + 1] = m_head[i];
            }
        }
    }
};

/**
 * @brief Executes operations
 * @param deq Reference to the deque instance
 */
void exec(deque& deq) {
    int cmds_count;
    std::cin >> cmds_count;
    bool is_ok = true;

    for (int i = 0; i < cmds_count; ++i) {
        int code, value, item;
        std::cin >> code >> value;

        switch (code) {
        case PUSH_FRONT:
            deq.push_front(value);
            break;
        case PUSH_BACK:
            deq.push_back(value);
            break;
        case POP_FRONT:
            item = deq.pop_front();

            if (item != value) {
                is_ok = false;
            }

            break;
        case POP_BACK:
            item = deq.pop_back();

            if (item != value) {
                is_ok = false;
            }

            break;
        }
    }

    if (is_ok) {
        std::cout << "YES";
    } else {
        std::cout << "NO";
    }
}

int main()
{
    deque deq;
    exec(deq);

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Up to a 1000000 elements. Sounds like Dr Doom. This is a small list by most modern computer standards. \$\endgroup\$ – Martin York Oct 20 '17 at 16:51
2
\$\begingroup\$

Performance

Right now, your pop_front is linear on the number of items in the deque--that is, every time you do a pop_front, you move the entire content of the deque, so the first item is always at m_head[0].

That means your push_front is also linear--that is, you normally plan on shifting everything in the deque to make room for that item to become m_head[0]. This means that operations (either push or pop) on the front will get quite expensive if the deque holds very many items.

There are quite a few possible ways of dealing this this. One that's fairly simple (but still usually pretty fast) is to maintain pointers to the first item and one past the last item in the deque. When you create the deque, initialize them to the middle of the storage.

Then, the important part: when they reach the end of the storage, just wrap them around to the other end. The only thing you need to look out for is one of them "overtaking" the other, which would overwrite data--for that case, you do need a linear operation (re-allocate, and copy the data to the new buffer). But, in particular, this means pops are always constant time, and pushes are constant time except if you exceed the current capacity so you have to reallocate the buffer and copy data from the old to the new buffer.

You can also make that amortized constant complexity if you want--instead of increasing the size of the collection linearly, multiply the previous size by some factor (like std::vector does, just for one well-known example).

Here's a really minimal version (e.g., doesn't include expansion if you overflow the size of the deque) to demonstrate the general idea:

#include <memory>
#include <iostream>

template <class T>
class deque {
    size_t capacity;
    T *storage;
    size_t front;
    size_t back;
public:
    deque(size_t capacity) 
        : capacity(capacity)
        , storage(new T[capacity])
        , front(capacity/2)
        , back(front+1)
    { }

    void push_front(T const &t) {
        storage[front] = t;
        if (front == 0)
            front = capacity;
        else
            --front;
        if (front == back)
            throw std::runtime_error("deque overflow (push_front)");
    }

    void pop_front(T &t) {
        if (front == capacity)
            front = 0;
        else
            ++front;
        if (back == front)
            throw std::runtime_error("Deque underflow (pop_front)");
        t = storage[front];
    }

    void push_back(T const &t) {
        *(storage+back) = t;
        ++back;
        if (back == front)
            throw std::runtime_error("deque overflow (push_back)");
        if (back == capacity)
            back = 0;
    }

    void pop_back(T &t) {
        if (back == 0)
            back = capacity - 1;
        else
            --back;
        if (back == front)
            throw std::runtime_error("Deque underflow (pop_back)");
        t = *(storage + back);
    }

    ~deque() { delete[] storage; }
};

Non-performance

Although the code above basically imitates this mistake in your code, you should really use something like a std::unique_ptr for the storage. The obvious advantage is that this automatically cleans up the memory, reducing the chance of a memory leak.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for offering! Seems it must improve performance really \$\endgroup\$ – Шах Oct 20 '17 at 11:46
2
\$\begingroup\$

Handling of special values

Ignoring for now, that the choice of returning a special value instead of throwing an exception (or using some other means of indicating error) when poping from an empty queue isn't that great.

Then, if you have a special value ("magic value") like EMPTY_DEQUE which will be returned on an empty queue, then it's crucial that you cannot push this value into the queue. So check for that in push_front and push_back.

Useful testing

    case POP_FRONT:
        item = deq.pop_front();

        if (item != value) {
            is_ok = false;
        }

You're wasting an opportunity for some useful testing output: For example, you could print something like "POP_FRONT, expected {value} but got {item}". If you want to "beef it up" further, then keep a line / instruction count and output that as well.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Code Review

This seems redundant! Don't you use specific method names to indicate the operation.

/**
 * @brief The operations enum to mark operation codes
 */
enum operations {
    PUSH_FRONT = 1,
    POP_FRONT = 2,
    PUSH_BACK = 3,
    POP_BACK = 4
};

Magic numbers very worrying.

    const int EMPTY_DEQUE = -1;

Sure.

    deque() : m_size{0}, m_capacity{INC_ARRAY} {
        m_head = new int[m_capacity];
    }

Don't try and save space like that you are making the code less readable. Like normal variable declarations use one line per variable so we can read them easily.

So you delete the copy constructor.

    deque(const deque& that) = delete;

But what about the copy assignment operator. This seems to be missing and will lead to exactly the same issue as not deleting the copy constructor.

Sure.

    deque(deque&& other) {
        m_head = other.m_head;
        m_size = other.m_size;
        m_capacity = other.m_capacity;
        other.m_head = nullptr;
    }

The standard way is to implement using the swap operator. Also move constructor and move copy assignment should usually be marked as noexcept this will allow better optimizations when you use your object with he standard libraries.

I normally write move like this:

    deque(deque&& other) noexcept
        : m_head(nullptr
        , m_size(0)
        , m_capacity(0)
    {
        swap(other);
    }
    deque& operator=(deque&& other) noexcept
    {
        swap(other)
        return *this;
    }
    void swap(deque& other) noexcept
    {
        using std::swap;
        swap(m_head,     other.m_head);
        swap(m_size,     other.m_size);
        swap(m_capacity, other.m_capacity);
    }

OK. Now we see an efficiency problem.

    void push_front(int value) {

        if (!increase(1)) {
            shift();
        }

        m_head[0] = value;
        ++m_size;
    }

Every item we push on the front you have to move all the elements up one place. The whole point of a deque (double ended queue) is that pushes to the front moves the beginning of the queue back (so you move move the "beginning" you don't move the other elements).

Think of it as a block of memory

    ****************************************************
    ^         ^                   ^                     ^
    |         |                   |                     End of block
    |         |                   End of Data           (one past usually)
    |         |                   (one past usually)
    |         Beginning of Data
    |
    Beginning of block
  • if you add to the back you move "End of Data".
  • if you add to the front you move "Beginning of Data"

If can't move either of these points you chain another block onto the queue. So you allocate in large chunks, but you don't have to re-allocate already allocated chunks.

This gives several advantages.

  • Iterators/pointers are never invalidated.
  • Allocation does not need to move elements already in the dequeue

In addition to efficiency concerns you have issues with correctness if the object contained is for a type T that can potentially throw during a copy or move. Luckily your type T is limited to int so there are no issues there yet.

More efficiency problems.

    int pop_front() {

        // Why are you checking for empty.
        // That is the responsability of the user of your class.
        // If I know I have put a 100 items in the queue and then pop
        // a hundred items from the queue then you are making me pay
        // for a check that I don't use. The branch predication
        // breaking can cause all sorts of issues.
        //
        // Also the normal use case is
        //     while(!q.empty())
        //         int val = q.pop_front();
        //
        // So in this use case you are forcing me to call `empty()`
        // twice. Why are you forcing me to call empty twice.
        //
        // Also we have correctness issues. You have a magic number here
        // Which is also a perfectly valid data value.
        // So if I was popping values and I see -1 come from a pop_front
        // Then I have to wonder if accidentally got a -1 in the data
        // or have I got an empty queue. I can't even check empty()
        // because if this is the last value then empty is going to be true.
        if (empty()) {
            return EMPTY_DEQUE;
        }

        // Making a copy of the value.
        // That should be unneeded.
        auto value = m_head[0];


        // Then we have the problem of efficiency 
        // having to move all the values again.
        shift(true);

        --m_size;
        //decrease();

        return value;
    }

Again the pop_back() has the inefficiency of forcing a check that is not needed. Also causes branch predication problems.

    int pop_back() {

        if (empty()) {
            return EMPTY_DEQUE;
        }

        auto value = m_head[m_size - 1];
        --m_size;
        //decrease();

        return value;
    }

Again because you are implementing a dequeue like a vector your increase in size is very expensive because of the copy you are making.

    bool increase(int offset = 0) {

        // You are copying the whole memory segment
        // rather than just creating a new block.
        auto tmp = new int[m_capacity];

        // Don't use copy when you you can use move.
        // A move is no more expensive than a move but
        // will be much more efficient if the type knows how to move.
        std::copy(m_head, m_head + m_size, tmp + offset);

        // This is exceedingly dangerous.
        // never delete things that belong to the object.
        // If any of the members throw an exception during destruction
        // then your object is left in an inconsistent state.
        delete[] m_head;
        m_head = tmp;

        // It should be done by swaping the tmp and the m_head
        // then calling delete. That way of there are any exceptions
        // your object is still in a good state.
        //     std::swap(m_head, tmp);
        //     delete [] tmp;

        return true;
    }

All the same issues in decrease as there are in increase.

    bool decrease() {
        }

Shift should be using std::move on each element. Not using the copy.

    void shift(bool inverse = false) {

        if (inverse) {

            for (int i = 1; i <= m_size; ++i) {
                m_head[i - 1] = m_head[i];
            }
        } else {

            for (int i = m_size - 1; i >= 0; --i) {
                m_head[i + 1] = m_head[i];
            }
        }
    }
};
| improve this answer | |
\$\endgroup\$

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.