1

为简单起见，我将问题转换为员工/工资问题。

拥有员工记录emp，例如：

| id | salary (in 1000s) |

给定一个数字 ' num'，找到薪水 ' sal' 的员工数量在哪里salary<=sal（>=num类似于统计中的曲线下面积问题）。我们正在使用 Python 和 Sqlite，但问题并不特定于它们：

我正在做以下事情（天真的开始解决方案）：

num = some_num
sal = 1000 # starting miminmum value
count = 0
while count < num:
    sql = 'select count(*) from (select 1 from emp where salary<=? limit ?)' 
    # using limit so that we don't keep counting more than num - might help (?)
    (count,) = cursor.execute(sql, (sal, num)).next() # using apsw sqlite adapter
    sal += 1000

print sal

我们怎样才能使这更有效率？（使用标准 SQL 或等效的算法矿石，但不使用给定系统的怪癖）

或者：是否可以通过在记录中添加额外字段来提高效率，这些字段可以在插入/更新操作上保持最新而没有太多开销？

4

1 回答 1

1

如果您使用的是准备好的语句，我相信您可以将准备步骤移出循环以使其更快。

sql = 'select count(*) from (select 1 from emp where salary<=? limit ?)' 
# using limit so that we don't keep counting more than num - might help (?)
while count < num:
    (count,) = cursor.execute(sql, (sal, num))
    sal += 1000

如果您进一步想提高性能并且您的数据库大小相当小，您可以将整个数据加载到一个数组中并执行您的操作。

我认为如果先按薪水对数组进行排序，则可以进一步优化。之后，您可以对<条件翻转的位置执行二进制搜索等操作，该点的索引 + 1 将是计数。

编辑：

解决方案比看起来简单。如果记录按薪水排序，则#num'th记录的薪水将是所需的答案，因此这成为选择第 n 行的问题：

num = some_num
sql = 'select salary from emp order by salary limit 1 offset ?'
(sal,) = cursor.execute(sql, (num-1,)).next()
print sal
于 2012-12-14T05:45:04.287 回答