php - 使用 Asterisk PHP 脚本匹配电话前缀的最快方法

Question

提前感谢您的帮助。

背景 - 我正在编写一个 PHP 脚本，需要弄清楚调用者试图到达的目的地。电话前缀是标识目的地的字符串。对于每次调用，程序必须找到与字符串匹配的最长前缀。例如，数字 30561234567 将与 305 匹配，但不会与 3057 或 304 匹配。如果 3056 存在，它将是首选匹配项。

在研究了几种数据结构之后，每个节点都存储一个数字并包含指向其他 10 个可能选择的指针的树似乎是理想的。这可以实现为一个数组数组，其中脚本可以检查 3，在那里找到一个数组，然后检查那个新数组上的 0，找到另一个数组等等，直到它找到一个值而不是一个数组。该值将是目标 ID(脚本的输出)。

要求 - 性能绝对至关重要。花在检查这些前缀上的时间延迟了调用，每个服务器都要处理大量的调用，所以数据结构必须存储在内存中。目前大约有 6000 个前缀。

问题 - 每次服务器收到调用时都会运行该脚本，因此数据必须保存在某种缓存服务器中。在检查了 memcached 和 APC(高级 PHP 缓存)之后，我决定使用 APC，因为它 [快得多][3](它是本地内存存储)

我遇到的问题是，数组的数组可以达到 10 个数组的深度，并且将是一个非常复杂的数据结构，如果我将其作为对象添加到缓存中，将需要很长时间才能反序列化.

但是，如果我将每个数组分别添加到缓存中(使用一些逻辑命名结构可以轻松找到它，例如 3 表示数组 3，然后 30 表示数组 30，305 表示该补丁后面的数组等。 .) 我将不得不多次从缓存中获取不同的数组(每次调用最多 10 个)，这让我经常访问缓存。

我的做法是否正确？也许还有另一种解决方案？或者我提出的其中一种方法优于另一种方法？

感谢您的参与，

亚历克斯

Answer 1

下面是一些 N 叉树结构的示例代码；

class PrefixCache {
 const EOS = 'eos';
 protected $data;

 function __construct() {
  $this->data = array();
  $this->data[self::EOS] = false;
 }

 function addPrefix($str) {
  $str = (string) $str;
  $len = strlen($str);

  for ($i=0, $t =& $this->data; $i<$len; ++$i) {
   $ch = $str[$i];

   if (!isset($t[$ch])) {
    $t[$ch] = array();
    $t[$ch][self::EOS] = false;
   }

   $t =& $t[$ch];
  }

  $t[self::EOS] = true;
 }

 function matchPrefix($str) {
  $str = (string) $str;
  $len = strlen($str);

  $so_far = '';
  $best = '';

  for ($i=0, $t =& $this->data; $i<$len; ++$i) {
   $ch = $str[$i];

   if (!isset($t[$ch]))
    return $best;
   else {
    $so_far .= $ch;
    if ($t[$ch][self::EOS])
     $best = $so_far;

    $t =& $t[$ch];     
   }
  }

  return false; // string not long enough - potential longer matches remain
 }

 function dump() {
  print_r($this->data);
 }
}

这可以称为

$pre = new PrefixCache();

$pre->addPrefix('304');
$pre->addPrefix('305');
// $pre->addPrefix('3056');
$pre->addPrefix('3057');

echo $pre->matchPrefix('30561234567');

按要求执行(返回 305；如果 3056 未注释，则返回 3056)。

请注意，我为每个节点添加了一个终端标志；这避免了错误的部分匹配，即如果您添加前缀 3056124，它将正确匹配 3056 而不是返回 305612。

避免每次都重新加载的最好方法是把它变成一个服务；然而，在这样做之前，我会用 APC 测量运行时间。它可能已经足够快了。

Alex:你的回答绝对正确——但不适用于这个问题:)