初级会员
  • 第 14870 位会员
  • snake117
  • 2017-12-15 02:15:59
  • 214
  • Offline
  • 19 84

最近发布的主题

    暂无

最近发布的文章

最近分享的资源

    暂无

最近发布的项目

    暂无

最近的评论

  • 评论了主题 go的string深复制
    string是不可变类型,为啥非要深复制?
  • #24 @jthmath 带优先级的队列,其底层的数据结构实现中其实就包括我说的跳表/链表二叉树。当然采用树堆也是可行的。
  • 二叉树版本的排版错了,正确排版 package main import ( "fmt" "github.com/hydar13142/container/sbt" "os" ) type Void = struct{} func main() { t := sbt.NewSBT() for i := 2; i < 6; i++ { t.Insert(int64(i), Void{}) } p := t.Index(0) xs := [10000]int64{} for i := 0; i < 10000; i++ { k := p.Key() xs[i] = k t.Insert(k*2, Void{}) t.Insert(k*3, Void{}) t.Insert(k*5, Void{}) t.DeleteNode(p) p = p.Next() } file, _ := os.Create("output.txt") defer file.Close() fmt.Fprintln(file, xs) }
  • 我们不要用对数字进行检验的方法,不管检验的速度快慢,都需要检验太多数字了。 根据我计算的结果,第10000个数字是:288555831593533440。 你们说如果检验数字,要检验多久吧。即使采用各种方法排除了一大批数字,并且单个数字的检验很快,这个数量级也太大了。 所以采用生成数字的方法。 我们只要保证有一个数据仓库,这个仓库可以很方便的按从小到大的顺序取出值,同时插入新的值时,能够保持有序(最好插入时维护有序的操作时间尽可能短)即可。
  • 这个最好使用一个动态遍历的、有序的、插入耗时短的结构,来保存候选数字。 然后我们就可以一边生成候选数字,存入这个结构,一边从这个结构里按从小到大的顺序取出数字就行了。 个人觉得最合适的数据结构,就是跳表。插入时间Nlog(N),遍历时更是log(1)的复杂度。 双向链表和平衡二叉查找树的复合数据结构也很合适。 不知道python里有没有。 我自己的库里倒是有两个。只要采用了合适的数据结构,代码反而很简单。 跳表版本(这个跳表采用int64+string作为键,值为interface{}) package main import ( "fmt" "github.com/hydra13142/container/skiplist" "os" ) type Void = struct{} func main() { t := skiplist.New() for i := 2; i < 6; i++ { t.Insert(int64(i), "", Void{}) } p := t.SearchByIndex(0) xs := [10000]int64{} for i := 0; i < 10000; i++ { k, _ := p.Key() xs[i] = k t.Insert(k*2, "", Void{}) t.Insert(k*3, "", Void{}) t.Insert(k*5, "", Void{}) p.Next() } file, _ := os.Create("output2.txt") defer file.Close() fmt.Fprintln(file, xs) } 二叉树版本(SBT树采用int64作为键,值为interface{}) package main import ( "fmt" "github.com/hydar13142/container/sbt" "os" ) type Void = struct{} func main() { t := sbt.NewSBT() for i := 2; i < 6; i++ { t.Insert(int64(i), Void{}) } p := t.Index(0) xs := [10000]int64{} for i := 0; i < 10000; i++ { k := p.Key() xs[i] = k t.Insert(k*2, Void{}) t.Insert(k*3, Void{}) t.Insert(k*5, Void{}) // t.DeleteNode(p) 删不删节点都不影响结果 p = p.Next() } file, _ := os.Create("output.txt") defer file.Close() fmt.Fprintln(file, xs) }