Какова подходящая структура данных для двустороннего отношения имя-идентификатор?

Question

У меня есть список имен учеников и их ID. Иногда мне нужно искать имя, используя идентификатор, иногда мне нужно искать идентификатор, используя имя.

• Если используется array[id] = name, то быстро найти имя по идентификатору, но медленно найти идентификатор по имени.
• Если используется hash{name} = id, то можно быстро найти идентификатор по имени, но медленно найти имя по идентификатору.

Какая структура данных лучше всего подходит для представления отношения ученика с именем? Примечание: имя студента - это строка, а id - целое число от 1 до общего числа этих студентов.

Спасибо.

Answer 1

Если вы пытаетесь сделать это без использования реальной базы данных, вам нужно иметь два индекса. Есть несколько способов сделать это, и вы на самом деле не дали достаточно информации о том, для чего вы это используете, но вот кое-что, что будет хорошо работать во многих случаях:

<code>
# Store student records sequentially, in any convenient order
my @student =
  ( { id=27,  name => 'Alice Amber', class = 'X' }
  , { id=2,   name => 'Bob Brown',   class = 'y' }
  , ...
  , { id=104, name => 'Zacharia Zebra', class = 'x' }
  );

# build index by id
my @student_by_id;
$student_by_id[$student[$_]{id}] = $student[$_] for 0..$#student;

# build index by name
my %student_by_name;
$student_by_name{$student[$_]{name}} = $student[$_] for 0..$#student;

То, что вам дает, - это одна копия студенческих записей, хранящихся в @student в произвольном порядке, и два индекса с именами @student_by_id и% student_by_name . Поскольку индексы хранят ссылки в записях учащихся, любые изменения, внесенные в запись с помощью любого индекса, будут видны с другого. Единственные проблемы возникают, когда вам нужно изменить либо имя студента, либо идентификационный номер, поскольку это потребует обновления затронутого индекса.

Answer 2

Вы можете просто объединить оба «быстрых» подхода. Используйте массив для поиска id -> name и хеш для перехода от name -> id.

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

Answer 3

Я часто создаю хэши, содержащие записи информации и разные хеш-индексы, чтобы найти их.

my $record 
    = { name          => 'James'
      , rank          => 'Captain'
      , serial_number => '007'
      };

foreach my $field ( qw<name rank serial_number> ) { 
    my $ref = \$lookup{ $field }{ $record->{ $field } };
    if ( ref( $$ref ) eq 'ARRAY' || !$lookup{meta}{$field}{is_unique} ) { 
        push @$ref, $record;
    }
    else { 
        $$ref = $record;
    }
}

Это мужество, хотя я бы, вероятно, инкапсулировал запись и механизм поиска.

Answer 4

Используйте как массив, так и хеш.Ваш вопрос является частным случаем этого вопроса .

. В Perl вы можете использовать механизм tie , чтобы создать класс, похожий на хеш, с дополнительным методом.для поиска по идентификатору, но там, где добавления и удаления сохраняют хэш и массив за кулисами.

Tie :: Hash :: TwoWay предоставляет структуру данных с двойным поиском схешировать в обе стороны.Это, вероятно, подойдет для вашей цели (хранение идентификаторов учеников в массиве мало что даст, кроме быстрого перечисления в порядке идентификаторов учеников), и если нет, то это может послужить вдохновением.

Answer 5

Одним из способов может быть использование обеих этих реализаций. Используйте массив, когда вам нужно имя из идентификатора, и используйте хэш, когда вам нужен идентификатор из имени. Не уверен, что это лучший способ.