Lazarus中文社区

 找回密码
 立即注册(注册审核可向QQ群索取)

QQ登录

只需一步,快速开始

Lazarus IDE and 组件 下载地址版权申明
查看: 2348|回复: 3

2014新年社区比赛,按猫工公布的错误条件做的程序,包括源代码!

[复制链接]

该用户从未签到

发表于 2014-1-20 23:21:40 | 显示全部楼层 |阅读模式
本帖最后由 aaa 于 2014-1-23 12:34 编辑

想了2天,头都痛了。好多个不同的想法都不现实,只有经典的位图索引是我想到的最现实的方法。
哎,真不知道algo是怎么搞的?但我觉得也许不会有比位图索引更好的方法吧。
但algo,又特别强调了,6个一组,还有啥概率。无语了。。。。


下面的方法完全错误的哦。各位但看个笑话吧。我也不删贴了,记录下以后看看来也是好的。
-----------------
猫工发的题目是300个bool条件,100万条数据,随机查询。
但algo原题目是1800个bool条件,6个一组随机,共300个条件查询。

所以我的代码是有点错误的。但不太合适algo的原题,因为原题目6个条件是分组的,而数据也是固定的100w条,那么我考虑可用index[6]/[6]/[6]/[6]/[6]/[6]/[6]/[6]/[...]这样的优化索引结构。效率应该会更高,有待测试

但是,我这个代码是很通用,扩展一下就能用于更多此类情况。完全随机的情况也是可以的。所以也别浪费了,贴上来。

解题思路:
按照题目,要进行300次比较,因此,我的优化方向就是减少比较次数。

1、从Linux系统中文件权限得到启发,将63bit作为一个整体,存为一个8Byte 数字类型。没有用64bit时因为我采用的Sqlite数据库,不支持无符号数。300位就要使用5个8Byte的数值。其中最后一个8Byte数值,只用前47位,后面补零。

2、采用SQLite数据库存储,建立一个表格:
CREATE TABLE table1 (indexid INTEGER PRIMARY KEY, f1 NUMERIC, f2 NUMERIC, f3 NUMERIC, f4 NUMERIC, f5 NUMERIC)
为了提高效率,在f1到f5列建立索引。

3、这样一来,每次查询由300次比较,变为5次,那么按题目百万条数据量,只要小几百MB就可以存储了,应该能够满足需求。(由于我的电脑太差,麻烦帮我测试一下。)

-------------
进一步优化:
使用内存数据库。
由于要求中内存小于6GB就可以,那么可以考虑使用SQLite内存数据库来存放数据。这个好像Lazarus的控件不支持,得再研究一下。

------------
再进一步优化:
不使用数据库。
考虑到Lazarus数据库控件带来的性能损失,考虑每次查询必须的SQL语句分析带来的性能损失,自定义一个仅需查询的索引是可行的。
但这里由于我的技术水平限制,给我带来2个问题!
第一、在整个查询中,SQL语句分析带来的系统开销很小。那么,我实现的数据结构能否比SQLite实现的还要高效??
第二、Freepascal本身的会比C语言慢一些(记得有资料说是10%到15%,不确定,但慢一点是肯定的),那么,纯Freepascal代码的性能损失能弥补性能获得么??
-------
最后优化:
我还想到一个优化方法,就是采用SSE编码。
当然这个是必须采用我最开始的思路,并自己实现查询索引的情况下。SSE好像能够支持128bit减法,那么3个数即可存储300位信息,比较次数少了2次!性能应该会高30%以上吧。可惜,这个SSE我只是听说过,不会用。Freepascal编译器是支持的。

可执行文件:http://pan.baidu.com/s/1dDoW8TF
源代码下载链接:
游客,如果您要查看本帖隐藏内容请回复

回复

使用道具 举报

该用户从未签到

发表于 2014-1-20 23:31:47 | 显示全部楼层
看看,貌似很厉害得样子
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2014-1-21 10:08:34 | 显示全部楼层
谢谢指正...
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2014-1-21 10:10:56 | 显示全部楼层
回复 支持 反对

使用道具 举报

*滑块验证:

本版积分规则

QQ|手机版|小黑屋|Lazarus中国|Lazarus中文社区 ( 鄂ICP备16006501号-1 )

GMT+8, 2024-6-22 05:52 , Processed in 0.030903 second(s), 9 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表