LRU 实现

2019-04-272019-05-03 yuiwongComputer science

LRU 实现

LRU:

Least recently used, 最近最少(least)使用: 对于当前所有缓存, 后续使用时, 缓存满的时候,
最近使用的缓存被移除的概率最小(最后被移除)! .. 即缓存满的时候最先移除最近最少使用的!

(Discards the least recently used items first, i.e. once a cache used, then it least likely to be removed when caches full!!)

参考: https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU

C++ 实现: 使用双链表存储缓存以及使用 hash map 查找缓存!

See also:

template<typename K, typename V>
class LruCache {
public:
    /// Internal cache type.
    using Cache = std::tuple<K, V>;
    /// Cache datas type.
    using Caches = DoublyLinkedList<Cache>;
    /// Key to cache iterator type.
    using KeyCaches = std::unordered_map<K, typename Caches::Iterator>;
    /// Default ctor.
    LruCache() noexcept;
    /// Dtor
    ~LruCache() noexcept;
    /// @return caches capacity.
    inline int32_t getCapacity() const noexcept;
    /// @return current caches size.
    inline int32_t getSize() const noexcept;
    /// Check whether this caches empty.
    inline bool isEmpty() const noexcept;
    /**
     * Set cache capacity.
     * @param capacity the capacity to set, NOTE: should >= current caches
     * and > 0.
     * @return true when set success, otherwise false.
     */
    inline bool setCapacity(const int32_t capacity) noexcept;
    /**
     * Set or update cache of key.
     * @param key the key to set.
     * @param value the value to set.
     */
    void set(K&& key, V&& value) noexcept;
    void set(const K& key, V&& value) noexcept;
    void set(K&& key, const V& value) noexcept;
    void set(const K& key, const V& value) noexcept;
    /// Check whether has cache of key.
    inline bool has(const K& key) const noexcept;
    /**
     * Get cache of key.
     * @param key the key to get cache.
     * @return the cache of key.
     * @return true when success otherwise false.
     */
    bool get(const K& key, V& value) const noexcept;
    /**
     * Get cache of key, if not exists, value is default.
     * @param key the key to get cache.
     * @return the cache of key.
     * @sa
     * - has
     * - get
     * - set
     */
    V& operator[](const K& key) noexcept;
    /// @throw std::logic_error when no such key.
    const V& operator[](const K& key) const;
    /// @return caches.
    inline const Caches& getCaches() const noexcept;
    /// Clear all caches.
    inline void clear() noexcept;
private:
    mutable Caches caches;///< The cache datas.
    KeyCaches keyCaches;///< { key, cacheIterator }.
    int32_t capacity{ 16 };///< The capacity of cache(max caches), default 16.
};

