享元模式股票代码池

Flyweight Symbol Pool

专题: General / 综合
难度: L3
来源: MyntBit

个人笔记

题目详情

高频交易系统每天处理数百万订单，内存优化和缓存效率至关重要。享元设计模式通过对股票代码等重复数据去重，将其放入共享池并使用轻量级整数 ID 来引用，从而大幅减少内存占用。

任务：实现一个使用垃圾回收享元模式的 OrderManager 类，高效管理订单。

英文原题

High-frequency trading systems process millions of orders daily, making memory optimization and cache efficiency critical. The Flyweight design pattern addresses this by deduplicating repetitive data, such as ticker symbols, into a shared pool and utilizing lightweight integer IDs. Implementing a garbage-collected Flyweight pattern ensures that memory is dynamically managed and stale symbols are safely recycled.
Task
Implement an OrderManager class that uses a garbage-collected Flyweight pattern to manage orders efficiently.

解析

问题分析

高频交易系统每天处理数百万订单，每个订单都包含股票代码等重复数据。享元模式（Flyweight Pattern）通过将重复数据去重并放入共享池来节省内存。关键设计点包括：使用哈希表实现 O(1) 的符号查找、使用引用计数管理生命周期、以及确保线程安全。

解决方案

class SymbolPool {
    std::unordered_map<std::string, std::shared_ptr<const Symbol>> pool_;
    mutable std::shared_mutex mutex_;
public:
    std::shared_ptr<const Symbol> getOrCreate(const std::string& ticker) {
        std::shared_lock read_lock(mutex_);
        auto it = pool_.find(ticker);
        if (it != pool_.end()) return it->second;
        read_lock.unlock();
        
        std::unique_lock write_lock(mutex_);
        auto [it2, inserted] = pool_.emplace(ticker, 
            std::make_shared<Symbol>(ticker));
        return it2->second;
    }
    
    void garbageCollect() {
        std::unique_lock write_lock(mutex_);
        for (auto it = pool_.begin(); it != pool_.end(); ) {
            if (it->second.use_count() == 1)  // only pool holds it
                it = pool_.erase(it);
            else ++it;
        }
    }
};

关键考虑

线程安全：使用 `std::shared_mutex` 实现读写锁，读多写少场景下避免不必要的竞争。
内存管理：`std::shared_ptr` 自动管理引用计数。垃圾回收时检查 `use_count() == 1`（仅池持有）来清理不再使用的符号。
性能：查找 O(1)，插入均摊 O(1)。读写锁允许并发查找，仅在插入/回收时独占。
缓存友好性：连续存储的哈希表比链表有更好的缓存局部性。考虑使用 `std::pmr` 配合池化分配器。
边界条件：处理空 ticker、超长 ticker、并发插入同一符号等。

英文解析

Analysis

High-frequency trading systems process millions of orders daily, each containing repetitive data like stock tickers. The Flyweight Pattern deduplicates repetitive data into a shared pool to reduce memory usage. Important design factors include: using a hash table for O(1) symbol lookup, reference counting for lifecycle management, and ensuring thread safety.

Solution

class SymbolPool {
    std::unordered_map<std::string, std::shared_ptr<const Symbol>> pool_;
    mutable std::shared_mutex mutex_;
public:
    std::shared_ptr<const Symbol> getOrCreate(const std::string& ticker) {
        std::shared_lock read_lock(mutex_);
        auto it = pool_.find(ticker);
        if (it != pool_.end()) return it->second;
        read_lock.unlock();
        
        std::unique_lock write_lock(mutex_);
        auto [it2, inserted] = pool_.emplace(ticker, 
            std::make_shared<Symbol>(ticker));
        return it2->second;
    }
    
    void garbageCollect() {
        std::unique_lock write_lock(mutex_);
        for (auto it = pool_.begin(); it != pool_.end(); ) {
            if (it->second.use_count() == 1)  // only pool holds it
                it = pool_.erase(it);
            else ++it;
        }
    }
};

Complexity & Edge Cases

Time complexity: O(1) for lookup via hash map; O(1) for intern with existing symbol
Space complexity: O(N) for N unique symbols stored
Edge cases: (1) Empty or null ticker strings must be handled gracefully. (2) Concurrent insertion of the same symbol from multiple threads requires synchronization. (3) Excessively long ticker strings waste pool memory.

Key Considerations

Thread safety: `std::shared_mutex` implements a read-write lock, avoiding unnecessary contention in read-heavy scenarios.
Memory management: `std::shared_ptr` manages reference counts automatically. Garbage collection checks `use_count() == 1` (only pool holds it) to clean up unused symbols.
Performance: Lookup O(1), insertion amortized O(1). Read-write lock allows concurrent lookups, exclusive access only for insertion/collection.
Cache friendliness: Contiguous hash table storage has better cache locality than linked lists. Consider `std::pmr` with pooled allocators.
Edge cases: Handle empty tickers, excessively long tickers, concurrent insertion of the same symbol.