This repository has been archived by the owner on Jul 2, 2023. It is now read-only.

0xleizhang / top-k-in-time-sliding-window Public archive

Notifications You must be signed in to change notification settings
Fork 0
Star 5

查找滑动时间窗口频繁项(24小时实时热榜)

5 stars 0 forks Branches Tags Activity

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 2 Commits
data		data
pkg		pkg
.gitignore		.gitignore
README.md		README.md
go.mod		go.mod
go.sum		go.sum
handler.go		handler.go
handler_test.go		handler_test.go
sketch_window.go		sketch_window.go
sketch_window_test.go		sketch_window_test.go
window.go		window.go
window_test.go		window_test.go

Repository files navigation

find top-k in time sliding window

查找滑动时间窗口频繁项

算法：

sketchWindow 记录n秒内的top k个频繁线
sketchWindow满时生成摘要添加到下一个window窗口
window窗口如果不是最后一个窗口，判断当前窗口是否已满，如果满生成摘要添加到下一个窗口并清空当前窗口，如果不满进行滑动计算
滑动计算，将滑出的摘要做减法，滑入的做加法
window窗口是最后一个窗口时进行滑动计算不生成摘要

具体实现需要考虑时间跨越检测周期的情况

数据结构

minheap 最小堆
circular_queue 循环队列
countMinSketch

测出用例设计

About

查找滑动时间窗口频繁项(24小时实时热榜)

Report repository

Releases

No releases published

Packages

No packages published

Languages

Go 100.0%