大きなテーブルを操作するためのグリッド実装。 パート2

記事の前の部分で、システムの動作の一般的な原理が分析されました。その2つの主要なブロックが補間器と番号付け装置であることがわかりました。 相互作用スキームを構築し、補間器の実装についても十分に議論しました。 このパートでは、番号付けの実装を分析します。キーフィールド値のセットを自然数（BigInteger）に変換する可逆関数です。 少ないダイヤル 以下の場合に限り、DBMSの観点から 。 簡単に言えば、値のセットと、最も興味深いことに、文字列を補間する方法を学習します。

複合キー分子

データ型の力を、この型を使用して表現できるさまざまな値の数と呼びます。 たとえば、BIT型は2の累乗で、INT-2 ³²と入力します。 複合データ型にパワーを持たせる 。 次に、複合キーのキーフィールド値の可能な組み合わせの総数は 。 各フィールドの値に対して番号付け関数を計算する方法を既に知っていると仮定します。 -値のシリアル番号 フィールド。 次に、複合キーの番号付けの機能は、各フィールドの番号付けの機能を通じて次のように表すことができます。


1）値を検証するのは簡単です 最大の重みを持っています -番号付け機能の最小で基本的な要件が満たされている、2） 。

私たちはすぐに計算に注意します 上記の式によって直接必要 乗算演算、およびホーナーのスキームのアナログを使用して、乗算の数を 同じ数の追加で：


ここで、逆関数を計算するアルゴリズムが必要です 。 値に注意してください 数字を解釈するような 位置番号システムでは、基底が「数字」から「数字」に常に変化します。 したがって、値を変える 「数字」のセットに戻ると、与えられたベース（ここでは値= 、キー[i] .cardinality（）= ）：

BigInteger v = value; BigInteger[] vr; for (int i = keys.length - 1; i >= 0; i--) { vr = v.divideAndRemainder(keys[i].cardinality()); keys[i].setOrderValue(vr[1]); v = vr[0]; } 

プリミティブデータ型の番号付け

複合キーを把握しましたが、実際に遭遇する型のナンバラーを作成する必要があります。

1. BIT型の値の番号付けは簡単です。false-0、true-1です。
2. INT型の値の番号付けはもう少し複雑です。INT値（32ビット符号付き整数）は-2147483648〜2147483647の数字です。したがって、INT型の番号付けは 。 もちろん、追加はすでに行われているはずです BigIntegerと入力します。 逆関数 。
3. 同様に、64ビットの符号付き整数の分子を作成できます（9223372036854775808を追加する必要があります）。
4. IEEE 754形式で表示されるDOUBLE （倍精度浮動小数点）数には、符号付き64ビット整数として比較できる（NaNや±0などの小さな例外を伴う）性質があります。 たとえば、Javaでは、double型の値の場合、IEEE 754形式の64ビットイメージは、Double.doubleToLongBitsメソッドを使用して取得できます。
5. 最後に、最も近いミリ秒までの時間を決定するDATETIME値は、いわゆる「UNIX時間」、つまり1970年1月1日の午前0時からのミリ秒数を指定する64ビット符号付き整数に減らすこともできます。 たとえば、Javaでは、これはDate.getTime（）メソッドを使用して行われます。
6. 行（ VARCHAR ）には、個別の大規模な会話が必要です。

ラインの番号付け（最初の近似）

行の長さが制限されていない場合、番号付けを作成するタスクは不可能です。行 'a'と 'b'の間には、辞書式順序で無限に多くの行 'aa'、 'aaa'、 'aaaa' ...があり、任意の2つの自然数の間には常に有限数の自然数。 数学者は、辞書式に順序付けられた文字列のセットと自然数のセットの順序は非同型であると言います。 幸いなことに、私たちに知られているDBMSでは、インデックスは限られた長さの行にのみ構築でき、これにより問題が根本的に変わります。

アルファベットに含まれている場合 文字、その後の長さの行の総数 このアルファベットでは等しい


ここで、単位は空の文字列に対応し、 -1文字の行数、 -2文字の行数など。最終的には、幾何学的進行の古き良き合計を取得します。

今、任意の文字列を想像してください 長さ 配列のように どこで -番号 アルファベットの行の0番目の文字（ゼロからカウント）、行の文字の位置も最初からカウントします。 その後、行 単純な辞書式順序で番号があります




計算を最適化するには および逆関数、係数の配列を事前に準備する必要があります


もちろん、値を準備するときにこの式を直接使用してください 不要：すべてに注意することで算術演算を節約できます 等比数列の部分的な合計で、配列を埋めるときに「オンザフライ」で計算できます 。

