Golang 中国

snake117

Golang China 第 70 号会员,加入于 2012-09-28 23:20


snake117最近回复了


回复了 snake117 创建的主题: n++ 和 n= n+1、n+=1 不一样? 2018-03-15 09:23

@heimeil

是真的,我用的win10-64bit系统,go1.10。

两个文件如下
skiplist.go

package skiplist

import (
    "errors"
    "math/rand"
    "time"
)

var (
    rd = rand.New(rand.NewSource(time.Now().Unix()))
    er = errors.New("skiplist: out of range")
)

type key struct {
    N int64
    S string
}

// 代表一个元素
type Node struct {
    cnt int
    key
    val *interface{}
    lft *Node
    rgt *Node
    dwn *Node
}

// 跳表类型
type SkipList struct {
    root *Node
    line []*Node
    path []int
    long int
}

func (x *key) cmp(y *key) int8 {
    switch {
    case x.N < y.N:
        return -1
    case x.N > y.N:
        return +1
    }
    switch {
    case x.S < y.S:
        return -1
    case x.S > y.S:
        return +1
    }
    return 0
}

// 创建一个跳表
func New() *SkipList {
    return &SkipList{new(Node), make([]*Node, 1), make([]int, 1), 0}
}

// 返回跳表长度
func (this *SkipList) Len() int {
    return this.long
}

// 清空重置跳表
func (this *SkipList) Reset() {
    var p, q, a, b *Node
    for p = this.root; p != nil; p = q {
        q = p.dwn
        for a = p; a != nil; a = b {
            b = a.rgt
            a.lft, a.rgt, a.dwn, a.val = nil, nil, nil, nil
        }
    }
    this.root = new(Node)
    this.line = make([]*Node, 1)
    this.path = make([]int, 1)
    this.long = 0
}

func (this *SkipList) search(x *key) (i int, c int) {
    for i, p := 0, this.root; p != nil; {
        t, q := int8(1), p.rgt
        if q != nil {
            t = q.key.cmp(x)
        }
        switch t {
        case -1:
            p, c = q, c+q.cnt
        case +1:
            this.line[i] = p
            this.path[i] = c
            i, p = i+1, p.dwn
        default:
            c += q.cnt
            this.line[i] = q
            this.path[i] = c
            return i, c
        }
    }
    return -1, c
}

func (this *SkipList) member(n int) (i int, c int) {
    n++
    c = n
    for i, p := 0, this.root; p != nil; {
        if n == 0 {
            this.line[i] = p
            this.path[i] = c
            return i, c
        }
        if q := p.rgt; q != nil && q.cnt <= n {
            p, n = q, n-q.cnt
            continue
        }
        this.line[i] = p
        this.path[i] = c - n
        i, p = i+1, p.dwn
    }
    return -1, c
}

func (this *SkipList) insert(i int, c int, k *key, v interface{}) {
    var p, q *Node
    t := int(rd.ExpFloat64()) + 1
    l := len(this.line)
    if t > l {
        u := make([]*Node, t)
        v := make([]int, t)
        copy(u[t-l:], this.line)
        copy(v[t-l:], this.path)
        for i := t - l - 1; i >= 0; i-- {
            p = new(Node)
            p.dwn = this.root
            this.root = p
            u[i] = p
        }
        this.line = u
        this.path = v
        l = t
    }
    i, c = 0, c+1
    for i = 0; i < l-t; i++ {
        if p = this.line[i].rgt; p != nil {
            p.cnt++
        }
    }
    q = &Node{}
    x := *k
    y := new(interface{})
    for ; i < l; i++ {
        p = this.line[i]
        q.dwn = new(Node)
        q = q.dwn
        q.cnt = c - this.path[i]
        q.key, q.val = x, y
        q.lft, q.rgt = p, p.rgt
        p.rgt = q
        if q.rgt != nil {
            q.rgt.lft = q
            q.rgt.cnt -= q.cnt - 1
        }
    }
    *y = v
    this.long++
}

