Existe uma alternativa mais eficiente para avançar na busca por um único caractere?

7

Eu preciso dividir o conteúdo de um buffer em uma lista de seqüências de caracteres. O caractere nulo é usado para separar os itens.

Os itens foram separados por caracteres de nova linha, então eu poderia usar a mesma abordagem que process-lines:

(let (lines)
  (while (not (eobp))
    (setq lines (cons (buffer-substring-no-properties
               (line-beginning-position)
               (line-end-position))
              lines))
    (forward-line 1))
  (nreverse lines))

Eu suponho que forward-lineé eficiente, mas o uso line-beginning-positione line-end-positioné um pouco suspeito. Mas como o caractere nulo é usado, não posso fazer isso de qualquer maneira.

Uma maneira de fazer isso seria:

(split-string (buffer-string) "\0")

Eu também estava considerando essa variação:

(split-string (buffer-substring-no-properties (point-min)
                                              (point-max))
              "\0")

Isso é realmente mais eficiente? O texto no buffer não é propertizado, mas eu imaginaria que procurar as propriedades inexistentes ainda adicionaria uma sobrecarga.

Em vez de ler o buffer em uma string e depois dividi-la, eu gostaria de trabalhar diretamente no buffer - novamente assumindo que isso é realmente mais eficiente.

(let ((beg (point))
      items)
  (while (search-forward "\0" nil t)
    (push (buffer-substring-no-properties beg (1- (point))) items)
    (setq beg (point)))
  (nreverse items))

Existe algo assim search-forward-chare isso seria mais eficiente do que search-forward?

Suponho que eu poderia usar:

(while (not (= (char-after) ?\0)) (forward-char))

Mas eu esperaria que isso estivesse disponível como uma função se fosse mais eficiente do que search-forward.

search characters tarso
fonte
11
(skip-chars-forward "^\0")deve fazer o trabalho.
619 Tobias
@ Tobias Apenas me derrote. :) É quase três vezes mais rápido que (search-forward "\0" nil t)na minha máquina.
Basil
@ Basil No entanto, o programa geral precisa ser elaborado. Frequentemente, as funções c puras batem em coisas compiladas em bytes. Então, talvez a (split-string (buffer-substring-no-properties) "\0")variante vença. Além disso, o desempenho pode depender da estrutura do texto. (Existem muitas provas curtas terminadas por nulo caracteres ou há grandes fichas com apenas alguns nulos-caracteres.)
Tobias
@ Tobias eu sei, eu estava indo para fazer mais alguns testes por curiosidade de qualquer maneira. @ tarso Note que char-afterpode retornar nil.
Basil
11
Você se certificou de que a divisão da cadeia de buffer 0é realmente o gargalo do seu aplicativo antes de aprofundar tanto?
Tobias

Respostas:

10

Eu executei os seguintes benchmarks em

GNU Emacs 27.0.50
(build 14, x86_64-pc-linux-gnu, X toolkit, Xaw3d scroll bars)
of 2018-02-21

sem personalizações, ou seja, iniciando o Emacs com a -Qbandeira.

Existe uma alternativa mais eficiente para avançar na busca por um único caractere?

[...]

Existe algo assim search-forward-chare isso seria mais eficiente do que search-forward?

Como o @Tobias aponta corretamente em um comentário , é uma alternativa mais rápida para search-forwardprocurar um único caractere skip-chars-forward. Alguns benchmarks a seguir.

