为了简单起见,我将这个问题转化为雇员/工资问题。
具有员工记录emp
,例如:
| id | salary (in 1000s) |
给定一个数字'num
',找到salary '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或等效的,但不使用给定系统的怪癖)
或者:可以通过向记录添加额外的字段来使其更有效,这样就可以在插入/更新操作中保持最新,而不会有太多的开销?
1条答案
按热度按时间lsmd5eda1#
如果您使用的是预准备语句,我相信您可以将准备步骤从循环中移走,以使其更快。
如果您希望进一步提高性能,并且数据库大小相当小,则可以将整个数据加载到一个数组中并执行操作。
我认为如果你先按薪水对数组进行排序,那么进一步的优化是可能的,然后你可以做一些事情,比如二进制搜索,搜索到
<
条件翻转的地方,那个点的索引+1就是计数。解决方案比看起来要简单,如果记录是按salary排序的,那么
#num'th
记录的salary就是我们想要的答案,所以这就变成了selecting the n'th row的一个问题: