¿Existe una alternativa más eficiente para buscar hacia adelante cuando se busca un solo personaje?

7

Necesito dividir el contenido de un búfer en una lista de cadenas. El carácter nulo se usa para separar los elementos.

Si los elementos estaban separados por caracteres de nueva línea, entonces podría usar el mismo enfoque 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))

Supongo que forward-linees eficiente, pero el uso de line-beginning-positiony line-end-positiones un poco sospechoso. Pero como se usa el carácter nulo, no puedo hacerlo de todos modos.

Una forma de hacerlo sería:

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

También estaba considerando esta variación:

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

¿Es eso realmente más eficiente? El texto en el búfer no es propiedad, pero me imagino que buscar las propiedades inexistentes aún agregaría una sobrecarga.

En lugar de leer el búfer en una cadena y luego dividir la cadena, me gustaría trabajar directamente en el búfer, asumiendo nuevamente que eso es realmente más 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 así search-forward-chary sería eso más eficiente que search-forward?

Supongo que podría usar:

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

Pero esperaría que estuviera disponible como una función si fuera más eficiente que search-forward.

search characters tarsius
fuente
1
(skip-chars-forward "^\0")Debería hacer el trabajo.
Tobias
@Tobias Simplemente me ganó. :) Es casi tres veces más rápido que (search-forward "\0" nil t)en mi máquina.
Basil
@Basil Sin embargo, el programa general necesita ser perfilado. A menudo, las funciones c puras superan el compilado de bytes. Entonces, tal vez la (split-string (buffer-substring-no-properties) "\0")variante gane. Además, el rendimiento puede depender de la estructura del texto. (¿Hay muchas fichas cortas terminadas por caracteres nulos o hay fichas grandes con solo unos pocos caracteres nulos?)
Tobias
@Tobias Lo sé, iba a hacer algunas pruebas más por curiosidad de todos modos. @tarsius Tenga en cuenta que char-afterpuede volver nil.
Basil
1
¿Te aseguraste de que dividir la cadena del búfer en 0el cuello de botella de tu aplicación es realmente antes de cavar tan profundo?
Tobias

Respuestas:

10

He ejecutado los siguientes puntos de referencia en

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

sin personalizaciones, es decir, iniciando Emacs con la -Qbandera.

¿Existe una alternativa más eficiente para buscar hacia adelante cuando se busca un solo personaje?

[...]

¿Existe algo así search-forward-chary sería eso más eficiente que search-forward?

Como @Tobias señala correctamente en un comentario , es una alternativa más rápida a la search-forwardbúsqueda de un solo personaje skip-chars-forward. Algunos puntos de referencia siguen.

Carácter nulo al final del búfer

(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"))))

da

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

Largas líneas terminadas en 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)))))

da

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

Líneas cortas terminadas en 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)))))

da

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

Tenga en cuenta que la menor diferencia de tiempo con líneas cortas probablemente se deba a la mayor complejidad del bucle de la prueba (b). Además, la inversión de la dirección de la búsqueda (es decir, utilizando point-max, skip-chars-backward, bobp, y backward-char) no hace ninguna diferencia notable.

¿Es eso realmente más eficiente? El texto en el búfer no es propiedad, pero me imagino que buscar las propiedades inexistentes aún agregaría una sobrecarga.

Veamos:

(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))))

da

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

así que no hay diferencia en un búfer sin propiedad Tenga en cuenta que tuve que colocar la llamada buffer-stringen una función separada de compilación de bytes, de lo contrario, se habría optimizado a una constante debajo benchmark-run-compiled.

En lugar de leer el búfer en una cadena y luego dividir la cadena, me gustaría trabajar directamente en el búfer, asumiendo nuevamente que eso es realmente más eficiente.

Vamos a revisar. Las siguientes tres funciones deberían dar el mismo 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))

Carácter nulo al final del búfer

(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))))

da

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

Largas líneas terminadas en 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))))

da

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

Líneas cortas terminadas en 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))))

da

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

Entonces, probablemente pueda obtener una aceleración de ~ 2x usando skip-chars-{forward,backward}, pero como señala @Tobias , ¿vale la pena la complejidad adicional?

Albahaca
fuente