tech.guitarrapc.cóm

Technical updates

PowerShellのHashtableの並び替えを制御したい

Hashtable連載第三弾は、ソートです。 ご存じのとおり、Hashtableは勝手に並び替えられたり、ソートをするのが辛いです。 このままだと何かと使い難いため少しみてみました。

Hashtable

さて、まずは通常のHashtableを見てみます。
$hash = @{
    z=1
    c=3
    x=2
    b=4
}
出力してみます。
$hash | Format-Table -AutoSize
勝手に並び替えられていますね…
Name Value
---- -----
c    3
b    4
z    1
x    2
ご存じのとおりクラスは、System.Collections.Hashtableです。
$hash.GetType().FullName

PowerShellで追加された[ordered]@{}で入力順を保持する

さて、PowerShell 3.0では、Hashtableの頭にだけつけられるキーワードとして[ordered]があります。 さっそく見てみましょう。
$hashOrdered = [ordered]@{
    z=1
    c=3
    x=2
    b=4
}
出力してみます。
$hashOrdered | Format-Table -AutoSize
入力した通りに格納されていますね。
Name Value
---- -----
z    1
c    3
x    2
b    4
クラスが、System.Collections.Specialized.OrderedDictionaryに変化しています。
$hashOrdered.GetType().FullName
MSDN先生を見てみましょう。
MSDN - OrderedDictionary クラス
説明はこうですね。
OrderedDictionary の要素は、SortedDictionary クラスの要素とは異なり、キーによっては並べ替えられません。要素は、キーまたはインデックスを使用してアクセスできます。

頻繁に挿入、削除などがあるならSystem.Collections.Generic.SortedDictionary

さっそく、System.Collections.Generic.SortedDictionaryでやってみましょう
$GenericSortedDicKey = New-Object 'System.Collections.Generic.SortedDictionary[string, int]'
$GenericSortedDicKey.z = 1
$GenericSortedDicKey.c = 3
$GenericSortedDicKey.x = 2
$GenericSortedDicKey.b = 4
出力してみます。
$GenericSortedDicKey | Format-Table -AutoSize
キーで並び替えができました。
Key Value
--- -----
b       4
c       3
x       2
z       1
ご存じのとおりクラスは、System.Collections.Generic.SortedDictionaryです。
$GenericSortedDicKey.GetType().FullName

# System.Collections.Generic.SortedDictionary`2[[System.String, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089],[System.Int32, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]
ただ、Dictionaryはパフォーマンスがちょっと。
SortedDictionary ジェネリック クラスは、O(log n) 取得を使用するバイナリ サーチ ツリーです。n は、ディクショナリ内の要素数を示します。この点で、これは SortedList ジェネリック クラスに似ています。この 2 つのクラスには、同じようなオブジェクト モデルがあり、どちらも O(log n) 取得アルゴリズムを備えています。この 2 つのクラスの違いは、メモリの使用方法と、挿入および削除の速度です。
  • SortedList は、SortedDictionary ほどメモリを使用しません。
  • SortedDictionary には、並べ替えられていないデータ用の高速な挿入操作および削除操作があります。その計算量は、SortedList が O(n) であるのに対して、O(log n) となります。
  • 並べ替えられたデータから一度にすべてのデータを取り込む場合、SortedList の方が SortedDictionary よりも高速です。
値で並べ替えなら、あとはsort Vでいいかなぁと思います。

Listを見てみよう

今度は、System.Collections.Generic.Listです。
$GenericList = New-Object 'System.Collections.Generic.List`1[string]'
$GenericList.add("z")
$GenericList.add("c")
$GenericList.add("x")
$GenericList.add("b")
出力してみます。
$GenericList
入力順に入っていますね。
z
c
x
b
型を見てみましょう。
$GenericList.GetType() | Format-Table -AutoSize
$GenericList.GetType().FullName
そのまま出せばこうですが。
IsPublic IsSerial Name   BaseType
-------- -------- ----   --------
True     True     List`1 System.Object

System.Collections.Generic.List`1System.String, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089
, 演算子を付けるとObject[]に展開されるため注意です。 出力は変わりませんが。
, $GenericList
見た目は変わりません
z
c
x
b
型が変わります。
(, $GenericList).GetType() | Format-Table -AutoSize
$GenericList.GetType().FullName
Object[]になっています。
IsPublic IsSerial Name     BaseType
-------- -------- ----     --------
True     True     Object[] System.Array