template<typename K, typename V>
LruCache<K, V>::LruCache() noexcept {}
template<typename K, typename V>
LruCache<K, V>::~LruCache() noexcept {}
template<typename K, typename V>
inline int32_t LruCache<K, V>::getCapacity() const noexcept
{
    return this->capacity;
}
template<typename K, typename V>
inline int32_t LruCache<K, V>::getSize() const noexcept
{
    return this->caches.size();
}
template<typename K, typename V>
inline bool LruCache<K, V>::isEmpty() const noexcept
{
    return this->caches.empty();
}
template<typename K, typename V>
bool LruCache<K, V>::setCapacity(const int32_t capacity) noexcept
{
    if (capacity < 1) {
        return false;
    }
    if (uint32_t(capacity) < this->caches.size()) {
        return false;
    }
    this->capacity = capacity;
    return true;
}
template<typename K, typename V>
void LruCache<K, V>::set(K&& key, V&& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = std::move(value);
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, std::move(value) });
        this->keyCaches[std::move(key)] = this->caches.begin();
    }
}
template<typename K, typename V>
void LruCache<K, V>::set(const K& key, V&& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = std::move(value);
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, std::move(value) });
        this->keyCaches[key] = this->caches.begin();
    }
}
template<typename K, typename V>
void LruCache<K, V>::set(K&& key, const V& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = value;
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, value });
        this->keyCaches[std::move(key)] = this->caches.begin();
    }
}
template<typename K, typename V>
void LruCache<K, V>::set(const K& key, const V& value) noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt != this->keyCaches.end()) {
        auto& cacheIt = kCIt->second;
        std::get<1>(*cacheIt) = value;
        this->caches.rewire_to_front(cacheIt);
    } else {
        if (int32_t(this->keyCaches.size()) >= this->capacity) {
            auto const& back = this->caches.back();
            this->keyCaches.erase(std::get<0>(back));
            this->caches.pop_back();
        }
        this->caches.push_front(Cache{ key, value });
        this->keyCaches[key] = this->caches.begin();
    }
}
template<typename K, typename V>
inline bool LruCache<K, V>::has(const K& key) const noexcept
{
    return this->keyCaches.find(key) != keyCaches.end();
}
template<typename K, typename V>
bool LruCache<K, V>::get(const K& key, V& value) const noexcept
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt == this->keyCaches.end()) {
        return false;
    }
    const auto& cacheIt = kCIt->second;
    this->caches.rewire_to_front(cacheIt);
    value = std::get<1>(*cacheIt);
    return true;
}
template<typename K, typename V>
V& LruCache<K, V>::operator[](const K& key) noexcept
{
    auto kCIt = this->keyCaches.find(key);
    if (kCIt == this->keyCaches.end()) {
        this->set(key, V{});
        kCIt = this->keyCaches.find(key);
    }
    auto& cacheIt = kCIt->second;
    this->caches.rewire_to_front(cacheIt);
    return std::get<1>(*cacheIt);
}
template<typename K, typename V>
const V& LruCache<K, V>::operator[](const K& key) const
{
    const auto kCIt = this->keyCaches.find(key);
    if (kCIt == this->keyCaches.end()) {
        throw std::logic_error("no such key");
    }
    const auto& cacheIt = kCIt->second;
    this->caches.rewire_to_front(cacheIt);
    return std::get<1>(*cacheIt);
}
template<typename K, typename V>
inline const typename LruCache<K, V>::Caches&
LruCache<K, V>::getCaches() const noexcept
{
    return this->caches;
}
template<typename K, typename V>
inline void LruCache<K, V>::clear() noexcept
{
    this->caches.clear();
    this->keyCaches.clear();
}
template<typename K, typename V>
std::ostream& operator<<(
    std::ostream& os, const LruCache<K, V>& lruCache) noexcept
{
    const auto& caches = lruCache.getCaches();
    os << "capacity " << lruCache.getCapacity();
    const int32_t size = lruCache.getSize();
    os << ", size " << size;
    if (size > 0) {
        os << ": ";
    }
    for (const auto& cache : caches) {
        os << '(' << std::get<0>(cache) << ',' << std::get<1>(cache) << ") ";
    }
    return os;
}

Draw line primitives

2019-04-202019-04-20 yuiwongalgorithm

Draw line primitives

在栅格图中找到两点间的栅格(栅格图坐标), 这些点是两个点构成的线段经过的栅格, 使用算法:
Bresenham's_line_algorithm.

Implementation:

NOTE: Algorithm and implementation for integer arithmetic.

/**
 * Draw the segment with a Brush instance.
 * Implements in Bresenham's line algorithm: is a line drawing algorithm
 * that determines the points of an n-dimensional raster that should be
 * selected in order to form a close approximation to a straight line
 * between two points.
 * It is commonly used to draw line primitives in a bitmap image
 * (e.g. on a computer screen), as it uses only integer addition,
 * subtraction and bit shifting, all of which are very cheap operations
 * in standard computer architectures.
 * @tparam Brush the brush to draw, operator()(x, y) requried.
 * @param brush the brush instance.
 * @note
 * - Scalar should be integer!
 * - n should >= 2, this method for 2D, only use x and y.
 * - operator()(x, y) for Brush requried.
 * @return drawed count.
 * @sa
 * - https://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 * - https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#All_cases
 * - costmap_2d/include/costmap_2d/costmap_2d.h
 */
