リングバッファのdeque

Astral-23 commented 4 months ago

template<typename T> struct simple_deque {
    vector<T> data;
    int offset = 0;
    int n = 0;  // 格納されている要素数
    int cap = 0; // 配列のサイズ
    int mask = -1; // 2冪で割り算をする為のbitmask

    simple_deque(){}
    void expand() {
        if(cap == 0) {
            ++cap;
            ++mask;
        } else {
            cap *= 2;
            mask = mask * 2 + 1;
        }

        data.resize(cap);
        for(int i = 0; i < offset; i++) {
            data[(i + n) & mask] = data[i];
        }
    }
    void push_front(T x) {
        if(n == cap) expand();
        --offset;
        if(offset < 0) offset += cap;
        data[offset] = x;
        ++n;
    }

    void pop_front() {
        offset = (offset + 1) & mask;
        --n;
    }

    void push_back(T x) {
        if(n == cap) expand();
        data[(offset + n) & mask] = x;
        ++n;
    }

    void pop_back() {
        --n;
    }

    T front() {
        return data[offset];
    }

    T back() {
        return data[(offset + n - 1) & mask];
    }

    void reserve(int siz) {
        while(cap < siz) expand();
    }

    int size() {
        return n;
    }

    vector<T> dump() {
        vector<T> res;
        int i = offset;
        for(int t = 0; t < n; t++) {
            res.push_back(data[i]);
            i = (i + 1) & mask;
        }
        return res;
    }
};