逆関数を計算するためのアルゴリズム 、複合キーの番号付けの場合のように、任意のベースを使用して番号を番号システムに変換するためのアルゴリズムのバリエーションです。 次の文字を取得する前に、次の文字の式の最初の項を覚えて、1つ減算する必要があります。 ：

 for (int i = 0; i < m; i++) { r = r.subtract(BigInteger.ONE); cr = r.divideAndRemainder(q[i]); r = cr[1]; int c = cr[0].intValue(); arr[i] = c; if (r.equals(BigInteger.ZERO)) { if (i + 1 < m) arr[i + 1] = END_OF_STRING; break; } } 

一致ルールを持つ行の番号付け

データベースが文字列値をソートする順序は、実際には単純な辞書編集の順序とは異なり、いわゆるUnicode照合規則を使用します 。

データベースを使用してこれらのルールを念頭に置いて文字列を比較する場合、各文字は3つの側面で考慮されます。文字自体、大文字と小文字（スペル）、スペル（アクセント）です。 たとえば、ほとんどの場合、ロシア語の文字「e」には2つのスペルバリアントがあり、それぞれに2つのレジスタがあります。e、E、 This、。これにより、小文字と大文字を区別せずに、大文字と小文字を区別しない（アクセントを区別しない）および大文字と小文字を区別しないで "e"と ""を区別できなくなります。 同時に、別の文字と見なすもの、別の文字を書く変形と見なすものは文化的伝統に依存し、同じアルファベットを使用する言語でも異なる場合があります。

たとえば、ロシアの文化的伝統において、文字「」のステータスについてまだ意見の相違がある場合、「and」と「»」が異なる文字であることを疑う人はいません。 都市のアルファベット順のリストでは、並べ替えモードに関係なく、「Yoshkar-Ola」が「Irkutsk」の後に続きます。 ただし、PostgreSQLデータベースでアクセントを区別しない照合English-USを設定し、テーブルに都市のリストを入力し、名前で並べ替えると、Yzhkar-OlaがIrkutskに従うことがわかります（Izhevskの後でも） 「。 もちろん、選択された一致ルールのセットは、「d」を独立​​したシンボルとしてではなく、「and」という文字のスペルとして考慮しているためです。



一致ルールを考慮して文字列を比較する一般的なアルゴリズムは次のとおりです。

1. 文字列は、レジスタやオプションに関係なく文字ごとに比較されます。 違いが見つかった場合、結果が返されます（「もっと」または「より少なく」）。
2. 照合がアクセントを区別する場合、各文字のバリアント番号が比較されます。 違いが見つかった場合、結果が返されます。
3. 照合で大文字と小文字が区別される場合、各文字のレジスタが比較されます。 違いが見つかった場合、結果が返されます。
4. アルゴリズムの終了がこれまでに発生していない場合、行は等しくなります。

これらの微妙な点はすべて、タスクの実装に不可欠です。適切なグリッド操作は、分子によって返される値が（データベースの観点から）増加するにつれて増加する場合にのみ可能であるためです。

したがって、まず、一致規則を考慮するように文字列の番号付けアルゴリズムを変更する必要があります。次に、特定のデータベースで動作するようにグリッドを「教える」異なる一致規則を設定できる必要があります。

これらの問題の最初は、すでに得られた結果を考慮して、比較的簡単です。 すべての文字列値は、文字の1次元配列とは見なされません 、ただし3つのコンポーネントの値の配列（必要に応じてベクトル） 、 。 ここに -番号 アルファベットの文字 -独自のスペルバリアント、 -彼自身のレジスタ。 次に、3つのフィールドで構成される複合キーの操作と同様に、文字列フィールドの操作を実行できます。

わかっている場合 -アルファベットの文字数、 -スペルの最大数と -レジスタの最大数（既知の言語で） ：「大文字」と「小文字」）、その後


どこで -行の最初のコンポーネントから計算された数式値 （ ）、


前述の原則を使用して逆関数を作成するのは簡単です。最初に分離する必要があります 3つのコンポーネントに 、 そして 、その後、元の文字列の復元に基づいて、3つのコンポーネントの値の配列を取得します。

Java標準ライブラリには、抽象クラスjava.text.Collat​​orとその実装java.text.RuleBasedCollat​​orがあります。 これらのクラスの目的は、文字列をさまざまな一致規則と比較することです。 事前定義されたルールの広範なライブラリが利用可能です。 残念ながら、これらのクラスは文字列比較以外の目的での使用には適していません。一致ルールに関するすべての情報はカプセル化されており、通常の方法でシステムライブラリを使用して取得することはできません。

したがって、私たちの問題を解決するために、比較のルールのインタープリターを独立して作成する必要がありました。

RuleBasedCollat​​orクラスを学習すると、これが簡単になりました。 主なアイデアは、ソート規則を決定するための言語であり、その正式な説明はドキュメントに記載されています 。 この言語がどのように機能するかを理解する最も簡単な方法は、ルールの例を見ることです。

 <,<,<,;,<,<,<,;,<,<, 