func (this *SkipList) remove(t int) {
    i, l := 0, len(this.line)
    for ; i < t; i++ {
        p := this.line[i]
        if p.rgt != nil {
            p.rgt.cnt--
        }
    }
    for p := this.line[i]; i < l; i++ {
        q := p.dwn
        if p.lft != nil {
            p.lft.rgt = p.rgt
        }
        if p.rgt != nil {
            p.rgt.cnt += p.cnt - 1
            p.rgt.lft = p.lft
        }
        p.lft, p.rgt, p.dwn = nil, nil, nil
        p = q
    }
    this.long--
}

// 插入跳表新的值,如已存在相同键的值,不作修改并返回假
func (this *SkipList) Insert(n int64, s string, v interface{}) bool {
    k := &key{n, s}
    i, c := this.search(k)
    if i >= 0 {
        return false
    } else {
        this.insert(i, c, k, v)
    }
    return true
}

// 如该键不存在值则插入新值,如已存在则更新旧值
func (this *SkipList) InsertUpdate(n int64, s string, v interface{}) {
    k := &key{n, s}
    i, c := this.search(k)
    if i < 0 {
        this.insert(i, c, k, v)
    } else {
        *this.line[i].val = v
    }
}

// 删除跳表已有的值,如该键不存在值,返回假
func (this *SkipList) Delete(n int64, s string) bool {
    t, _ := this.search(&key{n, s})
    if t < 0 {
        return false
    } else {
        this.remove(t)
    }
    return true
}

// 删除跳表第n个值
func (this *SkipList) DeleteByIndex(n int) bool {
    if n < 0 || n >= this.long {
        return false
    }
    t, _ := this.member(n)
    if t < 0 {
        return false
    } else {
        this.remove(t)
    }
    return true
}

// 从跳表中搜索int64和string的参数为键
func (this *SkipList) Search(n int64, s string) *Node {
    c, k := 0, &key{n, s}
    for i, p := 0, this.root; p != nil; {
        t, q := int8(1), p.rgt
        if q != nil {
            t = q.key.cmp(k)
        }
        switch t {
        case -1:
            p, c = q, c+q.cnt
        case +1:
            i, p = i+1, p.dwn
        default:
            return q.rgt
        }
    }
    return nil
}

// 返回跳表中第n个值(下标从0开始)
func (this *SkipList) SearchByIndex(n int) *Node {
    if n < 0 || n >= this.long {
        return nil
    }
    n = n + 1 // 就是这一行
    for i, p := 0, this.root; p != nil; {
        if n == 0 {
            return p
        }
        if q := p.rgt; q != nil && q.cnt <= n {
            p, n = q, n-q.cnt
        } else {
            i, p = i+1, p.dwn
        }
    }
    return nil
}

// 获得前驱节点,用于简单迭代
func (this *Node) Prev() *Node {
    return this.lft
}

// 获得后继节点,用于简单迭代
func (this *Node) Next() *Node {
    return this.rgt
}

// 返回当前元素的键
func (this *Node) Key() (int64, string) {
    return this.N, this.S
}

// 返回当前元素的值
func (this *Node) Val() interface{} {
    return *this.val
}

// 设置当前元素的值
func (this *Node) Set(v interface{}) {
    *this.val = v
}

另一个文件是skiplist-try.go

package main

import (
    "fmt"
    "skiplist" // 这个根据你把shiplit放置的位置来改动
    "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 = p.Next()
    }
    file, _ := os.Create("output2.txt")
    defer file.Close()
    fmt.Fprintln(file, xs)
}

你可以测试一下。

回复了 gosenvei 创建的主题: golang如何才能计算出 sin(1e300) 2017-09-29 17:06

@jimmkuu 我测试了C和C++,确实都是-0.8178819121159085,看来go确实是有问题了。

