【アルゴリズム】SortedSet(平衡二分探索木)のインデックスアクセス
平衡二分探索木には様々なアルゴリズムが開発されている。私が実装に使っているのは赤黒木なのですが(というよりそれ以外は実装したことない)、たまにインデックスアクセスしたいことがあります。
二分木でインデックスアクセスしようとするとO(N)の計算量(※N=要素数)かかると勘違いしている人がたまにいるのですが、O(logN)でアクセスできます。
とりあえずソートListと平衡二分探索木の特徴をまとめてみます。
SortedList(ソートリスト)
検索 : O(logN)
挿入 : O(N)
インデックスアクセス : O(1)
SortedSet(平衡二分探索木)
検索 : O(logN)
挿入 : O(logN)
インデックスアクセス : O(logN)
メモリ量は平衡二分探索木のほうが重いですが、挿入の比重が重く、インデックスアクセスは普段しないので、平衡二分探索木を使っとけば間違いないです。
そして、二分探索木でインデックスアクセスする方法ですが、
実装は各ノードに、そのノードの子孫ノードにおいて自分より小さなノードの(つまり左下ノード)総数を記憶しておくだけでいいです。
アクセスする際はルートノードから和を累積していき、累積がアクセスしたいインデックスになるようなノードを見つけるだけです。
ノードを回転する時、挿入or削除の際に木を辿りながら、書き換えるだけなので計算量に影響はありません。
C#(VB)のSortedSetですが、インデックスアクセスもサポートされていませんし、
ソートされているという特徴上、次の(大きい)ノードをO(1)で探索できるのに、前や後ろを参照する関数もサポートされていない。
また、ある値(以上、以下、よりも大きい、未満)の値を取得する関数もありません。O(logN)
独自で作ると非常に使いやすく、よきプログラミングライフがおくれるのでお勧めです。
【WPF】Stringやintなどのシステム型をXamlで直接生成する。
<Window
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:sys="clr-namespace:System;assembly=mscorlib"
x:Class="hogehoge"
Title="test" Width="100" Height="100">
<ListBox Margin="10">
<ListBox.ItemsSource>
<x:Array Type ="{x:Type sys:String}">
<sys:String>foo</sys:String>
<sys:String>bar</sys:String>
</x:Array>
</ListBox.ItemsSource>
</ListBox>
</Window>
とすれば簡単に生成できる、よく質問される。
詰まるポイントとしては
- xmlnsでsysと生成している部分のasseemblyを指定していないか、Systemが設定されている。インテリジェンスを使うとよく起こる。ちゃんとmscorlibを設定しよう。
- x:Array、sys:Stringはインテリジェンス候補として表示されない。全て手動で入力しないといけない。
- x:ArrayのTypeを設定したり、全てのコンテンツを入力しないと不適当なエラーが表示される。
つまり、エラーやインテリジェンスに惑わされない事が必要。正常なコードでもビルドするまでエラーが消えないことがよくあるので、WPFにおいてはVIsualStudioをあんまり信用しちゃいけませんよって事。
私もBlend使い始めた時は、何度も騙されました(笑)
【WPF】Toolkitが導入できない件
本家本元WPFToolkitは既にサポートが切れているらしく、最終リリースは2010年らしい。
皆使ってるだろうからこれでいいかーってNugetしたらChart系のコントロールが見当たらない。
そんな馬鹿なって今度は公式からインストーラーをダウンロードしてインストールしても全然ダメ。
調べたら、NET.Framework3.5しかサポートされていないらしい。
仕方ないのでコードを入手して自分で設定弄ってやってコンパイルしようとしたが、今度はMicrosoft.Windows.Design.dllが参照できないし。OSにスキャンかけてやっても見つからない。多分古いバージョンではないと存在しないのだろう。
ここまでして本家は断念。皆どうやって使っているんだろう。
次は、Nugetで上位に来ていたExtendWPFToolkitを使用してみることに、Codeplexでドキュメントを翻訳しながら読んでいると、Chart系はまさかの有料。
諦めて今までどおりカスタムコントロールで自作しようと、簡易円グラフ作ったけど非常に時間がかかった。この調子でライブラリを作っていくと相当に時間がかかる。
適当にネットサーフィンしていたらSparrow Toolkitを発見。少し使ってみたが問題なく使えた。今までの苦労に涙を流しながら、これからはこれを使おうと思う。
