python - スキップリストの実装方法

Question

Pythonでスキップリストを実装する方法を考えていました。

リンク リストを作成しましたが、リンク リストのさまざまなレベルを作成する方法と、ノードを検索またはリストに挿入するときにリストのすべてのレベルを反復処理する方法に問題があります。

Answer 1

John Shipman の適切に書かれた pure-Python implementationを読むことができます。これには、トップレベルの設計からクラスの実装方法まで、彼がそれをどのように構築したかについての詳細な説明も含まれています。インターフェース。

複数の追加実装があるPyPIを検索することもできます。

または、ウィキペディアのエントリまたは元の論文を読むことができます。どちらにも詳細な説明と、Python に変換できる疑似コードが含まれています。

あなたの既存の質問はあまりにも一般的です。しかし、関連情報を読んだ後、特定の質問がある場合 (「Shipman のコードのこの部分は何をするのか」、「Pugh の論文のこの疑似コード行は何を意味し、どのように Python に変換すればよいのか」、「正確には何をするのか」は「カット リスト」です」など）、SO で質問できます。