Чтение случайной строки из файла за постоянное время в Go

Question

У меня есть следующий код для выбора 2 случайных строк из файла, содержащего строки вида ip:port:

import (
  "os"
   "fmt"
"math/rand"
"log"
"time"
"unicode/utf8"

//"bufio"
)
func main() {
fmt.Println("num bytes in line is: \n", utf8.RuneCountInString("10.244.1.8:8080"))
file_pods_array, err_file_pods_array := os.Open("pods_array.txt")
if err_file_pods_array != nil {
        log.Fatalf("failed opening file: %s", err_file_pods_array)
}
//16 = num of bytes in ip:port pair
randsource := rand.NewSource(time.Now().UnixNano())
                randgenerator := rand.New(randsource)
                firstLoc := randgenerator.Intn(10)
                secondLoc := randgenerator.Intn(10)
                candidate1 := ""
                candidate2 := ""
num_bytes_from_start_first := 16 * (firstLoc + 1)
num_bytes_from_start_second := 16 * (secondLoc + 1)
    buf_ipport_first := make([]byte, int64(15))
    buf_ipport_second := make([]byte, int64(15))
    start_first := int64(num_bytes_from_start_first)
    start_second := int64(num_bytes_from_start_second)
    _, err_first := file_pods_array.ReadAt(buf_ipport_first, start_first)
    first_ipport_ep := buf_ipport_first
    if err_first == nil {
            candidate1 = string(first_ipport_ep)
    }
    _, err_second := file_pods_array.ReadAt(buf_ipport_second, start_second)
    second_ipport_ep := buf_ipport_second

    if err_second == nil {
            candidate2 = string(second_ipport_ep)
    }
fmt.Println("first is: ", candidate1)
fmt.Println("sec is: ", candidate2)
}

Иногда это печатает пустые или частичные строки. Почему это происходит и как я могу это исправить?

Пример вывода:

num bytes in line is:
 15
first is: 10.244.1.17:808
sec is:
10.244.1.11:80

Спасибо.

Answer 1

Если бы ваши строки были фиксированной длины, вы могли бы сделать это в постоянное время.

1. Длина каждой строки - L.
2. Проверьте размер файла, S.
3. Разделите S / L, чтобы получить количество строк N.
4. Выберите случайное число R от 0 до N-1.
5. Найдите R * L в файле .
6. Чтение L байтов.

---

Но у вас нет линий фиксированной длины . Мы не можем делать постоянное время, но мы можем сделать это в постоянной памяти и O (n) времени, используя технику из Искусство компьютерного программирования, том 2, раздел 3.4.2, Дональдом Э. Кнутом .

1. Читать строку. Запомните номер строки M.
2. Выберите случайное число от 1 до M.
3. Если это 1, запомните эту строку.

То есть, когда вы читаете каждая строка у вас есть 1 / M шанс выбрать его. В совокупности это добавляет до 1 / N для каждой строки.

Если у нас есть три строки, первая строка имеет шанс выбора 1/1. Тогда 1/2 шанс остаться. Тогда шанс 2/3 остаться. Общий шанс: 1 * 1/2 * 2/3 = 1 / 3.

Вторая строка имеет шанс 1/2 быть выбранным и шанс 2/3 остаться. Суммарный шанс: 1/2 * 2/3 = 1 / 3.

Третья строка имеет шанс 1/3 быть выбранным.

package main

import(
    "bufio"
    "fmt"
    "os"
    "log"
    "math/rand"
    "time"
);

func main() {
    file, err := os.Open("pods_array.txt")
    if err != nil {
        log.Fatal(err)
    }
    defer file.Close()

    scanner := bufio.NewScanner(file)

    randsource := rand.NewSource(time.Now().UnixNano())
    randgenerator := rand.New(randsource)

    lineNum := 1
    var pick string
    for scanner.Scan() {
        line := scanner.Text()
        fmt.Printf("Considering %v at 1/%v.\n", scanner.Text(), lineNum)

        // Instead of 1 to N it's 0 to N-1
        roll := randgenerator.Intn(lineNum)        
        fmt.Printf("We rolled a %v.\n", roll)
        if roll == 0 {
            fmt.Printf("Picking line.\n")
            pick = line
        }

        lineNum += 1
    }

    fmt.Printf("Picked: %v\n", pick)
}

Поскольку rand.Intn(n) возвращает [0,n), то есть от 0 до n-1, мы проверяем 0, а не 1.

---

Может быть, вы думаете, "что если я найду случайную точку в файле и затем прочитаю следующее полная линия? Это не было бы постоянным временем, это было бы O (самая длинная линия), но это не было бы действительно случайным. Более длинные линии будут выделяться чаще.

---

Обратите внимание, что поскольку это (я предполагаю) все IP-адреса и порты, вы могли бы иметь постоянную длину записи. Сохраните IPv4-адрес как 32-битный, а порт - как 16-битный. 48 бит на строку.

Однако это не работает на IPv6. Для прямой совместимости сохраняйте все как IPv6: 128 бит для IP и 16 бит для порта. 144 бита на строку. Преобразование адресов IPv4 в IPv6 для хранения.

Это позволит вам выбирать произвольные адреса в постоянное время и сэкономит место на диске.

В качестве альтернативы, хранить их в SQLite .

Answer 2

нашел решение, используя ioutil и strings:

func main() {
randsource := rand.NewSource(time.Now().UnixNano())
                randgenerator := rand.New(randsource)
                firstLoc := randgenerator.Intn(10)
                secondLoc := randgenerator.Intn(10)
                candidate1 := ""
                candidate2 := ""

        dat, err := ioutil.ReadFile("pods_array.txt")
        if err == nil {
                ascii := string(dat)
                splt := strings.Split(ascii, "\n")
candidate1 = splt[firstLoc]
candidate2 = splt[secondLoc]
        }
fmt.Println(candidate1)
fmt.Println(candidate2)
}

Выход

10.244.1.3:8080
10.244.1.11:8080