Perl. Библиотека программиста

Представление отношений между данными

Проблема

Требуется представить отношения между данными — например, отношенш «предок/потомок» в генеалогическом дереве или «родительский/порожденный процесс» в таблице процессов. Задача тесно связана с представлением таблиц в реляционных базах данных (отношения между записями) и графов в компьютерных технологиях (отношения между узлами графа).

Решение

Воспользуйтесь хэшем.

Комментарий

Следующий хэш представляет часть генеалогического дерева из Библии:

%father =('Cain'	=> 'Adam',
          'Abel'	=> 'Adam',
          'Seth'	=> 'Adam',
          'Enoch'	=> 'Cain',
          'Irad'	=> 'Enoch',
          'Mehujael'	=> 'Irad',
          'Methusael'	=> 'Mehujael',
          'Lamech'	=> 'Methusael’,
          'jabal'	=> 'Lamech’,
          'Jubal'	=> 'Lamech',
          'Tubalcain'	=> 'Lamech',
          'Enos'	=> 'Seth');

Например, мы можем легко построить генеалогическое дерево любого персонажа:

while (<>) {
  chomp;
  do {
    print "$_";                 # Вывести текущее имя
    $_ = $father{$_};           # Присвоить $_ отца $_
  } while defined;              # Пока отцы находятся
  print "\n";
}

Просматривая хэш %father, можно отвечать на вопросы типа: «Кто родил Сета?» При инвертировании хэша отношение заменяется противоположным. Это позволяет дать ответ на вопросы типа: «Кого родил Ламех?»

while ( ($k, $v) = each %father ) {
  push( @{ $children{$v} }, $k );
}
$" = ',';                       # Выходные данные разделяются запятыми
while (<>)  {
  chomp;
  if ($children{$_)  {
    @children = @{$children{$_}};
  } else {
      @children = "nobody";
    }
  print  "$_ begat @children.\n";
}

Хэши также могут представлять такие отношения, как директива #include языка С — А включает В, если А содержит #include В. Следующий фрагмент строит хэш (он не проверяет наличие файлов в /usr/include, как следовало бы, но этого можно добиться ценой минимальных изменений):

foreach $file (@files)  {
  local *F;              # На случай,  если понадобится
                                   # локальный файловый манипулятор
  unless (open (F, "<$file"))  {
  warn "Couldn't  read file: $!; skipping.\n";
  next;
}
while (<F>)  {
  next unless /^\s*#\s+include\s+<([^>\+)>/;
  push(@{$includes{$1}}, $file);
  }
  close F;
}

Другой фрагмент проверяет, какие файлы не включают других:

@include_frее = ();                # Список файлов, не включающих других файлов
@uniq{map { @$_ } values %includes} = undef;
foreach $file (sort keys %uniq) {
  push( @include_free , $file ) unless $includes{$file} ;
}

Результат values %includes представляет собой анонимный массив, поскольку один файл может включать (и часто включает) сразу несколько других файлов. Мы используем map для построения большого списка всех включенных файлов и удаляем дубликаты с помощью хэша.

Представление отношений между данными

Проблема

Решение

Комментарий

См. также