Karmaşık Dize Karşılaştırmalar

4 Cevap

Ben (needle) dizelerden oluşan bir dizi alır ve dizeleri başka bir dizi karşı bir karşılaştırma gerçekleştirir PHP bir fonksiyon yazmaya çalışıyorum (haystack). Bu fonksiyonun amacı hızlı bir AJAX arama dizelerini eşleşen teslim etmektir, bu nedenle mümkün olduğunca hızlı olması gerekir.

İşte iki diziyi göstermek için bazı örnek kod;

$needle = array('ba','hot','resta');

$haystack = array(
    'Southern Hotel',
    'Grange Restaurant & Hotel',
    'Austral Hotel',
    'Barsmith Hotel',
    'Errestas'
);

Bu kendi içinde oldukça kolay iken, karşılaştırma amacı haystack görünen kaç needle dizeleri saymak etmektir.

Ancak, üç kısıtlamalar vardır;

  1. Karşılaştırma harf duyarsız
  2. The needle must only match characters at the beginning of the word. For example, "hote" will match "Hotel", but "resta" will not match "Errestas".
  3. Biz eşleştirme needles sayısını değil, needle maçta sayı saymak istiyorum. Bir yer "Otel Hotel" adlı, biz olması sonucu gerek 1 değil 3.

Yukarıdaki örneği kullanarak, biz bir sonucu olarak şu ilişkisel dizi beklersiniz:

$haystack = array(
    'Southern Hotel' => 1,
    'Grange Restaurant & Hotel' => 2,
    'Austral Hotel' => 1,
    'Barsmith Hotel' => 2,
    'Erresta'  => 0
);

Ben bir preg_match_all() kullanarak, bunu yapmak için bir fonksiyonu uygulamak için çalışıyor ve /(\A|\s)(ba|hot|resta)/ gibi görünen bir sıradanifade oldum. Bu sadece kelimelerin başında maç sağlar iken, iki kez aynı needle içeren hesap dizeleri içine almaz.

Ben başkası bir çözüm olup olmadığını görmek için ilanıyla?

4 Cevap

Ben bunu çözmek için bir TDD yaklaşım olabilir yeterince ayrıntılı sorunun açıklaması tespit ettik. Ben çok bir TDD adam olmaya çalışıyorum çünkü Yani, ben testleri ve testleri geçmek için işlevini yazdı ettik. Adlandırmaları mükemmel olmayabilir, ama onlar kolayca değiştirilebilir demektir. Fonksiyonunun algoritması da iyi olmayabilir, ama şimdi testler vardır ki, üstlenmeden çok kolay ve ağrısız olması gerekir.

Here are the tests:

class MultiMatcherTest extends PHPUnit_Framework_TestCase
{
    public function testTheComparisonIsCaseInsensitive()
    {
        $needles  = array('hot');
        $haystack = array('Southern Hotel');
        $result   = match($needles, $haystack);

        $this->assertEquals(array('Southern Hotel' => 1), $result);
    }

    public function testNeedleMatchesOnlyCharsAtBeginningOfWord()
    {
        $needles  = array('resta');
        $haystack = array('Errestas');
        $result   = match($needles, $haystack);

        $this->assertEquals(array('Errestas' => 0), $result);
    }

    public function testMatcherCountsNeedlesNotOccurences()
    {
        $needles  = array('hot');
        $haystack = array('Southern Hotel', 'Grange Restaurant & Hotel');
        $expected = array('Southern Hotel'            => 1,
                          'Grange Restaurant & Hotel' => 1);
        $result   = match($needles, $haystack);

        $this->assertEquals($expected, $result);
    }

    public function testAcceptance()
    {
        $needles  = array('ba','hot','resta');
        $haystack = array(
            'Southern Hotel',
            'Grange Restaurant & Hotel',
            'Austral Hotel',
            'Barsmith Hotel',
            'Errestas',
        );
        $expected = array(
            'Southern Hotel'            => 1,
            'Grange Restaurant & Hotel' => 2,
            'Austral Hotel'             => 1,
            'Barsmith Hotel'            => 2,
            'Errestas'                  => 0,
        );

        $result = match($needles, $haystack);

        $this->assertEquals($expected, $result);
    }
}


And here's the function:

function match($needles, $haystack)
{
    // The default result will containg 0 (zero) occurences for all $haystacks
    $result = array_combine($haystack, array_fill(0, count($haystack), 0));

    foreach ($needles as $needle) {

        foreach ($haystack as $subject) {
            $words = str_word_count($subject, 1); // split into words

            foreach ($words as $word) {
                if (stripos($word, $needle) === 0) {
                    $result[$subject]++;

                    break;
                }
            }
        }
    }

    return $result;
}


Testing that the break statement is necessary

break, gerektiğinde aşağıdaki test gösterir. Ve match fonksiyon içerisinde bir break deyimi olmadan hem de bu testi çalıştırın.

/**
 * This test demonstrates the purpose of the BREAK statement in the
 * implementation function. Without it, the needle will be matched twice.
 * "hot" will be matched for each "Hotel" word.
 */
public function testMatcherCountsNeedlesNotOccurences2()
{
    $needles  = array('hot');
    $haystack = array('Southern Hotel Hotel');
    $expected = array('Southern Hotel Hotel' => 1);
    $result   = match($needles, $haystack);

    $this->assertEquals($expected, $result);
}

dizi ve string fonksiyonları regexplerde daha büyüklükleri tarafından genellikle daha hızlı. Bu array_filter ve substr_count kombinasyonu ile ne istediğinizi yapmak oldukça kolay olmalıdır.

Alkış,

@ Ionut G. Stan vay, ne bir cevap!

@Lachlan McDonald If you have speed concerns (try it first, not just assume:) ) you can use that the needle should match the beginning of the string: splitting the haystack during the build process by the first letter and iterate only the haystack array matching the first char of the needle.

Bu iğne başına 1/10th karşılaştırmaları daha az yapacak.

Eğer deneyebilirsiniz:

$results=Array();
foreach ($haystack as $stack) {
 $counter=0;
 $lcstack=strtolower($stack);
 foreach ($needle as $need) {
  if (substr($lcstack,0,strlen($need))==strtolower($need)) {
   $counter++;
  }
 }
 $results[$stack]=$counter;
}

etiketler