Il modo più veloce per abbinare i prefissi telefonici utilizzando uno script PHP asterisco

StackOverflow https://stackoverflow.com/questions/1489487

Domanda

e grazie in anticipo per l'aiuto.

Sfondo - Sto scrivendo uno script PHP che ha bisogno di capire la destinazione che il chiamante sta cercando di raggiungere. prefissi di telefonia sono stringhe che identificano una destinazione. Per ogni chiamata, il programma deve trovare il prefisso più lungo che corrisponde alla stringa. Ad esempio, il numero 30561234567 sarebbe stato accompagnato da 305 ma non da 3057 o 304. Se esistesse 3056 sarebbe la partita preferita.

Dopo aver esaminato diverse strutture dati, un albero in cui ogni nodo memorizza una cifra e contiene puntatori alle altre 10 scelte possibili sembra l'ideale. Ciò può essere implementato come un array di array, dove lo script può controllare 3, per un array, allora controlli 0 su quel nuovo array, per un altro array e così via fino a trovare un valore invece di un array. Questo valore potrebbe essere l'id di destinazione (l'output dello script).

Requisiti - Le prestazioni sono assolutamente critica. Il tempo trascorso controllando questi prefissi ritarda la chiamata, e ogni server deve gestire grandi quantità di chiamate, in modo che la struttura dei dati devono essere memorizzati nella memoria. Ci sono circa 6000 prefissi in questo momento.

problema - Lo script viene eseguito ogni volta che il server riceve una chiamata, in modo che i dati devono essere tenuto in un server cache di qualche tipo. Dopo aver controllato memcached e APC (Advanced PHP Cache), ho deciso di utilizzare APC perché è [molto più veloce] [3] (si tratta di un negozio di memoria locale)

Il problema che ho è che l'array di array può diventare fino a 10 array profondo, e sarà una struttura dati molto complicato, se aggiungo alla cache come oggetto, avrà molto tempo per deserializzare .

Tuttavia, se aggiungo ogni singolo array alla cache separatamente (con una certa struttura di denominazione logica per essere in grado di trovare facilmente come 3 per il campo 3, poi 30 per serie 30, 305 per l'array che segue quella patch, ecc .. .) dovrò recuperare le matrici diverse dalla cache più volte (fino a 10 per ogni chiamata), rendendo mi ha colpito la cache troppo spesso.

Sto andando su questo nel modo giusto? Forse c'è un'altra soluzione? O è uno dei metodi che ho proposto superiore all'altro?

Grazie per aver inserito,

Alex

È stato utile?

Soluzione

Ecco alcuni esempi di codice per una struttura ad albero n-ario; 

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);
 }
}

questo può quindi essere definito come 

$pre = new PrefixCache();

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

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

che esegue come richiesto (restituisce 305, se 3056 è commentata, restituisce 3056 invece)

.

Si noti che aggiungo un terminale-flag per ogni nodo; questo evita false corrispondenze parziali, vale a dire se si aggiunge il prefisso 3.056.124 sarà adeguatamente corrispondere 3056 invece di restituire 305.612.

Il modo migliore per evitare ricaricando ogni volta è di trasformarlo in un servizio; Tuttavia, prima di farlo vorrei misurare run-volte con APC. Può anche essere abbastanza veloce come è.

Alex: la risposta è assolutamente corretto - ma non applicabile a questa domanda:)

Altri suggerimenti

Il mio modo di vedere, utilizzando una semplice struttura a matrice dovrebbe funzionare bene ...

Codice del campione: (notare che per le prestazioni dei prefissi sono le chiavi nella matrice, non valori) 

// $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;
}

Un altro modo sarebbe quello di interrogare la cache direttamente il numero - in questo caso, potrebbe essere ulteriormente ottimizzato:

  1. stringa di numero dividere in 2.
  2. interrogare quella stringa nella cache.
  3. se non esiste, goto 1
  4. mentre esiste, memorizzare tale valore come risultato, e aggiungere un'altra cifra.

Snippet: (si noti che query_cache_for () dovrebbe essere sostituito da qualsiasi funzione il meccanismo di caching utilizza) 

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;
}

Questo approccio ha il vantaggio ovvio che ogni prefisso è un singolo elemento nella cache - la chiave potrebbe essere 'asterix_prefix_ ' per esempio, il valore è irrilevante (1 opere)

.

Dal momento che si sta lavorando solo con i numeri, forse lavorando direttamente con le stringhe è inefficiente.

Si potrebbe eseguire un algoritmo di ricerca binaria. Se si memorizzano tutti i prefissi (numericamente), imbottito per 15 posti e poi in ordine, è possibile eseguire la scansione di codici 6000 in circa il log2 (6000) ~ = 13 gradini.

Per esempio, se si hanno i seguenti codici:

  • 01, 0127, 01273, 0809, 08

Si potrebbe memorizzare le seguenti in un array:

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

I passi sarebbero:

  1. Striscia numero in entrata fino a 15 posti.
  2. Esegui ricerca binaria per trovare il codice più basso più vicino (ed è indice nella matrice sopra)
  3. Cercare la lunghezza del codice in un array separato (usando l'indice)

Alcuni codice di esempio per vedere in azione: 

// 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]);
    }
}

Lo faccio utilizzando una tabella hash di corda, destinazione in cui le chiavi sono stringhe che rappresentano il prefisso della destinazione. Il fattore critico è che la tabella hash deve essere ordinato in modo che le stringhe più lunghe vengono controllati prima. Non appena viene trovata una corrispondenza di prefisso è nota la destinazione della chiamata.

Mi hanno fatto anche un giro di espressioni regolari che per le destinazioni più contorto e controllare le espressioni regolari prima i prefissi di destinazione.

Non ho misurato quanto tempo ci vuole per ottenere una partita, ma ho il sospetto 15ms max. L'intero processo di verifica della desitnation e quindi l'equilibrio dell'utente e, infine, la fissazione di un limite di tempo di chiamata dura circa 150ms. Nel mio caso io sto usando il servizio FastAGI e C # di Windows. Finché si prende meno di 500 ms sarà impercetible per gli utenti.

Ho anche eseguire un'applicazione di telefonia ... quello che ho fatto è prevista un'API REST interna per chiamare, questo è ciò che i numeri di telefono nella cache noti e fare tutto il controllo prefisso.

Anche io presumo che siete alla ricerca di codici di paese pure. Ci sono solo pochi sovrapposti codici di paese con il NANP. Così guardo prima per un NANP, e fare una partita veloce sul numero dei seguenti numeri (7) per assicurarsi che, altrimenti cado di nuovo su un codice di paese. Ho poi ho una una vaga idea di quanti numeri in un numero di telefono si suppone ogni paese di avere attraverso un'espressione regolare.

sto usando un documento XML e la corrispondenza su XPath, quindi la memorizzazione nella cache il risultato XPath quando possibile.

La cosa più cool utilizzando un API REST così, è che può essere usato per pulire i numeri prima di riporli in DB per la fatturazione.

Non è una scienza esatta, ma sembra funzionare.

Trovare la più lunga sottosequenza comune è un'applicazione classica di programmazione dinamica. La soluzione è O (n). http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top