Gibt es eine effizientere Alternative zur Vorwärtssuche bei der Suche nach einem einzelnen Zeichen?

7

Ich muss den Inhalt eines Puffers in eine Liste von Zeichenfolgen aufteilen. Das Nullzeichen wird verwendet, um die Elemente zu trennen.

Wenn die Elemente durch Zeilenumbrüche getrennt wurden, konnte ich den gleichen Ansatz verwenden wie 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))

Ich gehe davon aus, dass forward-linees effizient ist, aber die Verwendung von line-beginning-positionund line-end-positionist ein bisschen verdächtig. Aber da das Nullzeichen verwendet wird, kann ich das sowieso nicht tun.

Eine Möglichkeit wäre:

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

Ich habe auch über diese Variante nachgedacht:

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

Ist das eigentlich effizienter? Der Text im Puffer ist nicht geeignet, aber ich würde mir vorstellen, dass das Suchen nach nicht vorhandenen Eigenschaften immer noch einen Overhead verursachen würde.

Anstatt den Puffer in eine Zeichenfolge einzulesen und dann die Zeichenfolge aufzuteilen, möchte ich stattdessen direkt am Puffer arbeiten - wiederum unter der Annahme, dass dies tatsächlich effizienter ist.

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

Gibt es so etwas search-forward-charund wäre das effizienter als search-forward?

Ich nehme an, ich könnte verwenden:

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

Aber ich würde erwarten, dass das als Funktion verfügbar ist, wenn es effizienter wäre als search-forward.

search characters Tarsius
quelle
1
(skip-chars-forward "^\0")sollte den Job machen.
Tobias
@Tobias Schlagen Sie mich einfach dazu. :) Es ist fast dreimal so schnell wie (search-forward "\0" nil t)auf meiner Maschine.
Basil
@Basil Trotzdem muss das Gesamtprogramm profiliert werden. Oft schlagen reine C-Funktionen bytekompiliertes Zeug. Vielleicht (split-string (buffer-substring-no-properties) "\0")gewinnt also die Variante. Darüber hinaus kann die Leistung von der Struktur des Textes abhängen. (Gibt es viele kurze Token, die mit Nullzeichen abgeschlossen sind, oder gibt es große Token mit nur wenigen Nullzeichen?)
Tobias
@Tobias Ich weiß, ich wollte sowieso aus Neugier einige weitere Tests machen. @tarsius Beachten Sie, dass zurückkehren char-afterkann nil.
Basil
1
Haben Sie sichergestellt, dass das Aufteilen der Pufferzeichenfolge bei 0wirklich der Engpass Ihrer Anwendung ist, bevor Sie so tief gegraben haben?
Tobias

Antworten:

10

Ich habe die folgenden Benchmarks durchgeführt

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

ohne Anpassungen, dh indem Emacs mit der -QFlagge gestartet wird .

Gibt es eine effizientere Alternative zur Vorwärtssuche bei der Suche nach einem einzelnen Zeichen?

[...]

Gibt es so etwas search-forward-charund wäre das effizienter als search-forward?

Wie @Tobias in einem Kommentar richtig hervorhebt , ist eine schnellere Alternative zur search-forwardSuche nach einem einzelnen Zeichen skip-chars-forward. Einige Benchmarks folgen.

Nullzeichen am Pufferende

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

gibt

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

Lange nullterminierte Zeilen

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

gibt

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

Kurze nullterminierte Zeilen

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

gibt

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

Es ist zu beachten, dass der geringere Zeitunterschied bei kurzen Leitungen wahrscheinlich auf die höhere Schleifenkomplexität von Test (b) zurückzuführen ist. Darüber hinaus die Richtung der Suche Umkehren (dh mit point-max, skip-chars-backward, bobp, und backward-char) macht keinen spürbaren Unterschied.

Ist das eigentlich effizienter? Der Text im Puffer ist nicht geeignet, aber ich würde mir vorstellen, dass das Suchen nach nicht vorhandenen Eigenschaften immer noch einen Overhead verursachen würde.

Wir werden sehen:

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

gibt

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

also kein Unterschied in einem nicht propertisierten Puffer. Beachten Sie, dass ich den Aufruf von buffer-stringin eine separate bytekompilierte Funktion stellen musste, sonst wäre er auf eine Konstante unter optimiert worden benchmark-run-compiled.

Anstatt den Puffer in eine Zeichenfolge einzulesen und dann die Zeichenfolge aufzuteilen, möchte ich stattdessen direkt am Puffer arbeiten - wiederum unter der Annahme, dass dies tatsächlich effizienter ist.

Lass uns nachsehen. Die folgenden drei Funktionen sollten das gleiche Ergebnis liefern:

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

Nullzeichen am Pufferende

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

gibt

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

Lange nullterminierte Zeilen

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

gibt

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

Kurze nullterminierte Zeilen

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

gibt

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

Sie können also wahrscheinlich eine ~ 2-fache skip-chars-{forward,backward}Beschleunigung erzielen, wenn Sie verwenden , aber wie @Tobias hervorhebt , ist es die zusätzliche Komplexität wert?

Basilikum
quelle