ansaurus

Question

What is an appropriate data structure for a two-way name ↔ id relation?

Answer 1

+2 A:

You could just combine both "fast" approaches. Use an array to lookup id -> name, and a hash to go from name -> id.

By "database," I assume you're just talking about some data structure (like an array or hash) and not a relational database (like MySQL).

Matt Ball 2010-07-30 19:46:23

Answer 2

A:

One way could be to use both of these implementations. Use array when you need name from id and use hash when you need id from name. Not sure if it's the best way though.

Raze2dust 2010-07-30 19:46:44

Answer 3

A:

Use both an array and a hash. Your question is a special case of this question.

In Perl, you can use the tie mechanism to make a class that looks like a hash with an additional method for look up by id, but where additions and deletions maintain both a hash and an array behind the scenes.

Tie::Hash::TwoWay provides a dual-lookup data structure with a hash both ways. It would probably be suitable for your purpose (there isn't much to be gained by storing student ids in an array except fast enumeration in student id order), and if not it can serve as inspiration.

Gilles 2010-07-30 19:54:46

how can I make use of this functionsub hashValueAscendingNum { $student_record{$a} <=> $grades{$b};}which sort the hash{name}=id by value

2010-07-30 20:03:45

ignore the above comment I added. see below:how can I make use of this function sub hashValueAscendingNum { $student_record{$a} <=> $student_record{$b}; } which sort the $student_record{name}=id by value id

2010-07-30 20:05:24

@lilili08: you can delete or edit your comments, rather than just posting a new one.

Matt Ball 2010-07-30 21:09:33

Answer 4

+4 A:

swestrup 2010-07-30 20:04:45

since the student list is long and eat memory,I do not want to create both hash and array. I just to make the student name consume memory for once.but look like $student_by_id and $student_by_name copy student name again.it is correct?

2010-07-30 21:24:07

@lilili08 In programing you often have to choose between memory use and speed. If you must have both look ups fast you must use some memory to accomplish it.

Ven'Tatsu 2010-07-30 21:42:28

No, lilili08, there is only one copy of the student information kept, in the @student array. The other two arrays do NOT carry copies of the information, but references to it. If you modify the record in $student[1], then $student_by_name{'Bob Brown'} and $student_by_id[2] will change as well. Read up about perl references with 'perldoc perlreftut'

swestrup 2010-07-31 01:22:14

@swestrup I think you might want to assume that student IDs are sparse, and have student_by_id also be a hash.

hobbs 2010-07-31 04:38:22

@hobbs: I normally would assume that, but the answer explicitly states that student ids are sequential integers from 1 to the number of students. Even if some elements (like 0) are missing, that's sufficiently un-sparse to justify an array. Always read the spec.

swestrup 2010-07-31 15:09:32

In that case, you don't need `@student`; `@student_by_id` can easily do both jobs :)

hobbs 2010-07-31 23:54:56

@hobbs: Oh, I considered that too, but I can easily imagine many scenarios in which the need to maintain student ids in some particular order could become onerous, so I assumed they were essentially random. This could happen if, for example, the student records were concatenated from several administrative files and then read in.

swestrup 2010-08-01 15:11:39

Answer 5

+1 A:

I often create hashes that contain a record of information and different index hashes to locate them.

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

That's the guts, though I'd probably encapsulate the record and the lookup mechanism.

Axeman 2010-07-30 20:17:06

what does this code mean? the student name list is long, I do not want to store it in memory using multiple data structure. just want to store it in memory once. does your implementation save memory? Thanks

2010-07-30 21:31:54

@lilili08, it *is* only stored once, in two different hashes. It's a classic memory-time tradeoff.

Axeman 2010-07-31 03:28:27

ansaurus

tags:

views:

answers:

What is an appropriate data structure for a two-way name ↔ id relation?

related questions