0

Can this function be made more efficient? I need to process a million names...

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
4

1 回答 1

4

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

如果在您的情况下可以编写 C 扩展模块，我建议您这样做。使用 测量timeit，对于示例字符串 ，以下函数的性能比原始函数高约 17 倍（Python 版本为 0.184 微秒，而 Python 版本为 3.28 微秒）"foobaaar"。

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 语言编写的语句甚至更高效的查找表可能会进一步加快上述函数的速度，但这留给读者作为练习。

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

更新：上面的 C 函数对应于问题中的原始 Python 代码。编辑 Jost在他的编辑中偷偷地进行了一次重大的代码更改以及格式更改，这显然没有被审阅者发现。

于 2015-03-08T19:38:54.867 回答