Подсчитайте, сколько раз два элемента массива встречаются близко друг к другу

Question

У меня есть огромный массив слов. Я хочу подсчитать, сколько раз два конкретных слова встречаются меньше определенного расстояния.

Например, если расстояние между «временем» и «поздним» составляет не более трех слов, то я хочу увеличить счетчик. Слова «время» и «поздний» могут появляться сотни раз в массиве. Как я могу найти количество времени, которое они встречаются рядом друг с другом?

Answer 1

Вы не задавали вопрос, поэтому я предполагаю, что вы придумали алгоритм.

1. Итерации через индексы.
   1. Если первое слово найдено по этому индексу,
      1. Обратите внимание, что индекс.
   2. Если второе слово найдено по этому индексу,
      1. Обратите внимание, что индекс.
2. Вычесть один индекс от другого.

Примечание:

• Вы можете добавить проверку, чтобы убедиться, что каждое слово было найдено.
• Вы не указали, что должно произойти, когда одно из слов встречается более одного раза.

---

На вопрос заданный в комментариях:

1. Итерация по индексам.
   1. Если первое слово найдено по этому индексу,
      1. Обратите внимание, что индекс.
   2. Если второе слово найдено по этому индексу,
      1. Если разница между текущим индексом и отмеченного индекса ≤ 3,
         1. Приращение счетчика.

Примечание:

• Предполагает вы заботитесь только о расстоянии между вторым словом и предыдущих экземпляром первого слова.

Answer 2

Использование индекса хэш будет вполне эффективным решением:

my @words = qw(word1 word2 word3 word4 word5 word6); 

# That can be expensive, but you do it only once 
my %index; 
@index{@words} = (0..$#words); 

# That will be real quick 
my $distance = $index{"word6"} - $index{"word2"} 
print "Distance: $distance \n"; 

Выход скрипта выше будет:

Distance: 4 

Примечание: создание индекса хэш может быть дорогим. Но если вы планируете делать много дистанционных проверок, это может стоить того, поскольку любой поиск выполняется быстро (постоянное время, а не журнал событий (n)).

Answer 3

Нужно ли поддерживать дублирующиеся слова?

#! /usr/bin/perl 
use strict; 
use warnings; 
use constant DEBUG => 0; 

my @words; 
if($ARGV[0] && -f $ARGV[0]) { 
    open my $fh, "<", $ARGV[0] or die "Could not read $ARGV[0], because: $!\n"; 
    my $hughTestFile = do { local $/; <$fh> }; 
    @words = split /[\s\n]/, $hughTestFile; # $#words == 10M words with my test.log 
    # Test words (below) were manually placed at equal distances (~every 900K words) in test.log 
    # With above, TESTS ran in avg of 15 seconds. Likely test.log was in buffers/cache. 
} else { 
    @words = qw(word1 word2 word3 word4 word5 word6 word7 word8 word4 word9 word0); 
} 

sub IndexOf { 
    my $searchFor = shift; 
    return undef if(!$searchFor); 
    my $Nth = shift || 1; 

    my $length = $#words; 
    my $cntr = 0; 
    for my $word (@words) { 
     if($word eq $searchFor) { 
      $Nth--; 
      return $cntr if($Nth == 0); 
     } 
     $cntr++; 
    } 
    return undef; 
} 

sub Distance { 
# args: <1st word>, <2nd word>, [occurrence_of_1st_word], [occurrence_of_2nd_word] 
# for occurrence counts: 0, 1 & undef - all have the same effect (1st occurrence) 
    my($w1, $w2) = ($_[0], $_[1]); 
    my($n1, $n2) = ($_[2] || undef, $_[3] || undef); 
    die "Missing words\n" if(!$w1); 
    $w2 = $w1 if(!$w2); 

    my($i1, $i2) = (IndexOf($w1, $n1), IndexOf($w2, $n2)); 
    if(defined($i1) && defined($i2)) { 
     my $offset = $i1-$i2; 
     print " Distance (offset) = $offset\n"; 
     return undef; 
    } elsif(!defined($i1) && !defined($i2)) { 
     print " Neither words were "; 
    } elsif(!defined($i1)) { 
     print " First word was not "; 
    } else { 
     print " Second word was not "; 
    } 
    print "found in list\n"; 

    return undef; 
} 

# TESTS 
print "Your array has ".$#words." words\n"; 
print "When 1st word is AFTER 2nd word:\n"; 
Distance("word7", "word3"); 
print "When 1st word is BEFORE 2nd word:\n"; 
Distance("word2", "word5"); 
print "When 1st word == 2nd word:\n"; 
Distance("word4", "word4"); 
print "When 1st word doesn't exist:\n"; 
Distance("word00", "word6"); 
print "When 2nd word doesn't exist:\n"; 
Distance("word1", "word99"); 
print "When neither 1st or 2nd words exist:\n"; 
Distance("word00", "word99"); 
print "When the 1st word is AFTER the 2nd OCCURRENCE of 2nd word:\n"; 
Distance("word9", "word4", 0, 2); 
print "When the 1st word is BEFORE the 2nd OCCURRENCE of the 2nd word:\n"; 
Distance("word7", "word4", 1, 2); 
print "When the 2nd OCCURRENCE of the 2nd word doesn't exist:\n"; 
Distance("word7", "word99", 0, 2); 
print "When the 2nd OCCURRENCE of the 1st word is AFTER the 2nd word:\n"; 
Distance("word4", "word2", 2, 0); 
print "When the 2nd OCCURRENCE of the 1st word is BEFORE the 2nd word:\n"; 
Distance("word4", "word0", 2, 0); 
print "When the 2nd OCCURRENCE of the 1st word exists, but 2nd doesn't:\n"; 
Distance("word4", "word99", 2, 0); 
print "When neither of the 2nd OCCURRENCES of the words exist:\n"; 
Distance("word00", "word99", 2, 2); 
print "Distance between 2nd and 1st OCCURRENCES of the same word:\n"; 
Distance("word4", "", 2, 1);