hiệu quả phụ thêm để một container biến chiều dài của chuỗi (Golang)

Question

Vấn đề:

tôi cần phải áp dụng nhiều regexes để mỗi dòng của một file log lớn (như vài GB dài), thu thập các trận đấu không trống và đặt tất cả chúng trong một mảng (để tuần tự hóa và gửi nó qua mạng).

Slices là không thể giúp ích nhiều nếu câu trả lời cho this question giữ:

Nếu lát không có đủ năng lực, thêm sẽ cần phải phân bổ bộ nhớ mới và sao chép một tuổi hơn. Đối với các slice có các phần tử < 1024, nó sẽ tăng gấp đôi dung lượng, đối với các lát có> 1024 phần tử, nó sẽ tăng nó theo hệ số 1.25.

Vì có thể có hàng trăm nghìn kết quả phù hợp regex, tôi không thể dự đoán được chiều dài/công suất của một lát. Tôi không thể làm cho nó quá lớn hoặc là "chỉ trong trường hợp" bc này sẽ lãng phí bộ nhớ (hoặc nó sẽ? Nếu bộ cấp phát bộ nhớ là đủ thông minh không phân bổ quá nhiều bộ nhớ mà không được viết vào, có lẽ tôi có thể sử dụng một công suất lớn slice mà không gây hại nhiều?).

Vì vậy, tôi đang suy nghĩ về thay thế sau:

1. có một danh sách gấp đôi liên kết các trận đấu (http://golang.org/pkg/container/list/)
2. calc chiều dài của nó (? Sẽ len() làm việc)
3. preallocate một lát này công suất
4. con trỏ chuỗi sao chép vào lát này

Có ít lao động hơn không ious cách để đạt được mục tiêu này trong Go (nối với ~ O (1) nối thêm phức tạp)?

(golang newbie ở đây tất nhiên) trung bình (khấu hao) chi phí

Answer 1

append() 's đã là O (1) vì nó phát triển mảng bởi một mỗi lần tỷ lệ phần trăm. Khi mảng được lớn hơn, phát triển nó trở nên đắt hơn nhưng tỉ lệ hiếm hơn. Một lát cắt 10M sẽ đắt gấp 10 lần để phát triển hơn 1M slice, nhưng vì dung lượng bổ sung mà chúng tôi đang phân bổ tỷ lệ thuận với kích thước, nó cũng sẽ gấp 10 lần các cuộc gọi append(slice, item) cho đến lần tiếp theo . Chi phí ngày càng tăng và tần suất giảm của các lần phân bổ lại bị hủy bỏ, để lại hằng số chi phí trung bình, tức là O (1).

Ý tưởng tương tự cũng áp dụng các mảng có kích thước động của các ngôn ngữ khác: Ví dụ: triển khai của Microsoft std::vector dường như tăng mảng lên 50% mỗi lần. Phân bổ O (1) không có nghĩa là bạn không phải trả gì cho phân bổ, chỉ rằng bạn tiếp tục thanh toán với cùng tốc độ trung bình khi mảng của bạn lớn hơn.

Trên máy tính xách tay của tôi, tôi có thể chạy một triệu slice = append(slice, someStaticString) s trong 77ms. Một lý do nó nhanh chóng, mà siritinga lưu ý dưới đây, là "sao chép" chuỗi để mở rộng mảng thực sự chỉ cần sao chép tiêu đề chuỗi (một con trỏ/chiều dài cặp), không sao chép nội dung. 100.000 tiêu đề chuỗi vẫn dưới 2MB để sao chép, không phải là một vấn đề lớn so với số lượng dữ liệu khác mà bạn đang làm việc.

container/list tắt ~ 3x chậm hơn cho tôi trong một microbenchmark; liên kết danh sách liên kết cũng là thời gian liên tục, tất nhiên, nhưng tôi tưởng tượng append có hằng số thấp hơn vì thường có thể chỉ ghi vào một vài từ bộ nhớ và không cấp phát một mục danh sách, v.v. Mã thời gian sẽ không hoạt động trong sân chơi nhưng bạn có thể sao chép này tại địa phương và chạy nó để xem bản thân: http://play.golang.org/p/uYyMScmOjX

---

nhưng bạn đang hỏi một câu hỏi cụ thể hơn ở đây về một ứng dụng grep -like (và cảm ơn cho hỏi một câu hỏi chi tiết với ngữ cảnh). Đối với điều đó, khuyến nghị cuối cùng là nếu bạn đang tìm kiếm các hợp đồng biểu diễn của các bản ghi, có lẽ tốt nhất là tránh đệm toàn bộ đầu ra trong RAM.

Bạn có thể viết điều gì đó để truyền trực tuyến kết quả dưới dạng một chức năng duy nhất: logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp); bạn có thể thực hiện theo cách khác là out a chan []byte hoặc func(match []byte) (err error) nếu bạn không muốn mã gửi kết quả quá bị ghim với mã grep.

