6

助けてくれてありがとう。

背景- 呼び出し元が到達しようとしている宛先を把握する必要がある PHP スクリプトを作成しています。テレフォニー プレフィックスは、宛先を識別する文字列です。呼び出しごとに、プログラムは文字列に一致する最長のプレフィックスを見つける必要があります。たとえば、番号 30561234567 は 305 と一致しますが、3057 または 304 とは一致しません。3056 が存在する場合、それが優先一致となります。

いくつかのデータ構造を調査した結果、各ノードが数字を格納し、他の 10 個の可能な選択肢へのポインターを含むツリーが理想的であると思われます。これは配列の配列として実装できます。スクリプトは 3 をチェックし、そこで配列を見つけ、次にその新しい配列で 0 をチェックし、別の配列を見つけ、配列ではなく値が見つかるまで繰り返します。この値は宛先 ID (スクリプトの出力) になります。

要件- パフォーマンスは非常に重要です。これらのプレフィックスのチェックに時間がかかると呼び出しが遅延し、各サーバーは大量の呼び出しを処理する必要があるため、データ構造をメモリに格納する必要があります。現在、約 6000 のプレフィックスがあります。

問題- サーバーが呼び出しを受信するたびにスクリプトが実行されるため、データを何らかのキャッシュ サーバーに保持する必要があります。memcached と APC (Advanced PHP Cache) を確認した後、[はるかに高速][3] (ローカル メモリ ストア) であるため、APC を使用することにしました。

私が抱えている問題は、配列の配列が最大 10 配列の深さになる可能性があり、非常に複雑なデータ構造になり、オブジェクトとしてキャッシュに追加すると、逆シリアル化に長い時間がかかることです。

ただし、すべての配列を個別にキャッシュに追加すると (配列 3 の場合は 3、配列 30 の場合は 30、そのパッチに続く配列の場合は 305 などのように、簡単に見つけられる論理命名構造を使用して...) 私はキャッシュからさまざまな配列を何度もフェッチする必要があり (呼び出しごとに最大 10 個)、キャッシュにヒットする頻度が高くなりすぎます。

私はこれを正しい方法で行っていますか？多分別の解決策がありますか？それとも、私が提案した方法の 1 つが他の方法よりも優れているのでしょうか?

ご入力いただきありがとうございます。

アレックス

4

6 に答える 6

2

N-aryツリー構造のサンプルコードを次に示します。

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を追加すると、305612を返す代わりに3056と適切に一致します。

毎回リロードを回避する最善の方法は、サービスをサービスに変えることです。ただし、そうする前に、APCを使用して実行時間を測定します。そのままでも十分速いかもしれません。

アレックス：あなたの答えは絶対に正しいですが、この質問には当てはまりません:)

于 2009-09-28T23:35:33.223 に答える
2

私の見方では、単純な配列構造を使用しても問題なく動作するはずです...

サンプル コード: (パフォーマンスのために、プレフィックスは値ではなく配列内のキーであることに注意してください)

// $prefixes = array(3=>1, 30=>1, 304=>1,305=>1,3056=>1,306=>1,31=>1, 40=>1);

function matchNumber($number)
{
  $prefixes = getPrefixesFromCache();

  $number = "$number";
  // try to find the longest prefix matching $number
  while ($number != '') {
    if (isset($keys[$number]))
      break;
    // not found yet, subtract last digit
    $number = substr($number, 0, -1);
  }
  return $number;
}

もう 1 つの方法は、キャッシュに数値を直接問い合わせることです。この場合、さらに最適化することができます。

  1. 数値文字列を 2 つに分割します。
  2. キャッシュ内のその文字列を照会します。
  3. 存在しない場合は 1 へ
  4. 存在する間、その値を結果として保存し、別の数字を追加します。

スニペット: (query_cache_for() は、キャッシング メカニズムが使用する関数に置き換える必要があることに注意してください)

function matchNumber($number)
{
  $temp = "$number";
  $found = false;
  while (1) {
    $temp = substr($temp, 0, ceil(strlen($temp)/2) );
    $found = query_cache_for($temp);
    if ($found)
      break;
    if (strlen($temp) == 1)
      return FALSE; // should not happen!
  }
  while ($found) {
    $result = $temp;
    // add another digit
    $temp .= substr($number, strlen($temp), 1);
    $found = query_cache_for($temp);
  }
  return $result;
}

このアプローチには、各プレフィックスがキャッシュ内の単一の要素であるという明らかな利点があります。たとえば、キーは 'asterix_prefix_<number>' である可能性があり、値は重要ではありません (1 が機能します)。

