Что такое подходящая структура данных для двустороннего отношения имени ↔ id?

Question

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

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

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

Спасибо.

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

# 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 5

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

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

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