次の文字は、一致規則の言語で公式です。

1. <-文字の分離、
2. ; -スペルの分離、
3. 、-レジスタの分離。

上記のような式を使用して、異なるデータベースの異なるマッピングに対応するルールを定義できます。 マッチングルールの言語は非常に原始的であるため、その上で式を解析するために、 決定論的な有限状態マシンとして機能する十分なアルゴリズムがあります。 その結果、ルールの式が与えられると、次のことが可能なクラスのインスタンスを取得します

1. 指定されたルールに従って値を取得します （文字数）も （オプションの最大数）および （最大レジスタ数）直接および逆の番号付け関数を計算するため、
2. 特定の文字について、その3つのコンポーネント（アルファベットの文字番号、オプション番号、レジスタ番号）を決定します。
3. 与えられたトリプルのコンポーネントに対して、シンボルを決定します。

文字列値の分子が作成されます。 記事の最初の部分で説明したスキームに従ってシステムを組み立てることができます。

最後の仕上げ

システムが組み立てられ、テストが開始された後、いくつかの改善を伴う機能が発見されました。

まず、実際の実装における重要なニュアンスは、小さなステップでスクロールスライダーの動きを個別に処理する必要があることです。

垂直スクロールバーの上矢印と下矢印をクリックすると、1行上または下にスクロールします。 スライダーの上または下にあるスクロールバーのフリーフィールドをクリックすると、固定（小さい）行数までスクロールします。 これらの場合、ユーザーは、画面に表示されるすべての行が固定数の位置だけシフトすることを期待しています。 十分な補間ポイントを持たない補間器は、ユーザーに表示される画像を前後にドロップすることで予測できない動作をする可能性があり、明確化した後、スクロールバーの位置はユーザーが望むものに対応しなくなります。

ただし、この場合、補間器の使用は正当化されません。 キーフィールド値の以前のセットがわかっている場合は、データベースへのクイッククエリによって前の（または次の）レコードを取得できます。 これを数回実行すると、以前のレコードまたは後続のレコードを取得できますが、これらはまだユーザーには表示されません。
このデータを抽出した後、ユーザーに表示するだけでなく、 レコードをカウントする要求に頼らずに補間テーブルに別のポイントを追加することができます。受信したレコードには既知の値だけ前のレコードと異なる番号があるためです。

実際の実装におけるもう1つの重要なニュアンスは、ユーザーがグリッドのスクロールを開始する前に補間テーブルにデータを入力する必要があることです。

組み合わせ番号が驚くことではありません 数直線上に分布する実際のテーブルのデータに基づいて、非常に不均一です。 したがって、補間テーブルに十分なポイントがない場合、ユーザーは、スクロールバースライダーを一定の距離だけ移動すると、位置を指定した後、前後に強い「バウンス」を得ることができます。 その結果、表示されたデータの実際の位置は、ユーザーが望んでいたよりもはるかに遠く、または逆に移動します。

テストでは、位置決め時のスクロールバーの長さの20〜25％の誤差は心理的に許容できるが、それ以上ではないことが示されています。 したがって、グリッドを表示した後、ユーザーは、「バウンス」の最大長が、補間テーブルの統計がまだ蓄積されていない作業の最初でもスクロールバーの長さの20〜25％を超えないようにすることが望ましい。

これは、グリッドの表示後に起動される並列実行スレッドで効率的な方法で実行できます。 このスレッドでは、一連の改良クエリが実行され、その結果が補間テーブルを補充します。 詳細化クエリのキーの組み合わせの値は、補間テーブルのレコードのシリアル番号の値の最大のギャップの中央に位置するたびに選択されます。 このプロセスは、最大ギャップの幅が目的のサイズに縮小されるか、反復回数の制限に達するまで実行されます。

実用的な実装

ここで示した原則に従ったグリッドは、PostgreSQLをDBMSとして使用してJavaで実装されました。 負荷テストデータセットの1つとして、ロシアの集落の1075429通り名を含むKLADRデータベースが使用され、ソートはさまざまなフィールドとその組み合わせによって実行されます。 ここで概説したすべての原則が機能します。 垂直スクロールバースライダーが絶えず移動している場合、ユーザーはすべてのレコードをリアルタイムでスクロールしているように錯覚します。スクロールの終了直後（リファインメントクエリがトリガーされ、補間テーブルに別のドットが追加されたとき）、スクロールバースライダーの位置は短い距離をジャンプすることでリファインされます。 ポジショニングを使用すると、目的のエントリをすぐに表示し、すぐにその位置も指定された後すぐにスクロールバースライダーをおおよそ設定できます。 グリッドと補間ポイントの蓄積を操作すると、「バウンス」は次第に目立たなくなります。

***

行われた作業に基づいて、科学出版物を準備しています。また、arxiv.orgのこの記事の科学版の前刷りに慣れることもできます。