Bạn có thể preallocate không gian cho một String ở Julia?

Question

Tài liệu của Julia mô tả pre-allocating memory cho số Array để cải thiện hiệu suất bằng cách tránh thu gom rác thải. Điều này có thể làm với một String là một Vector, sau khi tất cả? String mã nguồn là here.

Trường hợp sử dụng của tôi là tôi đang xử lý các khối văn bản lớn, sử dụng readuntil() để lấy một đoạn, sau đó thực hiện regex match() hoặc matchall() hoặc replace(). Tôi đã mã hóa nó trong Perl, nhưng muốn xem liệu Julia có thể nhanh hơn không. Tôi đã biết độ dài của chuỗi dài nhất mà tôi sẽ phải xử lý.

fs=open(fn,"r") 
    while !eof(fs) 
     text = readuntil(fs, "</tag>") 
     text = match(r"pattern"s, text).match 
     text = replace(text, r"badpattern", "goodpattern") 
     text = replace(text, r"anotherbadpattern", "betterpattern") 
     ... (dozens more replacements) 
    end 
close(fs) 

Tôi mong đợi đĩa I/O là nút cổ chai chính, nhưng tôi quan tâm đến việc tìm hiểu về mọi thứ sẽ hữu ích. Tôi hoan nghênh mọi đề xuất về các phương pháp có thể để đẩy nhanh quá trình.

Answer 1

Chuỗi trong Julia là bất biến do đó khái niệm về phân bổ trước không hoạt động.

julia> a = "aaaa"; 
julia> pointer(a) 
    Ptr{UInt8} @0x0000000119628f50 

julia> a = "bbbb"; 
julia> pointer(a) 
    Ptr{UInt8} @0x000000011963a030 

Answer 2

Thứ nhất,

"Premature tối ưu hóa là gốc rễ của mọi tội lỗi" - Donald Knuth

Có nói rằng, các replace mã trong cơ sở cho thấy nó đọc source String và tìm các kết quả phù hợp để thay thế và nó viết các phần của String kết quả thành một IOBuffer. Sau khi xử lý nó đọc chuỗi đầu ra từ IOBuffer. Về cơ bản, điều này có hai bản sao của chuỗi nguồn. Nếu độ dài tối đa của chuỗi đầu vào (và do đó cũng là đầu ra) được biết, IOBuffer trong replace có thể được sử dụng lại thay vì được cấp phát.

Để đưa phân tích này vào mã, xác định như sau replace! (dựa trên replace):

function replace!(out::IOBuffer, str::String, pattern, repl, limit::Integer) 
    n = 1 
    e = endof(str) 
    i = a = start(str) 
    r = search(str,pattern,i) 
    j, k = first(r), last(r) 
    Base.ensureroom(out, floor(Int, 1.2sizeof(str))) 
    while j != 0 
    if i == a || i <= k 
     Base.write_sub(out, str.data, i, j-i) 
     Base._replace(out, repl, str, r, pattern) 
    end 
    if k<j 
     i = j 
     k = nextind(str, j) 
    else 
     i = k = nextind(str, k) 
    end 
    if j > e 
     break 
    end 
    r = search(str,pattern,k) 
    j, k = first(r), last(r) 
    n == limit && break 
    n += 1 
    end 
    write(out, SubString(str,i)) 
    takebuf_string(out) 
end 

replace!(out::IOBuffer,s::AbstractString, pat, f, n::Integer) = 
    replace!(out, String(s), pat, f, n) 
replace!(out::IOBuffer,s::AbstractString, pat, r) = 
    replace!(out, s, pat, r, 0) 

Và bây giờ,

const string1 = "the quick brown fox jumped over the lazy dog" 
const out = IOBuffer(100) 

replace!(out,string1,"quick","slow") 

sẽ thực hiện một sự thay thế mà không cần phân bổ IOBuffer. Sau khi replace!, out có thể được sử dụng lại (nó sẽ bị để trống bởi takebuf_string trong replace!. Đo điểm chuẩn cho thấy điều này sẽ giảm phân bổ 50% và tăng tốc quá trình. Nếu nhiều câu hỏi replace được sử dụng, như bạn đề xuất trong câu hỏi này nên cung cấp cho 30% hoặc cải thiện hơn.

Nếu bạn cố gắng này, nó sẽ được tốt đẹp để nghe một kết quả benchmark thế giới thực. có lẽ một số phiên bản của replace! nên được đưa vào cơ sở.

Answer 3

trong Julia 0,6 nó là dễ dàng hơn để thử một phiên bản tối ưu hơn, cụ thể là chúng ta có thể có một IOBuffer và một String chia sẻ cùng một bộ nhớ. và xử lý một Chuỗi, do đó, điều này cho chúng ta cơ hội để làm replace! mà không có bất kỳ phân bổ nào.

Một loạt các câu lệnh replace! có thể thay thế giữa hai bộ đệm được phân bổ trước và (gần như) tránh bất kỳ phân bổ nào.

Cụ thể là:

# version 0.6.0-pre.alpha.220 
function replace!(out::IOBuffer, str::AbstractString, 
    pattern, repl, limit::Integer) 
    n = 1 
    e = endof(str) 
    i = a = start(str) 
    r = search(str,pattern,i) 
    j, k = first(r), last(r) 
    out.size = 0 
    out.ptr = 1 
    while j != 0 
     if i == a || i <= k 
      Base.unsafe_write(out, pointer(str, i), UInt(j-i)) 
      Base._replace(out, repl, str, r, pattern) 
     end 
     if k<j 
      i = j 
      k = nextind(str, j) 
     else 
      i = k = nextind(str, k) 
     end 
     if j > e 
      break 
     end 
     r = search(str,pattern,k) 
     j, k = first(r), last(r) 
     n == limit && break 
     n += 1 
    end 
    write(out, SubString(str,i)) 
    return out.ptr-1 
end 

Và để lái xe chức năng này và tiền phân bổ bộ đệm chúng ta làm:

const string1 = "."^1000 
const string2 = "."^1000 

const io1 = IOBuffer(convert(Vector{UInt8},string1),true,true,length(string1)) 
const io2 = IOBuffer(convert(Vector{UInt8},string2),true,true,length(string2)) 

write(io1,"hello world. "^30) # test string to manipulate 

function switcheroo!() 
    replace!(io2,SubString(string1,1,io1.ptr-1),"hello","what's up",0) 
    replace!(io1,SubString(string2,1,io2.ptr-1),"what's up","hello",0) 
end 

switcheroo!() 

Chức năng switcheroo! thay thế hello với whats up và ngược lại. Rất đơn giản để sửa đổi mã để xử lý một loạt các replace như câu hỏi gợi ý là bắt buộc.

Ghi chú:

1. này được kết hợp chặt chẽ hơn với internals Julia String và do đó có thể không ổn định đi về phía trước với các phiên bản tương lai Julia (nhưng chỉ lựa chọn thay thế như hiệu quả có lẽ sẽ vẫn).

2. Vẫn còn hai (pesky!) Phân bổ cho mỗi replace! cho hai giá trị SubString được tạo. Các phân bổ này là 64 byte và không phát triển với kích thước chuỗi.