たくさんのカウンターを備えたたくさんのスレッドがあります。スレッドはカウンターをデクリメントし、カウンターがゼロになると興味深いことが起こります。これは、アトミック ops で実装するのは簡単です。
ただし、スレッドまたはカウンターの数に関係なく、2 つのプロパティを保持する必要がある場合は、さらに難しくなります。
- スケーラビリティ: カウンターのデクリメントは O(ポリログ) です。
- コンパクトさ: カウンターあたりのメモリは O(1) です。
私はこれらのいずれかを単独で行う方法を知っています: 単純な実装はコンパクトで、階層的なカウントネットワーク [4] はスケーラブルです)。両方を行うことは可能ですか？
注: O(n) スレッドは、O(n) 未満の時間で O(n) 個の異なる変更 O(1) メモリを作成できないため、これを解決するには、異なるカウンター間でデータ構造を共有する必要があります。
[4]: J. Aspnes、M. Herlily、および N. Shavit。ネットワークを数えます。ACM のジャーナル、41(5):1020-1048、1994 年 9 月。
更新: Jed Brown は、O(1) 時間は不可能であるという明白な事実を指摘しました。ポリログに変更。