快速字符串替换

Question

构建一个可能非常大的字符串后，我将对其中的单个字符（或字节，如有必要）进行大量更改，将其更改为另一个字符。

实际上，我的脚本是在构建填字游戏，所以字符串不会很长，但我的问题很笼统：

我如何利用不改变字符串（或任何更好的数据类型）长度这一事实来加快处理速度？

我想我正在寻找的部分内容是一种发送指针或字符串引用的方法，或者在 Tcl 的情况下是变量名。

我的另一个问题是 C 代码内部发生了什么。

这个调用会复制整个字符串零次、一次甚至两次吗？

set index [expr {$row * $width + $col}]
set puzzle [string replace $puzzle $index $index "E"]

Answer 1

如果满足两个条件，string replace 操作将进行 in-place 更改：

插入的字符串必须与被删除的字符串长度相同。我想这对你来说是显而易见的。
字符串必须在非共享引用中，这样其他任何东西都无法观察到被修改的值。（这是所有 Tcl 引用如何工作的关键部分；无法修改共享引用 in-place。）

如所写，该调用将被复制。基于对字符串的引用处理的简单检查，这是可以预测的；问题是旧版本的字符串保留在 puzzle 中，直到 string replace 完成（set 需要结果才能工作）。为了解决这个问题，我们做了一件有点奇怪的事情：

set puzzle [string replace $puzzle[set puzzle {}] $index $index "E"]

是的，这 很奇怪 但它工作得很好，因为与 known-empty 字符串的连接是一个明确优化的情况，假设您在这里处理未跟踪的变量。（它适用于跟踪变量，但可以观察到双重写入，并且跟踪可能会做一些棘手的事情，因此您会失去优化机会。）

如果您进行大量更改，有时会改变内容的长度，切换到使用列表和 lset 会更有效。列表上的等效操作都使用相同的通用引用和 in-place 语义，但作用于列表元素而不是字符。

反汇编

我说的优化是在 strcat 操作码中，strreplace 知道在可以的时候做 in-place 但你看不到字节码中的信息等级;几乎所有操作都知道这一点。

% tcl::unsupported::disassemble lambda {{puzzle index} {
    set puzzle [string replace $puzzle[set puzzle {}] $index $index "E"]
}}
ByteCode 0x0x7fbff6021c10, refCt 1, epoch 17, interp 0x0x7fbff481e010 (epoch 17)
  Source "\n    set puzzle [string replace $puzzle[set puzzle {}]..."
  Cmds 3, src 74, inst 18, litObjs 2, aux 0, stkDepth 4, code/src 0.00
  Proc 0x0x7fbff601cc90, refCt 1, args 2, compiled locals 2
      slot 0, scalar, arg, "puzzle"
      slot 1, scalar, arg, "index"
  Commands 3:
      1: pc 0-16, src 5-72        2: pc 0-14, src 17-71
      3: pc 2-5, src 40-52
  Command 1: "set puzzle [string replace $puzzle[set puzzle {}] $inde..."
  Command 2: "string replace $puzzle[set puzzle {}] $index $index \"E..."
    (0) loadScalar1 %v0     # var "puzzle"
  Command 3: "set puzzle {}..."
    (2) push1 0     # ""
    (4) storeScalar1 %v0    # var "puzzle"
    (6) strcat 2 
    (8) loadScalar1 %v1     # var "index"
    (10) loadScalar1 %v1    # var "index"
    (12) push1 1    # "E"
    (14) strreplace 
    (15) storeScalar1 %v0   # var "puzzle"
    (17) done

快速字符串替换

Fast string replace

tcl

反汇编