スウィフト3およびカスタムリンクリストコレクションタイプのインデックス

Question

スウィフト3 Collectionインデックスは、Equatableではなく、Comparableに準拠している必要があります。

ここで全文を読むことができますswift-evolution/0065。

通常インデックスは を効率的データ構造のルートから要素へのパスをコードする一つまたは二つのintで表すことができる：ここでは

は、関連する引用です。自由にパスのエンコーディングを選択できるので、 は、インデックスが で安価に匹敵するように選択することができると思います。これは、標準ライブラリを実装するために必要なすべてのインデックスの場合に該当しました。この変更を調査中に調査されたのは です。

私のカスタムリンクリストコレクションの実装では、ノード（後続を指す）は不透明なインデックスタイプです。ただし、2つのインスタンスがある場合、チェーンの重要な部分のトラバーサルを危険にさらすことなく、他が先行するかどうかを判断することはできません。

私は好奇心が強いのですが、でリンクリストのインデックスをComparableで実装する方法はありますか？O（1）複雑ですか？

私が現在持っている唯一のアイデアは、インデックスを前進させながらインデックスをインデックスとしてインデックスとして格納し、それらの値を比較しながら何らかのステップをカウントすることです。

このソリューションの深刻な欠点は、コレクションを変更する際にインデックスを無効にする必要があることです。そして、それは配列にとって妥当と思われますが、リンクリストには大きな利点があります。変更されていないノードのインデックスは無効になりません。

EDIT： それは、単一リンクリストはフロントを挿入実装することを想定し、コレクションのプロパティとして二つの追加の整数のコストで行うことができ、フロントとを削除するバックを追加します。途中で干渉している人は、とにかく壊れてしまうでしょう。O（1）複雑さが必要です。

Answer 1

ここに私のそれがあります。

）私はIndexというカスタムタイプのプライベート整数型プロパティをdepthに導入しました。

b）私はコレクションに2つのプライベート整数型プロパティ、startDepthとendDepthを導入しました。どちらも空のリストではデフォルトでゼロになっています。

1. 各フロントインサートは、startDepthをデクリメントします。
2. 各フロント削除はstartDepthを増分します。
3. 各バックアペンドは、endDepthをインクリメントします。

したがって、すべてのインデックスstartIndex..<endIndexは、反射整数範囲startDepth..<endDepthを持ちます。

c）コレクションは、インデックスがstartIndexまたはendIndexのいずれかである場合、そのコレクションに対応する深さの値を継承します。 index(_ after:)を呼び出してコレクションのインデックスを進めるように求められたら、新しいIndexインスタンスをインクリメントされた深さの値（depth += 1）で単純に初期化します。

Comparableに従うと、左側の奥行き値と右側の奥行き値とを比較することができます。

整数の範囲を両側からも拡張するため、中間インデックスのすべての奥行き値は変更されないため（無効化されません）です。

結論：の

上場利点O（1）のメモリフットプリントといくつかの整数の増分と減分のわずかな増加を犠牲に指数の比較。私は、インデックスの寿命は短く、コレクションの数は比較的少ないと考えています。

誰かがもっと良い解決策を持っていれば、私は喜んでそれを見てみましょう！

Answer 2

私には別の解決策があるかもしれません。整数の代わりに浮動小数点数を使用する場合は、挿入ノードのsortIndexを前任者と後継者の間の値に設定すると、O（1）中間結果の挿入が得られます。sortIndexこれは、先行者のsortIndexをあなたのノードに保存（および更新）する必要があります（これは、挿入や削除時に変更されるだけであり、常に上に伝播できるため難しいとは思いません）。

index(after:)メソッドでは、後継ノードをクエリする必要がありますが、ノードをインデックスとして使用するため、それは簡単です。

1つの注意点は浮動小数点の有限精度であるため、挿入時に2つのソートインデックス間の距離が2つ小さい場合は、リストの少なくとも一部を再インデックスする必要があります。あなたは小規模だけを期待していると言いましたので、私は穴のリストを通過し、その位置を使用します。

このアプローチには、すべて自分のメリットがあり、途中で挿入するとパフォーマンスが向上するという利点があります。