作った最適化かけたらstd::dequeとあんまし変わんなかった(´◦ω◦｀)

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
TT using minheap = priority_queue<T, vector<T>, greater<T>>;
TT using maxheap = priority_queue<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
TT int pre_id(vec<T> &A, T x) {  // must sorted
    return lower_bound(all(A), x) - A.begin() - 1;
}
TT int nex_id(vec<T> &A, T x) {  // must sorted
    return upper_bound(all(A), x) - A.begin();
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

template<typename T> struct simple_deque {
    vector<T> data;
    int offset = 0;
    int n = 0;  // 格納されている要素数
    int cap = 0; // 配列のサイズ
    int mask = -1; // 2冪で割り算をする為のbitmask

    simple_deque(){}
    void expand() {
        if(cap == 0) {
            ++cap;
            ++mask;
        } else {
            cap *= 2;
            mask = mask * 2 + 1;
        }

        data.resize(cap);
        for(int i = 0; i < offset; i++) {
            data[(i + n) & mask] = data[i];
        }
    }
    void push_front(T x) {
        if(n == cap) expand();
        --offset;
        if(offset < 0) offset += cap;
        data[offset] = x;
        ++n;
    }

    void pop_front() {
        offset = (offset + 1) & mask;
        --n;
    }

    void push_back(T x) {
        if(n == cap) expand();
        data[(offset + n) & mask] = x;
        ++n;
    }

    void pop_back() {
        --n;
    }

    T front() {
        return data[offset];
    }

    T back() {
        return data[(offset + n - 1) & mask];
    }

    void reserve(int siz) {
        while(cap < siz) expand();
    }

    int size() {
        return n;
    }

    vector<T> dump() {
        vector<T> res;
        int i = offset;
        for(int t = 0; t < n; t++) {
            res.push_back(data[i]);
            i = (i + 1) & mask;
        }
        return res;
    }
};

int main() {

    simple_deque<int> deq;
    deque<int> tru;
    int test_size = 1'000'000;

    auto dump = [&]() {
        vector<int> res;
        for(int i = 0; i < tru.size(); i++) {
            res.push_back(tru[i]);
        }
        return res;
    };

    for(int i = 0; i < test_size; i++) {
        int t = rand() % 4;
        int x = rand() % 100000;
        if(t == 0) {
            deq.push_back(x);
            tru.push_back(x);
        }
        else if(t == 1) {
            deq.push_front(x);
            tru.push_front(x);
        }
        else if(t == 2) {
            if(deq.size()) {
                deq.pop_back();
                tru.pop_back();
            }
        }
        else if(t == 3) {
            if(deq.size()) {
                deq.pop_front();
                tru.pop_front();
            }
        }

        assert(dump() == deq.dump());
        assert(deq.size() == tru.size());
    }

}

Astral-23 commented 4 months ago

あの　マージテクをちゃんとやりなさい

template<typename T> struct simple_deque {
    vector<T> data;
    int offset = 0;
    int n = 0;  // 格納されている要素数
    int cap = 0; // 配列のサイズ
    int mask = -1; // 2冪で割り算をする為のbitmask

    simple_deque(){}
    void expand() {
        if(cap == 0) {
            ++cap;
            ++mask;
        } else {
            cap *= 2;
            mask = mask * 2 + 1;
        }

        data.resize(cap);
        int front_siz = n - offset;//[0, 1, 2, 3, ..., k]
        int back_siz = n - front_siz;//[k, k + 1, k + 2...]
        if(front_siz > back_siz) {
            for(int i = 0; i < offset; i++) {
                data[i + n] = data[i];
            }
        }
        else {
            for(int i = n - 1; i >= offset; i--) {
                data[i + n] = data[i];
            }
            offset += n;
        }
    }
    void push_front(T x) {
        if(n == cap) expand();
        --offset;
        if(offset < 0) offset += cap;
        data[offset] = x;
        ++n;
    }

    void pop_front() {
        offset = (offset + 1) & mask;
        --n;
    }

    void push_back(T x) {
        if(n == cap) expand();
        data[(offset + n) & mask] = x;
        ++n;
    }

    void pop_back() {
        --n;
    }

    T front() {
        return data[offset];
    }

    T back() {
        return data[(offset + n - 1) & mask];
    }

    void reserve(int siz) {
        while(cap < siz) expand();
    }

    int size() {
        return n;
    }

    vector<T> dump() {
        vector<T> res;
        int i = offset;
        for(int t = 0; t < n; t++) {
            res.push_back(data[i]);
            i = (i + 1) & mask;
        }
        return res;
    }
};

Astral-23 commented 4 months ago

最適化マシマシで実行速度が25%減だった

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
TT using minheap = priority_queue<T, vector<T>, greater<T>>;
TT using maxheap = priority_queue<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
TT int pre_id(vec<T> &A, T x) {  // must sorted
    return lower_bound(all(A), x) - A.begin() - 1;
}
TT int nex_id(vec<T> &A, T x) {  // must sorted
    return upper_bound(all(A), x) - A.begin();
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

template<typename T> struct simple_deque {
    vector<T> data;
    int offset = 0;
    int n = 0;  // 格納されている要素数
    int cap = 0; // 配列のサイズ
    int mask = -1; // 2冪で割り算をする為のbitmask

    simple_deque(){}
    void expand() {
        if(cap == 0) {
            ++cap;
            ++mask;
        } else {
            cap *= 2;
            mask = mask * 2 + 1;
        }

        data.resize(cap);
        int front_siz = n - offset;//[0, 1, 2, 3, ..., k]
        int back_siz = n - front_siz;//[k, k + 1, k + 2...]
        if(front_siz > back_siz) {
            for(int i = 0; i < offset; i++) {
                data[i + n] = data[i];
            }
        }
        else {
            for(int i = n - 1; i >= offset; i--) {
                data[i + n] = data[i];
            }
            offset += n;
        }
    }
    void push_front(T x) {
        if(n == cap) expand();
        --offset;
        if(offset < 0) offset += cap;
        data[offset] = x;
        ++n;
    }

    void pop_front() {
        offset = (offset + 1) & mask;
        --n;
    }

    void push_back(T x) {
        if(n == cap) expand();
        data[(offset + n) & mask] = x;
        ++n;
    }

    void pop_back() {
        --n;
    }

    T front() {
        return data[offset];
    }

    T back() {
        return data[(offset + n - 1) & mask];
    }

    void reserve(int siz) {
        while(cap < siz) expand();
    }

    int size() {
        return n;
    }

    vector<T> dump() {
        vector<T> res;
        int i = offset;
        for(int t = 0; t < n; t++) {
            res.push_back(data[i]);
            i = (i + 1) & mask;
        }
        return res;
    }
};

int main() {

    simple_deque<int> deq;
    deque<int> tru;
    int test_size = 1'000'00;

    auto dump = [&]() {
        vector<int> res;
        for(int i = 0; i < tru.size(); i++) {
            res.push_back(tru[i]);
        }
        return res;
    };

    for(int i = 0; i < test_size; i++) {
        int t = rand() % 4;
        int x = rand() % 100000;
        if(t == 0) {
            deq.push_back(x);
            tru.push_back(x);
        }
        else if(t == 1) {
            deq.push_front(x);
            tru.push_front(x);
        }
        else if(t == 2) {
            if(deq.size()) {
                deq.pop_back();
                tru.pop_back();
            }
        }
        else if(t == 3) {
            if(deq.size()) {
                deq.pop_front();
                tru.pop_front();
            }
        }

        assert(dump() == deq.dump());
        assert(deq.size() == tru.size());
    }

}

Astral-23 commented 4 months ago

メモ : 非自明かもしれませんが、reserveはこれで上手くいっている筈

Astral-23 / competitive-programing

リングバッファのdeque #9