おそらく、アルゴリズムとデータ構造のほとんどのコースには、基底配列を因子で成長させることによって要素を追加する償却コストO（1）を持つ拡張可能な配列バッファが含まれます。命令型言語では、それはしばしばリストの最も効率的な実装です。 、線形連結と付加を伴う効果的に不変の配列支援配列
//imperative pattern:
val buffer = new ArrayBuffer
for (list <- lists) {
buffer append list
}
//functional pattern:
foldLeft(Nil)((acc, list) => list :::acc)(lists)
リンクリストと正常に動作します：
アレイ・バック・シーケンスはまだ利点場合でも、不変の多くを持っていますが、関数型言語では、バッファに繰り返し追加ループは、一般的に倍に置き換えられます純粋な実装では、配列のコストはO（n^n）です。 ArrayListのすべてのインスタンスが変化しないことが保証されたアレイfirstIndex .. firstIndex+length、一定の部分を表すことになりながら、そう
class ArrayList {
val array :Array
val firstIndex :Int
val length :Int
var ownsPrefix :Boolean
var ownsSuffix :Boolean
}
：効果的に不変なデータ構造を実装するために成長しているバッファのトリックを適応させることは可能ですそのセクション内のコンテンツは、いくつかのインスタンス間で共有することができます。 追加の可変フラグownsPrefix、ownsSuffixは、インスタンスが最後の要素の最初または最後の後に配列の要素の内容を自由に変更できるかどうかを定義します（配列の対応する部分は構造によって使用されません）。その場合、使用可能なスペースが十分にあり、連結操作では、追加/追加されたリストの要素をバッファの適切なフラグメントにコピーし、対応するフラグをオフにし、配列の結合セクションを表す値を返します。今バッファーを所有しています。
これは、単一構造の繰り返し成長の最も一般的な使用例の問題を解決する簡単なトリックですが、実際には標準または一般的なライブラリで実装されていないことがわかりました。
私の質問は：それは名前を持っているのか、分析されているのか、それとも効率的なオープンソースの実装があるのでしょうか？私はそれを自分自身のためにスケーラで実装しています。ソースをオープンしたいのですが、ホイールを再開発することは嫌いで、既にそれについて発明された調整や最適化を組み込むことは喜んで行います。
私はそれらを調べますが、Triesと少し似ています。はるかに汎用性の高い構造が一般的ですが、このケースは1つのことをうまくやっていることでした。配列の繰り返しと索引付けはメモリと時間的には効率的ですが、ここでの目標は一般的に効率的な連結ではありませんでしたが、典型的な使用パターンを利用してシーケンスの効率的な構築を実現しました。怠け者の私（最初に石を投げるように弦を連結したことはない）。 – Turin
各ノードで可変のファンアウトを除いて、試行とフィンガーツリーの間には類似点はありません。フィンガーツリーは構造的にBツリーと似ていますが、最初と最後の要素にすばやくアクセスできる「フィンガー」といくつかの異なるバランスルールが追加されています。 – ephemient