7

Python クラスには、次に示す 6 つの要件があります。太字の用語のみが要件として読み取られます。

  1. 次の 4 つの操作の多くで、O(1)に近いパフォーマンス。
  2. オブジェクトをコンテナに挿入する際にソート順を維持します。
  3. オブジェクトに含まれる最後の値 (最大値)を覗く機能。
  4. 両側でポップを許可します(最小値または最大値を取得します)。
  5. 格納されているオブジェクトの合計サイズまたは数を取得する機能。
  6. Pythonの標準ライブラリのコードのような既製のソリューションであること。

以下は、歴史的な理由からここに残されています (好奇心を助け、研究が行われたことを証明します)。

Python の標準ライブラリ (具体的にはデータ型に関するセクション) を調べた後でも、断片化テーブルの要件要件を満たすクラスをまだ見つけていません。collections.deque必要なものに近いですが、それに含まれるデータをソートしたままにすることはサポートされていません。以下を提供します。

  1. O(1) パフォーマンスで両端キューの両側に効率的に追加およびポップします。
  2. オブジェクト内に含まれるデータの両側でポップします。
  3. 内部に含まれるオブジェクトの合計サイズまたは数を取得します。

リストを使用して非効率的なソリューションを実装するのは些細なことですが、適切に機能するクラスを見つけることははるかに望ましいことです。上限のない増大するメモリ シミュレーションでは、このようなクラスは、空の (削除された) セルのインデックスを保持し、断片化レベルを低く抑えることができます。bisectモジュールが役立つ場合があります。

  1. 配列に新しいオブジェクトを挿入する際に、配列をソート順に保つのに役立ちます。
  2. オブジェクトが追加されたときにリストをソートしておくための既製のソリューション。
  3. 実行すると、配列内の最後の値array[-1]を覗くことができます。

要件を完全に満たすことができず、最も見込みがないと思われる最終候補はheapqモジュールでした。効率的な挿入のように見えるものをサポートし、それarray[0]が最小値であることを保証する一方で、配列は常に完全にソートされた状態にあるとは限りません。これほど役立つものは他にありませんでした。

これらの 6 つの要件に近いPython のクラスまたはデータ構造を知っている人はいますか?

4

3 に答える 3

12

要件は次のようです。

  1. O（1）両端からポップ
  2. 効率的len
  3. 並べ替え順
  4. 最後の値をのぞく

両端キューを回転し、一方の端に追加し、回転を解除するdequeカスタムメソッドでを使用できます。insert

>>> from collections import deque
>>> import bisect
>>> class FunkyDeque(deque):
...     def _insert(self, index, value):
...             self.rotate(-index)
...             self.appendleft(value)
...             self.rotate(index)
...
...     def insert(self, value):
...             self._insert(bisect.bisect_left(self, value), value)
...
...     def __init__(self, iterable):
...             super(FunkyDeque, self).__init__(sorted(iterable))
...
>>> foo = FunkyDeque([3,2,1])
>>> foo
deque([1, 2, 3])
>>> foo.insert(2.5)
>>> foo
deque([1, 2, 2.5, 3])

要件1、2、および4はすべて、基になるデータ構造が両端キューであるという事実に直接準拠しており、データの挿入方法のために要件3が成立することに注意してください。（もちろん、egを呼び出すことでソート要件をバイパスできることに注意してください。ただし、それは重要ではありません_insert。）

于 2010-11-04T15:35:24.880 に答える
9

katrielalex次の Python クラスにつながるインスピレーションを提供してくれた に感謝します。

import collections
import bisect

class FastTable:

    def __init__(self):
        self.__deque = collections.deque()

    def __len__(self):
        return len(self.__deque)

    def head(self):
        return self.__deque.popleft()

    def tail(self):
        return self.__deque.pop()

    def peek(self):
        return self.__deque[-1]

    def insert(self, obj):
        index = bisect.bisect_left(self.__deque, obj)
        self.__deque.rotate(-index)
        self.__deque.appendleft(obj)
        self.__deque.rotate(index)
于 2010-11-04T16:45:59.820 に答える
2

blist.sortedlist

  1. 次の 4 つの操作の多くで、O(1) に近いパフォーマンス。
  2. オブジェクトをコンテナに挿入する際にソート順を維持します。
  3. オブジェクトに含まれる最後の値 (最大値) を覗く機能。
  4. 両側でポップを許可します (最小値または最大値を取得します)。
  5. 格納されているオブジェクトの合計サイズまたは数を取得する機能。
  6. Python の標準ライブラリのコードのような既製のソリューションであること。

B+ツリーです。

于 2010-12-04T08:31:04.857 に答える