System.Collections.Generic.List`1System.String, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089
MSDN - List ジェネリック クラス

纏めて取り込んで、更新削除がないならならSortedListを見てみよう

SortedDictionaryより高速に処理するなら、System.Collections.Generic.SortedListです。
$GenericSortedList = New-Object 'System.Collections.Generic.SortedList[string, int]'
$GenericSortedList.z = 1
$GenericSortedList.c = 3
$GenericSortedList.x = 2
$GenericSortedList.b = 4
出力してみます。
$GenericSortedList | Format-Table -AutoSize
キーで並び替えができました。
Key Value
--- -----
b       4
c       3
x       2
z       1
型を見てみましょう。
$GenericSortedList.gettype() | Format-Table -AutoSize
$GenericSortedList.GetType().FullName
そのまま出せばこうですが。
IsPublic IsSerial Name         BaseType
-------- -------- ----         --------
True     True     SortedList`2 System.Object

System.Collections.Generic.SortedList`2[[System.String, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089],[System.Int32, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]
, 演算子を付けるとObject[]に展開されるため注意です。 出力は変わりませんが。
(, $GenericSortedList).gettype() | Format-Table -AutoSize
(, $GenericSortedList).GetType().FullName
型が変わります。
(, $GenericList).GetType() | Format-Table -AutoSize
$GenericList.GetType().FullName
Object[]になっています。
IsPublic IsSerial Name     BaseType
-------- -------- ----     --------
True     True     Object[] System.Array

System.Object[]
MSDN - SortedList ジェネリック クラス
この注意に気をつけましょう。
SortedList ジェネリック クラスは、O(log n) 取得を使用するバイナリ サーチ ツリーです。n は、ディクショナリ内の要素数を示します。この点で、これは SortedDictionary ジェネリック クラスに似ています。この 2 つのクラスには、同じようなオブジェクト モデルがあり、どちらも O(log n) 取得を備えています。この 2 つのクラスの違いは、メモリの使用方法と、挿入および削除の速度です。
  • SortedList は、SortedDictionary ほどメモリを使用しません。
  • SortedDictionary には、並べ替えられていないデータ用の高速な挿入操作および削除操作があります。その計算量は、SortedList が O(n) であるのに対して、O(log n) となります。
  • 並べ替えられたデータから一度にすべてのデータを取り込む場合、SortedList の方が SortedDictionary よりも高速です。
あとはインデックスでのアクセスでしょうか。
SortedListクラス = インデックスを指定したキー・値へのアクセスが出来る SortedDictionaryクラス = インデックスを指定したアクセスは出来ない つまり、SortedListでは、KeysプロパティおよびValuesプロパティを参照して、インデックスを指定しての各要素K,Vを取得可能。(インデックスを指定した値・キーの設定は出来ない あとの、SortedDictionary と SortedList の違いは、SortedList はKとVを効率的にインデックスで取得します。 リストはKとVの内部配列をラッパーしてるだけなので、Kおよび Vによって返されるコレクションが使用されプロパティアクセス時に再生成がない。

まとめ

HashTableは何かと使うのに不便でしょうがないので、このようなやり方がどうしても必要ですね。 最後に[PSCustomObject]へのキャストを見てみます。 ちなみに、すべて変換できますのでご安心を。 Hashtable
[PSCustomObject]$hash
c b z x
- - - -
3 4 1 2
System.Collections.Specialized.OrderedDictionary
[PSCustomObject]$hashOrdered
z c x b
- - - -
1 3 2 4
System.Collections.Generic.SortedDictionary
[PSCustomObject]$GenericSortedDicKey
Key Value
--- -----
b       4
c       3
x       2
z       1
System.Collections.Generic.List
[PSCustomObject]$GenericList
z
c
x
b
System.Collections.Generic.SortedList
[PSCustomObject]$GenericSortedList
Key Value
--- -----
b       4
c       3
x       2
z       1