Caractere nulo no final do buffer

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Newline-terminated line of random printable ASCII
    (insert (make-string 200 (+ #x20 (random #x5e))) ?\n))
  ;; NUL
  (insert 0)
  (garbage-collect)
  (message "a: %s" (benchmark-run-compiled 1000
                     (goto-char (point-min))
                     (search-forward "\0")))
  (message "b: %s" (benchmark-run-compiled 1000
                     (goto-char (point-min))
                     (skip-chars-forward "^\0"))))

dá

a: (6.959186105 0 0.0)
b: (2.527484532 0 0.0)

Linhas longas terminadas em nulo

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Null-terminated line of random printable ASCII
    (insert (make-string 200 (+ #x20 (random #x5e))) 0))
  (garbage-collect)
  (message "a: %s" (benchmark-run-compiled 1000
                     (goto-char (point-min))
                     (while (search-forward "\0" nil t))))
  (message "b: %s" (benchmark-run-compiled 1000
                     (goto-char (point-min))
                     (while (progn (skip-chars-forward "^\0")
                                   (not (eobp)))
                       (forward-char)))))

dá

a: (10.596461232 0 0.0)
b: (4.896477926  0 0.0)

Linhas curtas terminadas em nulo

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Null-terminated line of random printable ASCII
    (insert (make-string 4 (+ #x20 (random #x5e))) 0))
  (garbage-collect)
  (message "a: %s" (benchmark-run-compiled 1000
                     (goto-char (point-min))
                     (while (search-forward "\0" nil t))))
  (message "b: %s" (benchmark-run-compiled 1000
                     (goto-char (point-min))
                     (while (progn (skip-chars-forward "^\0")
                                   (not (eobp)))
                       (forward-char)))))

dá

a: (3.642238859 0 0.0)
b: (2.281851267 0 0.0)

Observe que a menor diferença de tempo com linhas curtas provavelmente ocorre devido à maior complexidade do loop do teste (b). Além disso, invertendo o sentido de busca (ou seja, utilizando point-max, skip-chars-backward, bobp, e backward-char) não faz qualquer diferença perceptível.

Isso é realmente mais eficiente? O texto no buffer não é propertizado, mas eu imaginaria que procurar as propriedades inexistentes ainda adicionaria uma sobrecarga.

Vamos ver:

(defun a ()
  (buffer-string))

(defun b ()
  (buffer-substring (point-min) (point-max)))

(defun c ()
  (buffer-substring-no-properties (point-min) (point-max)))

(dolist (f '(a b c))
  (byte-compile f))

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Random-length random-printable-ASCII newline-terminated line
    (dotimes (_ (random 200))
      (insert (+ #x20 (random #x5e))))
    (insert ?\n))
  (garbage-collect)
  (message "a: %s" (benchmark-run 1000 (a)))
  (garbage-collect)
  (message "b: %s" (benchmark-run 1000 (b)))
  (garbage-collect)
  (message "c: %s" (benchmark-run 1000 (c))))

dá

a: (7.069123577999999 1000 6.8170885259999885)
b: (7.072005507999999 1000 6.819331175000003)
c: (7.064939498999999 1000 6.812288113000008)

portanto, não há diferença em um buffer não autorizado. Observe que eu tive que fazer a chamada buffer-stringem uma função separada por compilação de bytes, caso contrário ela teria sido otimizada para uma constante abaixo benchmark-run-compiled.

Em vez de ler o buffer em uma string e depois dividi-la, eu gostaria de trabalhar diretamente no buffer - novamente assumindo que isso é realmente mais eficiente.

Vamos checar. As três funções a seguir devem fornecer o mesmo resultado:

(defun a ()
  (split-string (buffer-string) "\0"))

(defun b ()
  (goto-char (point-min))
  (let (l)
    (while (let ((p (point)))
             (push (buffer-substring-no-properties
                    p (+ p (skip-chars-forward "^\0")))
                   l)
             (not (eobp)))
      (forward-char))
    (nreverse l)))

(defun c ()
  (goto-char (point-max))
  (let (l)
    (while (let ((p (point)))
             (push (buffer-substring-no-properties
                    p (+ p (skip-chars-backward "^\0")))
                   l)
             (not (bobp)))
      (backward-char))
    l))

(dolist (f (a b c))
  (byte-compile f))

Caractere nulo no final do buffer

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Newline-terminated line of random printable ASCII
    (insert (make-string 200 (+ #x20 (random #x5e))) ?\n))
  ;; NUL
  (insert 0)
  (garbage-collect)
  (message "a: %s" (benchmark-run 100 (a)))
  (garbage-collect)
  (message "b: %s" (benchmark-run 100 (b)))
  (garbage-collect)
  (message "c: %s" (benchmark-run 100 (c))))

dá

a: (2.46373737  200 1.5349787340000005)
b: (1.046089159 100 0.7499454190000003)
c: (1.040357797 100 0.7460460909999975)

Linhas longas terminadas em nulo

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Null-terminated line of random printable ASCII
    (insert (make-string 200 (+ #x20 (random #x5e))) 0))
  (garbage-collect)
  (message "a: %s" (benchmark-run 100 (a)))
  (garbage-collect)
  (message "b: %s" (benchmark-run 100 (b)))
  (garbage-collect)
  (message "c: %s" (benchmark-run 100 (c))))

dá

a: (4.065745779999999  300 2.3008262569999927)
b: (2.787263217        274 2.097104968000009)
c: (2.7745770399999996 275 2.112500514999999)

Linhas curtas terminadas em nulo

(with-temp-buffer
  (dotimes (_ 10000)
    ;; Null-terminated line of random printable ASCII
    (insert (make-string 4 (+ #x20 (random #x5e))) 0))
  (garbage-collect)
  (message "a: %s" (benchmark-run 100 (a)))
  (garbage-collect)
  (message "b: %s" (benchmark-run 100 (b)))
  (garbage-collect)
  (message "c: %s" (benchmark-run 100 (c))))

dá

a: (1.346149274 85 0.640683847)
b: (1.010766266 80 0.6072433190000055)
c: (0.989048037 80 0.6078114269999908)

Portanto, você provavelmente pode obter uma aceleração de ~ 2x usando skip-chars-{forward,backward}, mas como o @Tobias aponta , vale a pena a complexidade extra?

Manjericão
fonte