为什么以下golang程序会导致运行时出现内存错误？

Question

该程序应该读取由一对int(每行一对)组成的文件并删除重复对.虽然它适用于小文件,但它会对大文件(例如1.5 GB的文件)引发运行时错误.最初,我认为是导致这种情况的地图数据结构,但即使在评论之后,它仍然会耗尽内存.任何想法为什么会这样？如何纠正呢？这是一个内存不足的数据文件:http://snap.stanford.edu/data/com-Orkut.html

package main
import (
    "fmt"
    "bufio"
    "os"
    "strings"
    "strconv"
)

func main() {
    file, err := os.Open(os.Args[1])
    if err != nil {
        panic(err.Error())
    }
    defer file.Close()
    type Edge struct {
        u, v int
    }
    //seen := make(map[Edge]bool)
    edges := []Edge{}
    scanner := bufio.NewScanner(file)

    for i, _ := strconv.Atoi(os.Args[2]); i > 0; i-- {
        scanner.Scan()
    }

    for scanner.Scan() {
        str := scanner.Text()
        edge := strings.Split(str, ",")
        u, _ := strconv.Atoi(edge[0])
        v, _ := strconv.Atoi(edge[1])
        var key Edge
        if u < v {
            key = Edge{u,v}
        } else {
            key = Edge{v,u}
        }
        //if seen[key] {
        //  continue
        //}
        //seen[key] = true
        edges = append(edges, key)
    }
    for _, e := range edges {
        s := strconv.Itoa(e.u) + "," + strconv.Itoa(e.v)
        fmt.Println(s)
    }
}

下面给出了一个示例输入.该程序可以如下运行(最后一个输入表示要跳过多少行).go run undup.go a.txt 1

# 3072441,117185083
1,2
1,3
1,4
1,5
1,6
1,7
1,8

Answer 1

我查看了这个文件:com-orkut.ungraph.txt它包含117,185,082行.数据的结构方式,每行至少16个字节.(Edge是两个64位整数)仅此为1.7GB.我过去遇到过这个问题,这可能是一个棘手的问题.您是否尝试针对特定用例(相关文件)或一般情况解决此问题？

在特定情况下,您可以利用的数据有以下几点:(1)密钥已排序;(2)它看起来每次连接存储两次,(3)数字似乎不大.以下是一些想法:

1. 如果您使用较小的类型键,您将使用较少的内存.试试吧uint32.

2. 您可以通过简单地查看第二列是否大于第一列来流式传输(不使用地图)其他文件的键:

   if u < v {
       // write the key to another file
   } else {
       // skip it because v will eventually show v -> u
   }
   

对于一般情况,您可以使用几种策略:

1. 如果结果列表的顺序无关紧要:使用磁盘上的哈希表来存储映射.有一堆这些:leveldb,sqlite,tokyo tyrant,......一个非常好的去掉就是螺栓.

   在for循环中,您只需检查一个存储桶是否包含给定的密钥.(您可以使用编码/二进制将整数转换为字节切片)如果是,则跳过它并继续.您需要将第二个for循环处理步骤移动到第一个for循环中,这样您就不必存储所有键.

2. 如果结果列表的顺序很重要(并且您无法保证输入是有序的):您还可以使用磁盘上的哈希表,但需要对其进行排序.螺栓经过排序,以便工作.添加所有键,然后在第二个循环中遍历它.

这是一个例子:(这个程序需要一段时间来运行1亿条记录)

package main

import (
    "bufio"
    "encoding/binary"
    "fmt"
    "github.com/boltdb/bolt"
    "os"
    "strconv"
    "strings"
)

type Edge struct {
    u, v int
}

func FromKey(bs []byte) Edge {
    return Edge{int(binary.BigEndian.Uint64(bs[:8])), int(binary.BigEndian.Uint64(bs[8:]))}
}

func (e Edge) Key() [16]byte {
    var k [16]byte
    binary.BigEndian.PutUint64(k[:8], uint64(e.u))
    binary.BigEndian.PutUint64(k[8:], uint64(e.v))
    return k
}

func main() {
    file, err := os.Open(os.Args[1])
    if err != nil {
        panic(err.Error())
    }
    defer file.Close()

    scanner := bufio.NewScanner(file)

    for i, _ := strconv.Atoi(os.Args[2]); i > 0; i-- {
        scanner.Scan()
    }

    db, _ := bolt.Open("ex.db", 0777, nil)
    defer db.Close()

    bucketName := []byte("edges")
    db.Update(func(tx *bolt.Tx) error {
        tx.CreateBucketIfNotExists(bucketName)
        return nil
    })

    batchSize := 10000
    total := 0
    batch := make([]Edge, 0, batchSize)
    writeBatch := func() {
        total += len(batch)
        fmt.Println("write batch. total:", total)
        db.Update(func(tx *bolt.Tx) error {
            bucket := tx.Bucket(bucketName)
            for _, edge := range batch {
                key := edge.Key()
                bucket.Put(key[:], nil)
            }
            return nil
        })
    }

    for scanner.Scan() {
        str := scanner.Text()
        edge := strings.Split(str, "\t")
        u, _ := strconv.Atoi(edge[0])
        v, _ := strconv.Atoi(edge[1])
        var key Edge
        if u < v {
            key = Edge{u, v}
        } else {
            key = Edge{v, u}
        }
        batch = append(batch, key)
        if len(batch) == batchSize {
            writeBatch()
            // reset the batch length to 0
            batch = batch[:0]
        }
    }
    // write anything leftover
    writeBatch()

    db.View(func(tx *bolt.Tx) error {
        tx.Bucket(bucketName).ForEach(func(k, v []byte) error {
            edge := FromKey(k)
            fmt.Println(edge)
            return nil
        })
        return nil
    })
}