|
|
本帖最后由 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
源代码下载链接：
|
|
|手机版|小黑屋|Lazarus中国|Lazarus中文社区
( 鄂ICP备16006501号-1 )
发表于 2014-1-20 23:21:40
发表于 2014-1-21 10:08:34