Перевод "Building a Better Hash" | Participants
|
- Statistics
- Participants
- Translate into Russian
- Translation result
- 22% translated in draft.
If you do not want to register an account, you can sign in with OpenID.
Building a Better Hash | ||
Originally published in The Perl Journal, Summer 1999 | Оригинал опубликован в The Perl Journal летом 1999г. | |
Introduction | ||
One of the nice things about Perl is its support for reuse. I can solve a problem once, and then generalize it so that everyone else with the same problem can use my solution. In this article, I'll examine a simple problem and take it through the steps required to turn it to a reusable module. Along the way, we'll visit the topics of data structures, ties, optimization, and testing. | Одна из замечтельных вещей, касающихся Perl - это система поддержки повторного использования. Единожды решив задачу и обобщив решение, я тем самым позволяю любому использовать для решения схожей задачи мое решение. В данной статье, я рассмотрю простые задачи и проанализирую этапы превращения их решений в повторно используемые модули. По пути мы обсудим и такие темы, как структура данных, связи, оптимизация, тестирование. | |
The problem | ||
Someone on the Boston Perl Mongers mailing list asked how to efficiently manage a collection of items such that you can insert and delete values quickly, but also choose random values quickly. | Кто-то в рассылке Boston Perl Mongers спросил, как эффективно работать с набором данных, чтобы можно было быстро добавлять и удалять значения, но в то же время и быстро выбирать случайные значения. | |
In a hash, it's easy to insert and delete values: | В хеш легко быстро добавлять значения и удалять их от туда: | |
$hash{$obj} = $obj; | ||
delete $hash{$obj}; | ||
But accessing random values is inefficient: | ||
my @k = keys %hash; | ||
$rand = $k[rand @k]; | ||
You can access random values quickly in an array, but you can't insert and delete values efficiently. | Можно получить быстрый доступ к случайному значению в массиве, но добавление и удаление значений неэффективно. | |
I might run into this problem if I were a soft-hearted person running an ongoing raffle. I'd have to keep track of the tickets people buy, and choose one randomly whenever it's time to select a winner. In addition, because I'm a nice guy, I'd let people drop out of the raffle, getting their money back, whenever they want; if someone wanted to drop out of the raffle like that, I'd need a way to find her ticket quickly. | ||
Discussion of the problem | ||
To restate the problem a little more formally, we want some sort of lookup table in which insertion, lookup, deletion, and random selection are all fast. | Сформулируя задачу более формально, нам нужна таблица преобразования для которой добавление, поиск, удаление, и выбор случайных значений быстры. | |
Do any of Perl's built-in data types do the trick? Let's compare the various naive data structures one could use for this problem: | ||
array hash | ||
insertion O(1) O(1) | ||
lookup O(n) O(1) | ||
deletion O(n) O(1) | ||
random key O(1) O(n) | ||
O(n) (pronounced 'order n'), or linear, time means that when there are n elements in the data structure, the operation takes time proportional to n. If an operation is O(1), it takes time proportional to 1; that is, it runs in constant time. |
© 1999 The Perl Journal.
