问题标签 [top-n]

由于没有更好的名称，我将我正在寻找的数据结构称为“TopScoreMap”。这是要求。首先，地图的大小是固定的。例如，该地图只需要保留将在该地图上抛出的前 n 个条目。就其键而言，排在前 n 位。由于地图应按其键排序，因此我选择基于java.util.TreeMap. 以下是我已经实施的。这已经通过了一些测试用例。我的问题是：

1. 是否存在提供此功能的现有数据结构？

2. 如果没有，有没有办法在执行时避免迭代put？看起来像 O(n^2)，最坏的情况。

我希望在 Postgres 服务器上提取总和值的前 10%。

所以我用 sum(transaction.value) 对一个值求和，我想要前 10% 的值

我在 SQL Server 2008 数据库中有一个非常大的表，包含 4000 万行。

我正在尝试优化以下查询的性能：

为了做到这一点，我在 CONTRACT_NUMBER、INVOICE_NUMBER 和 CUSTOMER_NAME 列上构建了一个包含索引。

查询仍然需要 3 秒到 10 秒才能执行。从查询执行计划中，我看到索引查找操作消耗了总工作量的大约 30%，而排序（前 N）操作消耗了另外 70%。知道如何优化此查询，最好响应时间小于 1 秒？注意：我还尝试在索引列中包含 [Unique_ID] 列。在这种情况下，查询执行计划正在执行索引扫描，但是有很多用户查询数据库，我遇到了同样的问题。

假设我有这样的熊猫数据框：

我想获得一个新的 DataFrame，每个 id 都有前 2 条记录，如下所示：

我可以通过以下方式对组内的记录进行编号：

但是有没有更有效/优雅的方法来做到这一点？还有更优雅的方法来对每个组中的记录进行编号（如 SQL 窗口函数row_number()）。

考虑在一组 N 个独立且同分布的浮点值中找到前 k 个元素的任务。通过使用优先级队列/堆，我们可以对所有 N 个元素进行一次迭代，并通过以下操作维护一个 top-k 集合：

• 如果元素 x 比堆头“差”：丢弃 x ⇒ 复杂度 O(1)

• 如果元素 x 比堆的头部“更好”：移除头部并插入 x ⇒ 复杂度 O(log k)

这种方法最坏情况的时间复杂度显然是O(N log k)，但是平均时间复杂度呢？由于 iid 假设，O(1) 操作的概率随着时间的推移而增加，我们很少需要执行代价高昂的 O(log k)，尤其是对于 k << N。

这个平均时间复杂度是否记录在任何可引用的参考资料中？平均时间复杂度是多少？如果您的答案有可引用的参考资料，请附上。

mysql表中的以下数据。

如何GROUP_CONCAT在每个品牌中找到前 5 个具有功能的图片？我想得到以下回报：

MySql 表中的以下数据。

我如何GROUP_CONCAT在每个品牌中找到前 5 个具有功能的图像我想跟随返回

以下查询提供预期结果

我在表和brand_id，image_id中有大量数据大约有200万条记录，每个用户下载都会重复，所以当我运行查询时出现以下错误

我认为超出了 GROUP_CONCAT 范围，请您提供解决方案，以便我在每个品牌中仅获得前 5 名下载，因此不需要 SUBSTRING_INDEX 功能。

谢谢

我有一张表客户，其中有一个字段“名称”，其中包含 a 到 z 名称记录。

我使用 asc 查询从 a 到 z 获取记录

但是我怎样才能得到 5 条记录，这些记录以所有 a 到 z 字母开头，只有一个查询？

输出：

1. 一种

2. 一种

3. 一种

4. 一种

5. 一种

6. b

7. b

8. b

9. b

10. b 以此类推到 z。提前致谢。

我使用以下查询从类别表中选择类别名称

查询正在运行 此查询的结果是

我只想选择最多的类别名称，这里我只需要电子产品。如何获得这个。在此先感谢您的帮助...>>

我有一个看起来像这样的大表（数百万条记录）。我需要每天获得前 30%（或第 70 个百分位）。所以结果应该看起来像节表。该表已经Bread_Date按升序排序，并且consumption_per_eater值已经按降序排序。

我知道这类似于 top-N 问题，我可能需要将其写为select语句的一部分：

if(@preBread_Date 为 null 或 @preBread_Date != Bread_Date, @row:=1, @row:=@row+1) as 'row', @preBread_Date := Bread_Date

但我被困住了。我不知道该写什么，因为每天都有不同数量的记录。所以在下面的例子中，2012-07-10 只有 3 条记录，而 2012-07-11 有 6 条不同的记录，2012-07 有 4 条记录。我想避免的一件事是任何加入。

如果有人能告诉我接下来需要写的查询，我将不胜感激。提前致谢。

面包日期 | Consumption_Per_Eater
.................................................. .....................
2012-07-10 | 300.1
2012-07-10 | 290.9
2012-07-10 | 230.5
2012-07-11 | 230.3
2012-07-11 | 340.1
2012-07-11 | 330.9
2012-07-11 | 230.5
2012-07-11 | 210.3
2012-07-11 | 209.4
2012-07-12 | 400.9
2012-07-12 | 300.5
2012-07-12 | 210.3
2012-07-12 | 200.4

面包日期 | Top_30%_of_that_day
..................................... ...................................
2012-07-10 | XXXXXXX
2012-07-11 | XXXXXXX
2012-07-12 | XXXXXXX