Powershell 2 и .NET: оптимизировать для очень больших хеш-таблиц? - PullRequest
Новая
       11

Powershell 2 и .NET: оптимизировать для очень больших хеш-таблиц?

3 голосов
/ 23 сентября 2011

Я увлекаюсь Powershell и совершенно не знаком с .NET.

Я запускаю скрипт PS, который начинается с пустой хеш-таблицы. Хэш-таблица увеличится как минимум до 15 000–20 000 записей. Ключи хеш-таблицы будут адресами электронной почты в строковой форме, а значения будут логическими. (Мне просто нужно отследить, видел ли я адрес электронной почты.)

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

Вот часть моего кода, о которой мы говорим: 

...
    if ($ALL_AD_CONTACTS[$emailString] -ne $true) {
      $ALL_AD_CONTACTS += @{$emailString = $true}
    }
...

Мне интересно, можно ли что-нибудь сделать с точки зрения PowerShell или .NET, чтобы оптимизировать производительность этой хеш-таблицы, если вы ЗНАЕТЕ, что она будет огромной заранее, например, от 15 000 до 20 000 записей или более. 1010 *

Спасибо!

Ответы [ 3 ]

5 голосов
/ 04 марта 2012

Я выполнил некоторые базовые тесты, используя Measure-Command, используя набор из 20 000 случайных слов .

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

Если бы я выбрал, я мог бы склониться к варианту 5 из-за его простоты (всего один Add вызов на строку), но все протестированные мною альтернативы кажутся жизнеспособными. 

$chars = [char[]]('a'[0]..'z'[0])
$words = 1..20KB | foreach {
  $count = Get-Random -Minimum 15 -Maximum 35
  -join (Get-Random $chars -Count $count)
}

# 1) Original, adding to hashtable with "+=".
#     TotalSeconds: ~800
Measure-Command {
  $h = @{}
  $words | foreach { if( $h[$_] -ne $true ) { $h += @{ $_ = $true } } }
}

# 2) Using sharding among sixteen hashtables.
#     TotalSeconds: ~3
Measure-Command {
  [hashtable[]]$hs = 1..16 | foreach { @{} }
  $words | foreach {
    $h = $hs[$_.GetHashCode() % 16]
    if( -not $h.ContainsKey( $_ ) ) { $h.Add( $_, $null ) }
  }
}

# 3) Using ContainsKey and Add on a single hashtable.
#     TotalSeconds: ~3
Measure-Command {
  $h = @{}
  $words | foreach { if( -not $h.ContainsKey( $_ ) ) { $h.Add( $_, $null ) } }
}

# 4) Using ContainsKey and Add on a hashtable constructed with capacity.
#     TotalSeconds: ~3
Measure-Command {
  $h = New-Object Collections.Hashtable( 21KB )
  $words | foreach { if( -not $h.ContainsKey( $_ ) ) { $h.Add( $_, $null ) } }
}

# 5) Using HashSet<string> and Add.
#     TotalSeconds: ~3
Measure-Command {
  $h = New-Object Collections.Generic.HashSet[string]
  $words | foreach { $null = $h.Add( $_ ) }
}
3 голосов
/ 01 октября 2011

Итак, прошло несколько недель, и я не смог найти идеальное решение.Друг в Google предложил разделить хеш на несколько меньших хешей.Он предложил, чтобы каждый раз, когда я шел искать ключ, у меня было несколько промахов, пока я не нашел правильное «ведро», но он сказал, что штраф за чтение не будет почти таким же плохим, как штраф за запись при запуске алгоритма столкновения.чтобы вставить записи в (уже гигантскую) хеш-таблицу.

Я взял эту идею и сделал еще один шаг вперед.Я разделил хэш на 16 меньших блоков.Вставляя адрес электронной почты в качестве ключа в структуры данных, я фактически сначала вычисляю хэш на самом адресе электронной почты и выполняю операцию mod 16, чтобы получить согласованное значение в диапазоне от 0 до 15. Затем я использую это вычисленное значение в качестве "bucket "number.

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

Общая скорость, необходимая для построенияпредставление в «памяти» моего «главного списка» из более чем 20 000 адресов электронной почты с использованием разделенных сегментов хеш-таблиц теперь примерно на 1000% быстрее.(В 10 раз быстрее).

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

2 голосов
/ 01 октября 2011

Вы собираетесь потратить много времени ЦП, перераспределяя внутренние «массивы» в Hashtable.Вы пробовали .NET конструктор для Hashtable, который занимает емкость ? 

$t = New-Object Hashtable 20000
...
if (!($t.ContainsKey($emailString))) { 
    $t.Add($emailString, $emailString) 
}

Моя версия использует ту же самую $ emailString для ключа и значения, нет .NET-бокса $ true для[объект] просто как заполнитель.В условных выражениях PowerShell непустая строка будет иметь значение $ true, поэтому другой код, который вы проверяете, не должен меняться.Использование «+ = @ {...}» было бы большим нет-нет в чувствительном к производительности .NET-коде.Возможно, вы выделяете новый Hashtable для каждого электронного письма, просто используя синтаксис '@ {}', который может тратить много времени.

Ваш подход разбить очень большую коллекцию на (относительно небольшую)Количество небольших коллекций называется «шардинг».Вам следует использовать конструктор Hashtable, который занимает всю емкость, даже если вы разделяете на 16.

Кроме того, @Larold прав, если вы не просматриваете адреса электронной почты, тогда используйте 'New-Object ArrayList20000 ', чтобы создать предварительно выделенный список.

Кроме того, коллекции растут по затратам (в 1,5 или 2 раза при каждом «росте»).Результатом этого является то, что вы должны быть в состоянии уменьшить, сколько вы предварительно выделяете на порядок, и если коллекции меняются один или два раза за «загрузку данных», вы, вероятно, не заметите.Держу пари, что это первые 10-20 поколений «роста», которые требуют времени.

...