java - 自定义数据结构(元素+权重)

Question

我应该使用哪种数据结构来保持元素按给定权重排序？我需要在集合中添加元素，其中每个元素都会生成特定的权重，但该权重不包含(也不计算)在元素本身内部；它是由元素之外的其他人计算的。而且，权重不需要存储(但如果需要的话可以存储)，它只是一个插入参数，用于将元素放在正确的位置。

我的具体用例是对音乐轨道进行排序。我有一个轨道列表和一个适用于每个轨道的规则列表。我迭代每个轨道，然后规则列表在给定当前轨道的情况下生成“分数”。我想将轨道添加到给定生成分数的“集合”中，这样​​我就可以选择分数最高的第一首轨道。

我看不出在 Java 中使用哪种数据结构。我必须自己实现一个新的吗？我最好的猜测是一种堆数据结构，但我无法弄清楚具体是哪一种。

编辑:重量在开始时只计算一次。我无法提供“比较器”，因为它会比较轨道，并且我无法在“compareTo 方法”上计算他们的分数。该算法可能如下所示:

 public Track determineNext() {
     MyStructure<Track> trackScores;
        for (Track track : tracks) {
            int score = 0;

            for (Rule rule : rules) {
                score += rule.applyScoreOn(track);
            }

            trackScores.add(track, score);
        }
     return trackScores.first();
 }

我希望你能明白。

Answer 1

在我看来， PriorityQueue 正是您所需要的:

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

在这种情况下，自然排序将按分数排序。简单。

至于你的观点:

I can't provide a "comparator" since it will compare Tracks, and I can't calculate their score on a "compareTo method".

这里的关键是你不使用compareTo()计算分数的方法。恰恰相反。您在执行 compareTo() 时使用分数.

<小时/>

您有几种方法可以实现这一点:

1. 制造Track implements Comparable<Track> ，并实现compareTo(Track t)比较您获得的分数，因此更高的分数-->“更大”的对象。 PriorityQueue我们会处理剩下的事情。
2. 实现 Comparator<Track>其作用与 compareTo() 基本相同对于选项 1 也是如此。

如果您稍后可以在程序中使用不同的标准进行排序，则选项 2 更好，因为您不 promise 拥有 Track仅按分数排序。

理想情况下，对于这两个选项，您都可以将分数存储在 Track 中，因为分数只需要计算一次；但是，您必须确保在插入 PriorityQueue 之前设置此分数。 。但这不应该是一个问题。

或者，如果您知道分数不会随时间变化，则可以在比较方法中动态计算分数；不过，如果必须进行大量比较，随着时间的推移，这可能会变得有些昂贵。如果您知道分数不会改变，我不会推荐这样做。

<小时/>

或者，如果 Track对象不知道它们的分数(这是有道理的)，您可以使用 Map与 Track s 作为键，scores 作为值来关联 Track得分:

HashMap<Track, Integer> scoreMap = new HashMap<>();
for (Track track : tracks) { // Copied from question, slightly altered
    int score = 0;

    for (Rule rule : rules) {
        score += rule.applyScoreOn(track);
    }

    scoreMap.put(track, Integer.valueOf(score));

现在您可以使用比较器从此 map 中提取分数

public class TrackComparator implements Comparator<Track> {
    private final Map<Track, Integer> scores;

    public TrackComparator(Map<Track, Integer> scores) {
        this.scores = scores;
    }

    @Override
    public int compare(Track t1, Track t2) {
        // Check to see if tracks are in map if you didn't pre-fill map
        // Get scores, compare, return
    }
}

不过，有一些注意事项:

• Map通常需要您定义其他方法( hashCode() 除了 equals() 的 HashMap ，以及 TreeMap 的某种形式的比较器)
• map 的键不应该是可变的，尽管 Track对象我真的不认为这是一个问题
• 你得到另一个集合来消耗内存。但是，如果您的分数在 [-128, 127] 范围内，那应该不是什么太大的问题。也可以传递 VM 标志来扩展此范围。我不会太担心内存消耗，除非你有大量的轨道或几个不同的 map 。
• 仅在外部更改映射的值不会对优先级队列重新排序。您必须删除()和添加()“分数”发生变化的对象，才能将其移动到队列中的新位置。

我不太确定Map解决方案是最好的解决方案，但我认为远非最差，而且本身应该相当不错。

帮助解决内存问题的一个可能的更改是将 Map里面Comparator ，并让比较器本身计算分数(如果需要)，并在轨道不存在时将它们添加到 map 中。这取决于您是否关心某些分数比其他分数晚“卡住”。这可能会对性能产生不利影响，但这是一个很大的猜测。