(Trên []byte vs string: a []byte dường như thực hiện công việc ở đây và tránh []byte < =>string chuyển đổi khi bạn làm I/O, vì vậy tôi muốn mà tôi không biết những gì tất cả các bạn'. làm lại, mặc dù, và nếu bạn cần string nó là tốt.)

Nếu bạn giữ nguyên toàn bộ danh sách đối sánh trong RAM, hãy lưu ý rằng việc giữ một tham chiếu đến một phần của một chuỗi lớn hoặc lát byte giữ toàn bộ nguồn chuỗi/slice từ rác được thu thập. Vì vậy, nếu bạn đi tuyến đường đó, sau đó ngược lại bạn thực sự có thể muốn để sao chép các kết quả phù hợp để tránh lưu giữ tất cả dữ liệu nhật ký nguồn trong RAM.

Answer 2

Tôi đã cố gắng chắt lọc câu hỏi của bạn thành một ví dụ rất đơn giản.

Vì có thể có "hàng trăm nghìn kết quả phù hợp regex", tôi đã phân bổ ban đầu lớn 1 M (1024 * 1024) mục nhập cho dung lượng lát matches. Một lát là một kiểu tham chiếu. Tiêu đề slice 'struct' có chiều dài, dung lượng và con trỏ cho tổng số 24 (3 * 8) byte trên hệ điều hành 64 bit. Phân bổ ban đầu cho một lát 1 M mục do đó chỉ có 24 (24 * 1) MB. Nếu có nhiều hơn 1 M mục, một lát mới có dung lượng 1,25 (1 + 1/4) mục M sẽ được cấp phát và các mục nhập tiêu đề 1 M slice hiện có (24 MB) sẽ được sao chép vào nó.

Tóm lại, bạn có thể tránh phần lớn chi phí của nhiều số append giây bằng cách ban đầu phân bổ công suất lát. Vấn đề bộ nhớ lớn hơn là tất cả dữ liệu được lưu và tham chiếu cho mỗi trận đấu. Vấn đề thời gian CPU lớn hơn nhiều là thời gian thực hiện để thực hiện regexp.FindAll.

package main 

import (
    "bufio" 
    "fmt" 
    "os" 
    "regexp" 
) 

var searches = []*regexp.Regexp{ 
    regexp.MustCompile("configure"), 
    regexp.MustCompile("unknown"), 
    regexp.MustCompile("PATH"), 
} 

var matches = make([][]byte, 0, 1024*1024) 

func main() { 
    logName := "config.log" 
    log, err := os.Open(logName) 
    if err != nil { 
     fmt.Fprintln(os.Stderr, err) 
     os.Exit(1) 
    } 
    defer log.Close() 
    scanner := bufio.NewScanner(log) 
    for scanner.Scan() { 
     line := scanner.Bytes() 
     for _, s := range searches { 
      for _, m := range s.FindAll(line, -1) { 
       matches = append(matches, append([]byte(nil), m...)) 
      } 
     } 
    } 
    if err := scanner.Err(); err != nil { 
     fmt.Fprintln(os.Stderr, err) 
    } 
    // Output matches 
    fmt.Println(len(matches)) 
    for i, m := range matches { 
     fmt.Println(string(m)) 
     if i >= 16 { 
      break 
     } 
    } 
}