Python：高效的多字符串替换

Question

这个功能可以提高效率吗？我需要处理一百万个名字...

def indian_soundex_encode(s):
    s = s.replace("aa", "a")
    s = s.replace("ee", "i")
    s = s.replace("zh", "l")
    s = s.replace("oo", "u")
    s = s.replace("bu", "b")
    s = s.replace("dh", "d")
    s = s.replace("gh", "g")
    s = s.replace("jh", "j")
    s = s.replace("kh", "k")
    s = s.replace("sh", "s")
    s = s.replace("th", "t")
    s = s.replace("ck", "k")
    s = s.replace("kk", "k")
    s = s.replace("nn", "n")
    s = s.replace("mm", "m")
    s = s.replace("pp", "p")
    s = s.replace("ll", "l")
    s = s.replace("ty", "ti")
    s = s.replace("ot", "od")
    s = s.replace("iya", "ia")
    s = s.replace("ya", "ia")
    s = s.replace("sv", "s")
    s = s.replace("sw", "s")
    s = s.replace("my", "mi")
    return s

Answer 1

使用纯 Python 很难提高函数的效率。 str.replace 已经相当高效了，但它确实需要多次扫描字符串，并且至少在某些情况下需要创建几个新字符串。用只扫描字符串一次的更智能算法替换对 replace 的多次调用，可能会使函数变慢，因为您将在纯 Python 中做更多工作并放弃 [= 的原始效率11=].

如果您可以编写 C 扩展模块，我建议您这样做。使用 timeit 进行测量，对于示例字符串 "foobaaar".[=18，以下函数的性能优于原始函数约 17 倍（0.184 usec 与 Python 版本的 3.28 usec 相比） =]

PyObject *
indian_soundex_encode(PyObject *ignore, PyObject *args)
{
  PyObject *py_s, *py_ret;
  bool replaced = false;
  if (!PyArg_ParseTuple(args, "S", &py_s))
    return NULL;

  const char *s = PyString_AS_STRING(py_s);
  Py_ssize_t len = PyString_GET_SIZE(py_s);
  char *ret = malloc(len + 1), *retptr = ret;
  if (!ret)
    return PyErr_NoMemory();

  while (len > 0) {
#define REPLACE(first, second, replacement)     \
    if (*s == first && *(s + 1) == second) {    \
      s += 2;                                   \
      len -= 2;                                 \
      *retptr++ = replacement;                  \
      replaced = true;                          \
      continue;                                 \
    }

    REPLACE('a', 'a', 'a');
    REPLACE('e', 'e', 'i');
    REPLACE('z', 'h', 'l');
    REPLACE('o', 'o', 'u');
    REPLACE('b', 'u', 'b');
    REPLACE('d', 'h', 'd');
    REPLACE('g', 'h', 'g');
    REPLACE('j', 'h', 'j');
    REPLACE('k', 'h', 'k');
    REPLACE('s', 'h', 's');
    REPLACE('t', 'h', 't');
    REPLACE('c', 'k', 'k');
    REPLACE('k', 'k', 'k');
    REPLACE('n', 'n', 'n');

#undef REPLACE
    *retptr++ = *s++;
    --len;
  }
  if (!replaced) {
    py_ret = py_s;
    Py_INCREF(py_ret);
  }
  else
    py_ret = PyString_FromStringAndSize(ret, retptr - ret);
  free(ret);
  return py_ret;
}

使用 switch 语句或用 C 编码的更高效的查找表可能会进一步加快上述功能，但这留作 reader 的练习。

尝试在 Cython 中编写此函数的一个版本，并将其性能与上述手写 C 扩展进行比较，这将是另一个有趣的练习。

更新： 上述C函数对应题中原Python代码。编辑 Jost 悄悄地进行了一次主要的代码更改以及格式更改 in his edit，这显然没有被审阅者发现。

Python：高效的多字符串替换

Python: efficient multi-string replace

python

replace

soundex