问带滤波的大型排行榜排名

EN

这是一个非常有趣的问题--谢谢你的发帖。在一般情况下，数据库擅长这种类型的问题，其中有大量的数据需要过滤和搜索。我的第一个猜测是，您没有正确地使用MySQL索引。话虽如此，您显然需要定期在有序列表中找到第n行，这是SQL根本不擅长的事情。

如果您正在寻找某种形式的内存数据库，那么您将需要一些比REDIS更复杂的东西。我建议你看看VoltDB，它速度很快，但不便宜。

如果您想要构建您自己的内存存储，那么您需要计算内存使用量，以确定它是否可行。对于要搜索或筛选的每一行，您将需要一个索引(在这个答案的后面讨论)，以及每个用户的记录。然而，即使对于1000万行和20个字段，它仍然小于1Gb内存，这在现代计算机上应该是很好的。

现在是数据结构。我相信你在正确的轨道上使用地图到列表。我不认为列表需要排序-你只需要能够得到一组特定价值的用户。事实上，集合可能更合适(同样值得测试性能)。下面是我的建议：(我刚刚添加了国家和年龄字段-我认为您需要其他字段，但这是一个合理的示例)：

enum Country {
    ...
}

class User {
    String givenName;
    String familyName;
    int xp;
    Country country;
    int age;
}

class LeaderBoard {
    Set<User> users;
    Map<Integer, Set<User>> xpIndex;
    Map<Country, Set<User>> countryIndex;
    Map<Integer, Set<User>> ageIndex;
}

当字段发生变化时，需要更新每个索引。例如：

private setUserAge(User user, int age) {
    assert users.contains(user);
    assert ageIndex.get(user.getAge()).contains(user);
    ageIndex.get(user.getAge()).remove(user);
    if (!ageIndex.containsKey(age)) {
        ageIndex.put(age, new TreeSet<>());
    }
    ageIndex.get(age).add(user);
    user.setAge(age);
}

让满足给定组合的所有用户，按等级排列，可以通过以下几种方式实现：

countryIndex.get(Country.Germany).stream()
    .filter(ageIndex.get(20)::contains)
    .sorted(User::compareRank)
    ...

或

SortedSet<User> germanUsers = new TreeSet<>(User::compareRank);
germanUsers.addAll(countryIndex.get(Country.Germany));
germanUsers.retainAll(ageIndex.get(20));

您需要检查其中哪个更有效--我猜流实现会更高效。而且，它可以很容易地转换为一个paralellStream。

您提到了对更新效率的关注。如果这是一个问题，我会非常惊讶，除非有许多更新一秒钟。通常，使用这些类型的应用程序，您将获得比写入更多的读取。

我认为没有理由像您所建议的那样手动划分索引，除非您将有数亿个条目。最好是用HashMap和TreeMap进行实验，以便具体地实例化索引。

如果需要更好的性能，下一个明显的增强是多线程应用程序。这不应该太复杂，因为您需要同步相对简单的数据结构。当然，在搜索中使用并行流会有所帮助(而且在Java 8中是免费的)。

因此，我的建议是使用这些简单的数据结构，并在尝试任何更复杂的实现之前，使用多线程和调整具体实现(例如哈希函数)来提高性能。

虽然我仍然处于基准的中间，但我正在更新目前的发展状况。最好的性能比率出现在使用：

Map<Country, Map<Age, Map <TimingIdentifier, List<User>>>> (列表被排序)

键上的一些注释:我添加了一个名为World的国家，以便有一个完全独立于领导委员会的国家的实例(就好像没有选择国家过滤器一样)。我对年龄(所有年龄)和TimeIdentifier (全时)也是如此.TimeIdentifier键值为全时、月、周、日。

上述内容可以扩展到其他过滤器，因此也可以应用于其他场景。Map<Filter1,Map<Filter2,Map<Filter3,Map<Filter4 ..other Map Keys here..,List<User>>>>

更新:与使用多个Map包装器不同，在带有上述字段的单个Map中用作键的类稍微快一些。当然，我们需要一个类似于多吨的模式来创建所有可用的FilterCombination对象：

class FilterCombination {
    private int CountryId;
    private int AgeId;
    private int TimeId;
    ...
}

然后定义Map<FilterCombination, List<User>> (排序列表)

我可以使用TreeSet，但我没有。为什么？基本上是在寻找订单统计树(参见这里)，但似乎没有官方的这里实现(参见这里)。由于List.add(index, Object)效率低下，即O(n)，这可能是相对于排序列表的一种方式。LinkedList对.add(index, Object)可能更好，但不幸的是，它在获取k元素(排名为O(n))方面进展缓慢。因此，每一种结构都有其利弊。

目前，我最终使用了一个排序列表。原因是在向排序列表中添加元素时，我使用了稍微修改过的二进制搜索算法(请参阅这里)。上述方法给出了当前用户在插入阶段的排名(不需要额外的搜索查询)，即O(logn + n) (二进制搜索索引+List.add(索引，对象))。

还有其他结构比O(logn + n)的插入+排序更好吗？

*当然，如果以后需要查询用户的排名，我将再次根据用户的XP (如您在下面看到的时间戳)进行二进制搜索，而不是Id，因为现在我无法通过列表中的用户Id进行搜索)。

**作为比较国，我使用以下标准

第一: XP点数

在第二次抽签的情况下:上次XP更新的时间戳。

因此，排序列表中的等式极有可能非常少。更重要的是，如果两个使用相同XP的用户被按相反顺序排列的话，我也不会介意(即使用我们数百万个游戏的样本数据，我也发现了很少的领带，不包括我根本不在乎的零XPs )。

XP更新程序需要一些工作和资源。幸运的是，第二个比较标准显著改进了这个列表中的用户搜索(再次进行二进制搜索)，因为在更新用户的XPs之前，我必须删除列表中该用户的先前条目.但是我通过她以前的XPs和时间戳来看，所以它是log(n)。

最简单的选择是选择Redis的排序集，并使用主从复制。在每个从站上打开RDB，并将RDB文件备份到S3。使用卡夫卡，坚持所有的写作之前，他们去红。这样我们就可以稍后重播丢失的事务了。