template<typename Brush>
uint32_t draw2D(const Brush& brush) const noexcept
{
    // Tparams check
    static_assert(2 == n || 3 == n, "n should be 2 or 3");
    static_assert(
        std::is_integral<typename std::decay<Scalar>::type>::value,
        "Scalar should be integer");
    // Draw
    uint32_t ndrawed = 0;
    // Cover gradients between 0 and -1 by checking whether y needs to
    // increase or decrease (i.e. dy < 0).
    const auto draw2DLow = [&brush, &ndrawed](const P& a, const P& b) {
        Scalar dx = b(0) - a(0);
        Scalar dy = b(1) - a(1);
        Scalar yi;
        if (dy < 0) {
            yi = -1;
            dy = -dy;
        } else {
            yi = 1;
        }
        const Scalar ddx = 2 * dx;
        const Scalar ddy = 2 * dy;
        Scalar D = ddy  - dx;
        Scalar y = a(1);
        for (const Scalar& x : Range<Scalar>{ a(0), b(0) }) {
            brush(x, y);
            ++ndrawed;
            if (D > 0) {
                y += yi;
                D -= ddx;
            }
            D += ddy;
        }
    };
    // By switching the x and y axis an implementation for positive or negative
    // steep gradients can be written as:
    const auto draw2DHigh = [&brush, &ndrawed](const P& a, const P& b) {
        Scalar dx = b(0) - a(0);
        Scalar dy = b(1) - a(1);
        Scalar xi;
        if (dx < 0) {
            xi = -1;
            dx = -dx;
        } else {
            xi = 1;
        }
        const Scalar ddx = 2 * dx;
        const Scalar ddy = 2 * dy;
        Scalar D = ddx  - dy;
        Scalar x = a(0);
        for (const Scalar& y : Range<Scalar>{ a(1), b(1) }) {
            brush(x, y);
            ++ndrawed;
            if (D > 0) {
                x += xi;
                D -= ddy;
            }
            D += ddx;
        }
    };
    // Need to detect whether x1 > x0 or y1 > y0 and reverse the input
    // coordinates before drawing
    if (std::abs(this->b(1) - this->a(1)) < std::abs(this->b(0) - this->a(0))) {
        if (this->a(0) > this->b(0)) {
            draw2DLow(this->b, this->a);
        } else {
            draw2DLow(this->a, this->b);
        }
    } else {
        if (this->a(1) > this->b(1)) {
            draw2DHigh(this->b, this->a);
        } else {
            draw2DHigh(this->a, this->b);
        }
    }
    return ndrawed;
}

Test and example:

TEST(Segment, draw2D)
{
    Segment<int32_t, 2> segment{ Eigen::Vector2i{ 3, 1 }, Eigen::Vector2i{ -6, -4 } };
    const std::vector<Eigen::Vector2i> expect{
        Eigen::Vector2i{ -6, -4 },
        Eigen::Vector2i{ -5, -3 },
        Eigen::Vector2i{ -4, -3 },
        Eigen::Vector2i{ -3, -2 },
        Eigen::Vector2i{ -2, -2 },
        Eigen::Vector2i{ -1, -1 },
        Eigen::Vector2i{ 0,  -1 },
        Eigen::Vector2i{ 1,  0 },
        Eigen::Vector2i{ 2,  0 },
        Eigen::Vector2i{ 3,  1 } };
    std::vector<Eigen::Vector2i> ps;
    const auto brush = [&ps](const int32_t x, const int32_t y) {
        std::cout << x << ' ' << y << '\n';
        ps.emplace_back(Eigen::Vector2i{ x, y });
    };
    ps.clear();
    EXPECT_EQ(expect.size(), segment.draw2D(brush));
    EXPECT_EQ(expect.size(), ps.size());
    if (expect.size() == ps.size()) {
        for (uint32_t i = 0; i < ps.size(); ++i) {
            EXPECT_EQ(expect[i], ps[i]);
        }
    }
    //
    Segment<int32_t, 3> s3;
    ps.clear();
    s3.draw2D(brush);
    EXPECT_EQ(1u, ps.size());
    if (1u == ps.size()) {
        EXPECT_EQ((Eigen::Vector2i{ 0, 0 }), ps[0]);
    }
    // BAD test:
    //Segment<double, 3> badS3;
    //badS3.draw2D(brush);
}

$draw2D-example.png$

Project Point Cloud to depth

2019-04-052019-04-05 yuiwongPointCloud

Project Point Cloud to depth

要投影点云到深度图首先输入的点云是 “organized” or “organizable(先处理 cloud 的 width 和 height!)”, 然后需要确定 以那个轴作为深度值或者投影到那个平面.

例如 cloud z to depth:

template<typename Point = pcl::PointXYZ, typename DT = float>
bool cloudZToDepth(
    const pcl::PointCloud<Point>& cloud,
    const bool invalidToNew,
    const DT newValue,
    cv::Mat& depth) noexcept
{
    if (!cloud.isOrganized()) {
        return false;
    }
    int32_t type;
    if (std::is_same<float, typename std::decay<DT>::type>::value) {
        type = CV_32F;
    } else if (std::is_same<double, typename std::decay<DT>::type>::value) {
        type = CV_64F;
    } else if (std::is_same<int32_t, typename std::decay<DT>::type>::value) {
        type = CV_32S;
    } else {
        return false;
    }
    const int32_t width = cloud.width;
    const int32_t height = cloud.height;
    if (std::is_floating_point<typename std::decay<DT>::type>::value) {
        depth.create(height, width, CV_MAKETYPE(type, 1));
    } else {
        depth.create(height, width, CV_MAKETYPE(type, 1));
    }
    if (invalidToNew) {
        for (int32_t y = 0; y < height; ++y) {
            for (int32_t x = 0; x < width; ++x) {
                // NOTE: cv: (row, column), BUT PCL (column, row)
                const auto dv = cloud(x, y).z;
                if (std::isfinite(dv)) {
                    depth.at<DT>(y, x) = DT(dv);
                } else {
                    depth.at<DT>(y, x) = newValue;
                }
            }
        }
    } else {
        for (int32_t y = 0; y < height; ++y) {
            for (int32_t x = 0; x < width; ++x) {
                // NOTE: cv: (row, column), BUT PCL (column, row)
                depth.at<DT>(y, x) = cloud(x, y).z;
            }
        }
    }
    return true;
}

再比如 cloud x, y, z to depth (3 channels):

template<typename Point = pcl::PointXYZ, typename CDT = float>
bool CvHelper::cloudXYZToDepth(
    const pcl::PointCloud<Point>& cloud,
    const bool invalidToNew,
    const CDT newValue,
    cv::Mat& depth,
    const CDT xFactor,
    const CDT yFactor,
    const CDT zFactor) noexcept
{
    if (!cloud.isOrganized()) {
        return false;
    }
    int32_t type;
    if (std::is_same<float, typename std::decay<CDT>::type>::value) {
        type = CV_32F;
    } else if (std::is_same<double, typename std::decay<CDT>::type>::value) {
        type = CV_64F;
    } else if (std::is_same<int32_t, typename std::decay<CDT>::type>::value) {
        type = CV_32S;
    } else {
        return false;
    }
    const int32_t width = cloud.width;
    const int32_t height = cloud.height;
    if (std::is_floating_point<typename std::decay<CDT>::type>::value) {
        depth.create(height, width, CV_MAKETYPE(type, 3));
    } else {
        depth.create(height, width, CV_MAKETYPE(type, 3));
    }
    if (invalidToNew) {
        for (int32_t y = 0; y < height; ++y) {
            for (int32_t x = 0; x < width; ++x) {
                // NOTE: cv: (row, column), BUT PCL (column, row)
                auto dv = cloud(x, y).x;
                if (std::isfinite(dv)) {
                    depth.at<cv::Vec<CDT, 3> >(y, x)[0] = CDT(dv * xFactor);
                } else {
                    depth.at<cv::Vec<CDT, 3> >(y, x)[0] = newValue;
                }
                // NOTE: cv: (row, column), BUT PCL (column, row)
                dv = cloud(x, y).y;
                if (std::isfinite(dv)) {
                    depth.at<cv::Vec<CDT, 3> >(y, x)[1] = CDT(dv * yFactor);
                } else {
                    depth.at<cv::Vec<CDT, 3> >(y, x)[1] = newValue;
                }
                // NOTE: cv: (row, column), BUT PCL (column, row)
                dv = cloud(x, y).z;
                if (std::isfinite(dv)) {
                    depth.at<cv::Vec<CDT, 3> >(y, x)[2] = CDT(dv * zFactor);
                } else {
                    depth.at<cv::Vec<CDT, 3> >(y, x)[2] = newValue;
                }
            }
        }
    } else {
        for (int32_t y = 0; y < height; ++y) {
            for (int32_t x = 0; x < width; ++x) {
                // NOTE: cv: (row, column), BUT PCL (column, row)
                depth.at<cv::Vec<CDT, 3> >(y, x)[0] = cloud(x, y).x * xFactor;
                depth.at<cv::Vec<CDT, 3> >(y, x)[1] = cloud(x, y).y * yFactor;
                depth.at<cv::Vec<CDT, 3> >(y, x)[2] = cloud(x, y).z * zFactor;
            }
        }
    }
    return true;
}

See also https://yuiwong.org/gitlab/pointcloud

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30