Efektywne dołączanie do pojemnika o zmiennej długości łańcuchów (Golang)

Question

Problem:

muszę zastosować wiele regexes do każdej linii dużego pliku dziennika (jak kilku GB długi), gromadzą niepuste mecze i umieść je wszystkie w tablicy (do serializacji i przesłania przez sieć).

Plastry nie są zbyt pomocne, jeśli odpowiedź na this question posiada:

Jeżeli plaster nie ma wystarczającej zdolności, dołączyć trzeba będzie przeznaczyć nową pamięć i skopiować starą skończona. Dla plastrów z < 1024 elementów, podwoi pojemność, dla plastrów z> 1024 elementami zwiększy ją o czynnik 1,25.

Ponieważ nie może być dosłownie setki tysięcy dopasowań regex, nie mogę naprawdę przewidzieć długość/pojemność plasterka. Nie mogę zrobić tego zbyt dużego albo "na wszelki wypadek" bc to będzie marnować pamięć (albo będzie ?, jeśli alokator pamięci jest na tyle sprytny, aby nie przydzielić zbyt dużo pamięci, która nie jest zapisana, może mógłbym użyć ogromnej pojemności plastra bez większych szkód?).

Więc myślę o następującej alternatywy:

1. mają podwójnie połączonej listy zapałek (http://golang.org/pkg/container/list/)
2. oblicz jego długość (? Czy len() pracy)
3. przydzielenia kawałek tego pojemność
4. kopia strunowe wskaźniki do tego wycinka

Czy istnieje mniej pracy W jaki sposób osiągnąć ten cel w Go (dołączyć z ~ O (1) dodać złożoność)?

(golang początkujących tu oczywiście)

Answer 1

append() jest średnia (amortyzowane) Koszt już O (1), ponieważ rośnie tablicę o procent za każdym razem. Gdy tablica staje się większa, staje się coraz droższa, ale proporcjonalnie rzadsza. Fragment o wielkości 10M będzie 10-krotnie droższy w rozwoju niż plasterek o wielkości 1M, ale ponieważ dodatkowa pojemność, którą przydzielamy, jest proporcjonalna do rozmiaru, będzie to również 10-krotna liczba wywołań append(slice, item), aż do następnego wzrostu . Rosnący koszt i malejąca częstość ponownych przydziałów znoszą się, pozostawiając średni koszt stały, tj. O (1).

Ta sama zasada dotyczy również tablic dynamicznych o innych językach: implementacja Microsoft std::vector najwyraźniej powiększa tablicę o 50% za każdym razem, na przykład. Amortyzacja O (1) nie oznacza, że ​​nie płacisz nic za alokacje, tylko że nadal płacisz z tą samą średnią stawką co twoja tablica zwiększa się.

Na moim laptopie mogłem uruchomić milion slice = append(slice, someStaticString) s w 77ms. Jednym z powodów, dla którego jest to szybkie, które siritinga odnotowano poniżej, jest to, że "kopiowanie" ciągu w celu powiększenia tablicy to po prostu kopiowanie nagłówka (pary wskaźnika/długości), a nie kopiowanie zawartości. 100 000 nagłówków łańcuchów wciąż nie może zawierać więcej niż 2 MB danych, co nie jest wielkim problemem w porównaniu z innymi ilościami danych, z którymi pracujesz.

container/list okazało się ~ 3x wolniej dla mnie w microbenchmark; Dołączona lista-dołączeń to oczywiście również czas stały, ale wyobrażam sobie, że append ma niższą stałą, ponieważ zazwyczaj wystarczy napisać kilka słów pamięci i nie można przydzielić elementu listy itp. Kod czasu nie zadziała w plac zabaw dla dzieci, ale można skopiować ten lokalnie i uruchomić go zobaczyć siebie: http://play.golang.org/p/uYyMScmOjX

---

ale pytasz bardziej konkretne pytanie tutaj o aplikacji grep -jak (i ​​dzięki za zadając szczegółowe pytania z kontekstu). W tym celu zaleca się, że jeśli szukasz przebojów dzienników, najlepiej jest unikać buforowania całego wyjścia w pamięci RAM.

Możesz napisać coś, aby przesyłać strumieniowo wyniki w postaci pojedynczej funkcji: logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp); możesz też alternatywnie zrobić out a chan []byte lub func(match []byte) (err error), jeśli nie chcesz, aby kod, który wysyła wyniki, był zbyt mocno zazębiony z kodem grep.

(Na []byte vs. string: a []byte wydaje się do pracy tutaj i unika []byte < =>string konwersje kiedy to zrobić I/O, więc wolałbym, że nie wiem, co wszyscy ci”. re robi, choć i jeśli trzeba string jest w porządku).

Jeśli zrobić zachować całą listę mecz w pamięci RAM, należy pamiętać, że utrzymywanie wokół odniesieniu do części wielkiego łańcucha lub bajtów plaster utrzymuje całość ciąg źródłowy/kawałek z bycia zebranym. Więc jeśli idziesz tą trasą, to wbrew intuicji możesz chcieć kopiować mecze, aby uniknąć przechowywania wszystkich danych logu źródłowego w pamięci RAM.

Answer 2

Próbowałem poddać destylacji twoje pytanie w bardzo prosty przykład.

Ponieważ nie może być "setki tysięcy dopasowań wyrażeń regularnych", zrobiłem dużą początkową alokację 1 M (1024 * 1024) wpisów dla zdolności wycinania matches. Plasterek jest typem referencyjnym. Nagłówek "struct" nagłówka ma długość, pojemność i wskaźnik dla łącznej liczby 24 (3 * 8) bajtów w 64-bitowym systemie operacyjnym. Początkowa alokacja dla wycinka 1 M wpisów wynosi zatem tylko 24 (24 * 1) MB. Jeśli jest więcej niż 1 M wpisów, przydzielony zostanie nowy wycinek o pojemności 1,25 (1 + 1/4) M, a do niego zostaną skopiowane istniejące pozycje nagłówka 1 M (24 MB).

Podsumowując, można uniknąć znacznego obciążenia wielu różnych append s przez początkowe przydzielanie pojemności plasterka. Im większy problem z pamięcią, tym wszystkie dane są zapisywane i przywoływane dla każdego dopasowania. O wiele większy problem z czasem procesora to czas potrzebny na wykonanie 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 
     } 
    } 
}