1

問題：

1) I have buckets of fixed size, in my case 64. This cannot change.
2) Values vary in size, but are never bigger than a bucket (64).
3) Access is much slower if any element is split between buckets.

バケット内の要素の最適な順序を計算するアルゴリズムはありますか？

ここには2つのバリエーションがあり、コードのユーザーが速度とメモリ使用量のどちらかを選択できるようにするために、両方に興味があります。

A) Splitting is allowed, but should be minimized.
B) Splitting is not allowed, and padding should be minimized.

アルゴリズム、またはそれらへのリンク、あるいは「よく知られている」場合は少なくともそれらの名前を投稿してください。インターネット検索では、おそらく、最適なバケットサイズやハッシュテーブルでのデータの分割など、無関係な結果に答えが溺れてしまったために、有用なものは何も返されませんでした。

対象言語はJavaですが、違いはないと思います。

4

1 に答える 1

2

ファーストフィット、ベストフィット、ワーストフィットなどのメモリ割り当てアルゴリズムを使用できると思います（ここでそれらについて読むことができます）：これらは最適解のヒューリスティック近似にすぎませんが、元の問題はビンに関連していると思われます-パッキング問題はどういうわけか、NP困難かもしれません-最適に解決するのは難しいです。近似アルゴリズムを使用してみてください。それなしでは要素を配置できない場合にのみ分割してください。

于 2012-06-17T08:33:56.147 に答える