README
¶
topk
TopK is a Go implementation of the Top K elements.
https://godoc.org/github.com/n1chre/topk
API
New(k int, l Less) Interface- create a new Interface which supportsPushandGet. Less determines the orderingPush(t Interface, x interface{})- push the new value onto the structureGet(t Interface, x interface{})- get the top K values
Example usage
package main
import "github.com/n1chre/topk"
func main() {
tk := topk.New(3, topk.IntComparator)
for _, x := range []int{1, 5, 2, -1, 8, 9, -10} {
topk.Push(tk, x)
}
// top3 = []interface{}{9, 8, 5}
fmt.Println(topk.Get(tk))
}
Documentation
¶
Overview ¶
Example ¶
Example shows an example usage of the topk structure
tk := New(3, IntComparator)
for _, x := range []int{1, 5, 2, -1, 8, 9, -10} {
Push(tk, x)
}
// top3 = []interface{}{9, 8, 5}
fmt.Println(Get(tk))
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Float64Comparator ¶
func Float64Comparator(a, b interface{}) bool
Float64Comparator compares float64s
func Get ¶
func Get(t Interface) []interface{}
Get returns the top K values from the given interface. The complexity is O(k * log k)
func Push ¶
func Push(t Interface, x interface{})
Push pushes the element x onto the topK. The complexity is O(log k)
func StringComparator ¶
func StringComparator(a, b interface{}) bool
StringComparator compares strings
Types ¶
type Interface ¶
type Interface interface {
// Interface is a heap with a size, so it needs to implement the heap.Interface
heap.Interface
// IsLess is used to determine whether a new value will get pushed to the structure or not
// IsLess(interface{}, interface{}) should be consistent with Less(int, int) from heap.Interface
IsLess(a, b interface{}) bool
// Peek should return the minimum element. Same as Pop(), but without removing it
Peek() interface{}
// Get must return top K values, in any order
// it mustn't modify (push/pop) the Interface, and the complexity should be O(1)
// returned slice won't be modified, so one can/should return a "live view" of the data
// if we pushed L values, then len(result) is for
// - L < K: L
// - L >= K: K
Get() []interface{}
// K returns the size
K() int
}
Interface type describes the requirements for a type using the routines in this package Note that Push in this interface (heap.Interface) is for package topk's implementation to call. To add things from the heap, use topk.Push Useful for large streams of data when you only care about the top K elements, where K is small. Then it only keeps the top K elements in memory and performs Push in O(log k) time.
Source Files