<
查看: 328|回复: 1
收起左侧

[其他] 提供一个windowed kv store方案,大家讨论下有没有更好的

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
题目要求是一个key value store,超过30分钟的key需要删除。
要求:
void put(string key, int val)
int get(string key)
void delete(string key)
int avg(): 返回所有没有过期的平均值
avg会被call很多次,所以 O(n) 是不可以接受的。

思路:
1. 类似lru解法,一个hashmap + 一个linkedlist。
这样,get, put, delete都是O(1)
2. 记录下所有的node个数,以及所有value的和 sum
3. 每次求avg,都先从head出发,删除过期的节点,同时更新sum和node个数。
因为avg call的很频繁,以及每个过期节点最多被删除一次,所以amortized complexity是O(1).


[Python] 纯文本查看 复制代码
from datetime import datetime, timedelta


class Node:
    def __init__(self, val):
        self.val = val
        self.time = datetime.now()
        self.prev = None
        self.next = None


class WindowKVStore:

    # window size by minutes
    WINDOW = timedelta(minutes=50)

    def __init__(self):
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.mapping = {}
        self.sum = 0
        self.nodes = 0

    def put(self, key, val):
        # remove old node if exists
        if key in self.mapping:
            self.delete(key)

        # put in map
        node = Node(val)
        self.mapping[key] = node

        # insert in front of tail
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

        # update sum and nodes
        self.sum += val
        self.nodes += 1

    def get(self, key):
        if key not in self.mapping:
            return None

        node = self.mapping[key]
        if node.time < datetime.now() - self.WINDOW:
            return None

        return node.val

    def delete(self, key):
        if key not in self.mapping:
            return

        # delete node from link list
        node = self.mapping[key]
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None

        # delete node from map
        del self.mapping[key]

        # update sum and nodes
        self.sum -= node.val
        self.nodes -= 1

    def avg(self):
        self.__remove_expired()
        return self.sum / self.nodes if self.nodes else 0

    def __remove_expired(self):
        now = datetime.now()
        while self.head.next != self.tail and self.head.next.time < now - self.WINDOW:
            self.head = self.head.next
            self.head.prev = None
            self.sum -= self.head.val
            self.nodes -= 1


评分

参与人数 2大米 +7 收起 理由
inter1908 + 1 赞一个
14417335 + 6

查看全部评分


上一篇:如何提高java的内功:stream的编写能力
下一篇:Leetcode 国内大厂高频Top100 (Plus会员专享)
 楼主| OrionNebula 2021-5-8 10:36:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎
代码里面有问题,也欢迎指出来。共同进步
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表