双链表应用——千万数据量秒级查询

原理

利用双链表,
将数据全部读入内存,将读到的数据头插插入双链表,
因为链表头插效率高
然后在内存中检索数据,检索到就输出

代码片段

// 读取文件
file,_ := os.Open(path) // 打开文件
br := bufio.NewReader(file) // 读出文件对象
for{
    line,_,end := br.ReadLine()
    if end == io.EOF{
        break  //文件结束跳出循环
    }
    linestr := string(line) 
}

代码

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strings"
    "time"
)

type DoubleLinkNode struct{
    Value interface{}
    Next *DoubleLinkNode
    Pre *DoubleLinkNode
}

type MyDoubleLinkList struct{
    Lens int
    Head *DoubleLinkNode
}

func NewDoubleLinkNode(value interface{})*DoubleLinkNode{
    return &DoubleLinkNode{
        Value: value,
        Next:  nil,
        Pre:   nil,
    }
}

//func (DoubleLinkNode)

func Constructor()*MyDoubleLinkList{
    return &MyDoubleLinkList{
        Lens: 0,
        Head: nil,
    }
}

// GetLength 获取长度
func (this *MyDoubleLinkList)GetLength()int{
    return this.Lens
}

// InsertHead 头插
func (this *MyDoubleLinkList)InsertHead(node *DoubleLinkNode){
    bak := this.Head
    this.Head = node
    this.Head.Pre = nil

    this.Head.Next = bak
    if this.Head.Next!=nil{
        this.Head.Next.Pre = this.Head
    }
    this.Lens++
}

func (this *MyDoubleLinkList)toString(){
    node := this.Head
    str := ""
    fmt.Println("lens:", this.Lens)
    for node != nil{
        str += fmt.Sprintf("%v-->", node.Value)
        node = node.Next
    }
    str += fmt.Sprintf("nil")
    fmt.Println(str)
}

func (this *MyDoubleLinkList)FindStr(value string)interface{}{
    node := this.Head

    for node!= nil{
        if strings.Contains(node.Value.(string), value){
            fmt.Println("找到:", node.Value.(string))
        }
        node = node.Next
    }
    return false
}

func main() {
    l := Constructor()
    startTime := time.Now()
    pathList := []string{
        "D:\\itcast\\社工\\压缩\\猴岛游戏社区\\houdao\\1_1.txt",
        "D:\\itcast\\社工\\压缩\\猴岛游戏社区\\houdao\\1_2.txt",
        "D:\\itcast\\社工\\压缩\\猴岛游戏社区\\houdao\\1_3.txt",
    }
    for i:=0; i<len(pathList);i++{
        path := pathList[i]
        file,_ := os.Open(path) // 打开文件
        br := bufio.NewReader(file) // 读出文件对象
        for{
            line,_,end := br.ReadLine()
            if end == io.EOF{
                break  //文件结束跳出循环
            }
            linestr := string(line) //转化为字符串
            node := NewDoubleLinkNode(linestr) //新建节点
            l.InsertHead(node)
        }
    }
    fmt.Printf("内存载入完成, 数据量:%d, 用时:%v", l.GetLength(), time.Since(startTime))

    for;;{
        fmt.Println("\n请输入要查询的信息:")
        var str string
        fmt.Scanln(&str)
        startTime2 := time.Now()
        l.FindStr(str)
        fmt.Printf("查询完成,用时:%v", time.Since(startTime2))
    }
}

分类: go

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72643 人次

浙公网安备33011302000604

辽ICP备20003309号