31

一部の C++ コードを Python に移植していますが、データ構造の 1 つがマルチセットですが、これを Python でモデル化する方法がわかりません。

msC++にしましょうmultiset<int>

使い方ms（いくつかの例を掲載）

multiset<int>::iterator it = ms.find(x)
ms.erase(it)

ms.insert(x)
ms.end()
ms.lower_bound(x)
ms.clear()
4

5 に答える 5

8

あなたの基準に合うソートされたリストのデータ型の実装がいくつかあります。2 つの一般的な選択肢は、SortedContainersとblistモジュールです。これらの各モジュールは、ソートされた順序で要素を自動的に維持し、高速な挿入と下限/上限のルックアップを可能にするSortedListデータ型を提供します。役立つパフォーマンス比較もあります。

SortedContainers モジュールの SortedList 型を使用した同等のコードは次のようになります。

from sortedcontainers import SortedList
sl = SortedList()

# Start index of `x` values
start = sl.bisect_left(x)

# End index of `x` values
end = sl.bisect_right(x)

# Iterator for those values
iter(sl[start:end])

# Erase an element
del sl[start:end]

# Insert an element
sl.add(x)

# Iterate from lower bound
start = sl.bisect_left(x)
iter(sl[x] for x in range(start, len(sl)))

# Clear elements
sl.clear()

これらの操作はすべて、並べ替えられたリストのデータ型で効率的に機能する必要があります。

于 2014-04-28T18:53:49.697 に答える
8

ありません。Python の標準ライブラリを参照してください- バランスの取れたバイナリ ツリーのモジュールはありますか? Pythonの C++ ツリー コンテナー ( map、set、 ) に相当するものの一般的な説明についてはmultimap、 を参照してください。multiset

私が考えることができる最も近いのは、整数をカウント（整数も）にマッピングする辞書を使用することです。ただし、これではキーが順番に取得されないため、を使用して検索することはできませんlower_bound。別の方法は、他の人がすでに提案しているように、順序付きリストを使用することです。おそらく（整数、カウント）タプルのリストですか？すべての挿入を行った後にのみ検索する必要がある場合は、構築のための一時的な構造として辞書を使用し、すべての挿入を行った後にリストを作成し、そのリストを検索に使用できます。

于 2013-06-27T15:39:51.917 に答える
3

bisect関数を使用して、リストの順序を維持できます。たとえばfind、

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

docs で他の同等物を見つけることができます。チェックする代わりにend、ValueError

于 2013-06-27T15:30:37.837 に答える