于 2009-09-28T22:32:52.570 に答える
1

数値のみを操作しているため、文字列を直接操作するのは非効率的かもしれません。

二分探索アルゴリズムを実行できます。すべてのプレフィックスを（数値で）保存し、15の場所にパディングしてから順番に保存すると、約log2（6000）〜=13ステップで6000コードをスキャンできます。

たとえば、次のコードがある場合：

  • 01、0127、01273、0809、08

以下を配列に格納します。

  1. 010000000000000
  2. 012700000000000
  3. 012730000000000
  4. 080000000000000
  5. 080900000000000

手順は次のとおりです。

  1. 着信番号を15か所まで削除します。
  2. バイナリ検索を実行して、最も近い最も低いコード（および上の配列のインデックス）を見つけます
  3. 別の配列でコードの長さを検索します（インデックスを使用）

実際の動作を確認するためのサンプルコード：

// Example for prefixes 0100,01,012,0127,0200
$prefixes = array('0100','0101','0120','0127','0200');
$prefix_lengths = array(4,2,3,4,4);
$longest_length_prefix = 4;

echo GetPrefix('01003508163');

function GetPrefix($number_to_check) {
    global $prefixes;
    global $prefix_lengths;
    global $longest_length_prefix;

    $stripped_number = substr($number_to_check, 0, $longest_length_prefix);

    // Binary search
    $window_floor = 0;
    $window_ceiling = count($prefixes)-1;
    $prefix_index = -1;

    do {
        $mid_point = ($window_floor+$window_ceiling)>>1;

        if ($window_floor==($window_ceiling-1)) {
            if ($stripped_number>=$prefixes[$window_ceiling]) {
                $prefix_index=$window_ceiling;
                break;
            } elseif ($stripped_number>=$prefixes[$window_floor]) {
                $prefix_index=$window_floor;
                break;
            } else {
                break;
            }
        } else {
            if ($stripped_number==$prefixes[$mid_point]) {
                $prefix_index=$mid_point;
                break;
            } elseif ($stripped_number<$prefixes[$mid_point]) {
                $window_ceiling=$mid_point;
            } else {
                $window_floor=$mid_point;
            }
        }
    } while (true);

    if ($prefix_index==-1 || substr($number_to_check, 0, $prefix_lengths[$prefix_index])!=substr($prefixes[$prefix_index],0, $prefix_lengths[$prefix_index])) {
        return 'invalid prefix';
    } else {
        return substr($prefixes[$prefix_index], 0, $prefix_lengths[$prefix_index]);
    }
}
于 2009-09-29T11:59:11.683 に答える
0

最長共通部分列を見つけることは、動的計画法の古典的なアプリケーションです。解はO（n）です。http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

于 2009-09-28T22:52:49.970 に答える
0

電話アプリケーションも実行しています...私が行ったことは、呼び出すための内部 REST API を提供することでした。これは、既知の電話番号をキャッシュし、すべてのプレフィックス チェックを行うものです。

また、国コードも探していると思います。NANP と重複する国コードはわずかです。そのため、最初に NANP を探し、次の数字 (7) の数を簡単に照合して確認します。そうでない場合は、国コードに頼ります。次に、正規表現を使用して、各国の電話番号の数を大まかに把握します。

XML ドキュメントを使用して XPath で照合し、可能な場合は XPath の結果をキャッシュしています。

REST API を使用することの優れた点は、請求のために DB に格納する前に数値をクリーンアップするために使用できることです。

それは正確な科学ではありませんが、うまくいくようです。

于 2009-09-28T21:55:42.800 に答える
0

キーが宛先のプレフィックスを表す文字列である、文字列、宛先のハッシュテーブルを使用してそれを行います。重要な要素は、最も長い文字列が最初にチェックされるように、ハッシュ テーブルを並べ替える必要があることです。一致するプレフィックスが見つかるとすぐに、呼び出し先がわかります。

私は実際には、より複雑な宛先のために、宛先プレフィックスの前に正規表現をチェックする一連の正規表現も持っています。

一致するまでの時間を測定したことはありませんが、最大 15 ミリ秒だと思います。宛先を確認し、次にユーザーの残高を確認し、最後に通話時間制限を設定するプロセス全体に約 150 ミリ秒かかります。私の場合、FastAGI と C# Windows サービスを使用しています。500 ミリ秒未満である限り、ユーザーには認識されません。

于 2009-09-28T21:44:49.503 に答える