armon / go-radix Goto Github PK
View Code? Open in Web Editor NEWGolang implementation of Radix trees
License: MIT License
Golang implementation of Radix trees
License: MIT License
I see that the implementation is recursive, but this isn't exposed in the public API. For example it would be powerful to get a reference to a sub-tree and then to be able to query it the same as the root tree.
I don't have the time to deep dive into the implementation, so I was hoping you could answer this for me: Is there any technical reason why non-root Nodes can't be exposed and queried like the root Node? Is there some quirk in the implementation that prevents this, that requires all queries to be made from the root?
There are some commits after the latest release, most notably this one f30034d -- could you just create a new release tag?
I have a high traffic server where I'm maintaining prefix trees of a number of data sets with tens of thousands to millions of elements. When keys expire, I'm removing them from the tree. However, memory usage is still increasing. I believe this is because t.Delete() doesn't clean up n.edges[] when an element is deleted and also because the string slicing for n.prefix holds onto the underlying strings, not allowing them to be freed once the keys are no longer referenced.
Since go-radix stores characters as bytes instead of runes, I'd guess not. Or am I missing something?
I want to ask a low-level question, is this an adaptive radix tree?
Sorry for the drive by. This is a useful package and I've made extensive changes to my version. There is an easy performance improvement. If you like it, you can take it, no attribution necessary. If not, feel free to close with no further comment.
The numbers I quoted in the header are for benchmarks when 10,000 entries are added to a tree. The order of insertions doesn't matter. They can be ordered, unordered, and even reverse ordered. Always 28% fewer allocations occur.
The package requires the edges are kept sorted. Currently the addEdge method performs a full sort after appending the new edge. Using the same binary search other parts of the package use, the insertion point can be found exactly. The binary search is much more efficient than the sort.
Replace
func (n *node) addEdge(e edge) {
n.edges = append(n.edges, e)
n.edges.Sort()
}
with
func (n *node) addEdge(e edge) {
num := len(n.edges)
idx := sort.Search(num, func(i int) bool {
return n.edges[i].label >= e.label
})
n.edges = append(n.edges, edge{})
copy(n.edges[idx+1:], n.edges[idx:])
n.edges[idx] = e
}
Hi,
Before anything, great package ๐
I'm creating an personal web framework and I need to route my routes ๐. I'm studying and find a possible solution, use radix tree, and found this package.
But I've a problem, how to route the path if I catch a path with parameters ?
Ex.:
package main
import (
"fmt"
radix "github.com/armon/go-radix"
)
func main() {
r := radix.New()
r.Insert("/a/b/c/:d", 1)
r.Insert("/a/b/n/:d", 2)
r.Insert("/a/t/u/:i", 2)
m, _, _ := r.LongestPrefix("/a/b/c/test")
fmt.Println(m) // Don't match path
}
In this scene this code not match my path, but should. Can you help me, it is possible to do?
Tks
Can this be used from multiple concurrent goroutines?
It a question and sorry for asking this here. Is it safe to use it concurrently for getting and inserting nodes? Or maybe I have to implement locks?
sort.Search is Binary search
time complexity is O(log(n))
is there any more fast code?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.