Как мне удалить хеш-элементы во время итерации?

Question

У меня довольно большой хэш (около 10M ключей), и я хотел бы удалить из него некоторые элементы.

Я обычно не люблю использовать delete или splice, и я копирую то, что хочу, вместо того, чтобы удалять то, что не делаю. Но на этот раз, поскольку хеш действительно большой, я думаю, что я хотел бы удалить непосредственно из него.

Итак, я делаю что-то вроде этого:

foreach my $key (keys %hash) {
 if (should_be_deleted($key)) {
  delete($hash{$key});
 }
}

И, похоже, работает хорошо. Но .. что, если я хотел бы удалить некоторые элементы еще до того, как итерировать их? Я объясню на примере:

foreach my $key (keys %hash) {
 if (should_be_deleted($key)) {
  delete($hash{$key});
  # if $key should be deleted, so does "$key.a", "kkk.$key" and some other keys
  # I already know to calculate. I would like to delete them now...
 }
}

Я подумал о некоторых возможных решениях - например, проверка того, существует ли еще ключ в качестве первого шага в цикле или первый цикл, и создание списка ключей для удаления (без фактического удаления их), затем фактическое удаление в другом цикле.

Что вы думаете об этом?

UPDATE

Кажется, что подход с двойным проходом имеет консенсус. Однако это довольно неэффективно в том смысле, что во время первого прохода я перепроверяю ключи, которые уже были помечены для удаления. Это довольно рекурсивно, потому что я не только проверяю ключ, но и вычисляю другие ключи, которые следует удалить, хотя они уже были рассчитаны по первоначальному ключу.

Возможно, мне нужно использовать более динамическую структуру данных для перебора ключей, которая будет динамически обновляться?

Answer 1

Я рекомендую сделать два прохода, потому что это более надежно.Порядок хеширования фактически случайный, поэтому нет никаких гарантий, что вы увидите «первичные» ключи перед соответствующими.Например, если should_be_deleted() обнаруживает только первичные ключи, которые не нужны, а соответствующие ключи вычисляются, вы можете в итоге обработать ненужные данные.Двухпроходный подход позволяет избежать этой проблемы.

my @unwanted;
foreach my $key (keys %hash) {
    if (should_be_deleted($key)) {
         push @unwanted, $key;
         # push any related keys onto @unwanted
    }
}

delete @hash{@unwanted};

foreach my $key (keys %hash) {
    # do something
}

Answer 2

Как насчет этого:

my %to_delete;

foreach my $key (keys %hash) {
    if (should_be_deleted($key)) {
        $to_delete{$key}++;
    }
    # add some other keys the same way...
}

delete @hash{keys %to_delete};

Answer 3

Вы можете пометить элементы хеша, которые нужно удалить, установив их значения на undef.Это позволяет избежать потери места в отдельном списке ключей, которые необходимо удалить, а также избежать проверок элементов, уже отмеченных для удаления.И было бы также менее расточительно использовать each вместо for, который формирует список всех ключей хеша перед началом итерации цикла

Как это

while ( my ($key, $val) = each %hash ) {

    next unless defined $val and should_be_deleted($key);

    $hash{$key}       = undef;
    $hash{$key.'a'}   = undef;
    $hash{'kkk'.$key} = undef;
}

while ( my ($key, $val) = each %hash ) {
    delete $hash{$key} unless defined $val;
}

Answer 4

Исходя из приведенного в примере примера, вы можете использовать grep для фильтрации ключей, соответствующих вашему токену $key.

Обновление

Ваш комментарий уточнил вашу потребность.Мое предложение было бы определить индексы, которые соответствуют вашим требованиям и обновить вас @keys установить соответствующим образом.Идея состоит в том, чтобы обновлять @keys во время его циклирования, чтобы избежать ненужных итераций.

Я реализовал простой grep как настраиваемую функцию здесь.

sub matches { $_[0] =~ /$_[1]/ ? 1 : 0 }  # Simple grep implemented here

my @keys = keys %hash;  # @keys should initially contain all keys

while ( @keys ) {

    my $key = shift @keys;
    next unless should_be_deleted ($key);  # Skip keys that are wanted

    my @indexes_to_delete = grep { matches ($key, qr/$keys[$_]/) } 0 .. $#keys;

    delete @hash { @keys[@indexes_to_delete] };     # Remove the unwanted keys

    splice @keys, $_, 1 foreach @indexes_to_delete; # Removes deleted ...
                                                    # ... elements from @keys.
                                                    # Avoids needless iterations.
}