回复了 gosenvei 创建的主题: golang如何才能计算出 sin(1e300) 2017-09-28 14:50

@jimmykuu

我觉得这算不上bug吧,数值太大了,精度问题肯定会体现出来的。

很可能这就是编译型语言的固有特性。

谁有C、C++的计算结果吗?

还有C#、java的?

回复了 gosenvei 创建的主题: golang如何才能计算出 sin(1e300) 2017-09-21 03:14

1,5000位的pi值,计算结果也是-0.985750425160377

回复了 gosenvei 创建的主题: golang如何才能计算出 sin(1e300) 2017-09-21 03:07

好吧,貌似都不够准确,big版本如下:

package main

import (
    "fmt"
    "math"
    "math/big"
)

func main() {
    F, _, _ := big.ParseFloat("1e300", 10, 5000, big.ToNearestEven)
    P, _, _ := big.ParseFloat(pi, 10, 5000, big.ToNearestEven)
    P.Mul(P, big.NewFloat(2))
    F.Quo(F, P)
    M, _ := F.Int(nil)
    N := big.NewFloat(0).SetPrec(5000).SetInt(M)
    F.Sub(F, N)
    F.Mul(F, P)
    f, _ := F.Float64()
    fmt.Println(math.Sin(f))
    /*fmt.Println(N.Add(N.Mul(N, P), F))*/
}

const pi = "3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151557485724245415069595082953311686172785588907509838175463746493931925506040092770167113900984882401285836160356370766010471018194295559619894676783744944825537977472684710404753464620804668425906949129331367702898915210475216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992458631503028618297455570674983850549458858692699569092721079750930295532116534498720275596023648066549911988183479775356636980742654252786255181841757467289097777279380008164706001614524919217321721477235014144197356854816136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179049460165346680498862723279178608578438382796797668145410095388378636095068006422512520511739298489608412848862694560424196528502221066118630674427862203919494504712371378696095636437191728746776465757396241389086583264599581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745530506820349625245174939965143142980919065925093722169646151570985838741059788595977297549893016175392846813826868386894277415599185592524<BR>59539594310499725246808459872736446958486538367362226260991246080512438843904512441365497627807977156914359977001296160894416948685558484063534220722258284886481584560285060168427394522674676788952521385225499546667278239864565961163548862305774564980355936345681743241125"

结果输出是-0.985750425160377

回复了 gosenvei 创建的主题: golang如何才能计算出 sin(1e300) 2017-09-21 02:33

@gosenvei @jimmykuu @wpf000

用golang计算,用如下算式:
fmt.Println(math.Sin(math.Mod(1e300, math.Pi*2))) fmt.Println(math.Sin(math.Remainder(1e300, math.Pi*2)))
结果基本一致:
-0.6619570086831917
-0.6619570086831915

反正不是-0.81788191211591,不知道哪个更准确

回复了 newgolanger 创建的主题: 请问: int, float,struct, 指针本身,数组是不是多线程安全的? 2017-09-14 20:59

@jthmath rust是搞成和python一样,将数值设成不可变类型了,不可变了都,当然线程安全了。

回复了 snake117 创建的主题: 最新版的LiteIDE-Windows-qt5不太稳定啊 2017-08-31 21:20

我的神舟win10 x64,i7-4720hq,同样qt5版本的经常崩溃,换回qt4版本的了。

回复了 lightbee 创建的主题: go html/template包 新建一个模板然后使用ParseFiles方法之后使用Execute方法发现居然不会输出!!! 2017-06-30 22:48

直接用包级别的ParseFiles来解析文件,不要创建一个模板然后用方法解析

回复了 Bluek404 创建的主题: nwui —— 又一个go语言图形界面解决方案 2017-01-19 10:55

简直无奈,其实这个跨平台很不错的。编写起来也比较简单。

话说为啥总有人想让go的gui也尽善尽美,术业有专攻,go在擅长之外的功能只需要实用就够了啊。

snake117 创建的更多回复