Re: Re: [cpp] 这样的数据如何存储，使查询插入最快？

[李慧霸]

我猜xw是说几万吧。
如果插入和检索的频率数量级相当，还是用set好些，插入和检索都是log级别的，而且set确保元素都是排好序的。

ps:
我以前在vc6里面用std::partition好像结果有点问题，不过当时没有细看，不知道你遇到过没有？

------------------				 
李慧霸
2006-03-22

-------------------------------------------------------------
发件人：Chen Shuo
发送日期：2006-03-22 15:34:43
收件人：
抄送：
主题：Re: [cpp] 这样的数据如何存储，使查询插入最快？


没看懂"XW 这个数量级"是什么意思，我觉得你可以写个程序对比一下。另外要看你查询的频率有多高，才能决定用哪种优化。
另外插入快和查询快本身是矛盾的需求，如果你在插入的时候多做点工作（比如更新索引），那么插入变慢，查询就快；如果插入的时候只是放到那里，那么插入就快，查询变慢。看你怎么取舍了。

On 3/22/06, ZiDing <xuziding at gmail.com> wrote:
> 在 Wed, 22 Mar 2006 14:48:38 +0800，Chen Shuo <giantchen at gmail.com> 写道:
>
> 这个方案不错，但是数据量很大的情况下（因为这个数据量应该是在 XW 这个数量级
> 别上），
> vector<DataType>::iterator it = partition(table.begin(), table.end(),
> PredOne()); // linear time
> 这里会消耗不少的时间，这个和我第二个方案比起就是多了这部分的时间，但是比我
> 的要方便多了，崇拜一个，高人啊。
> 不知道还有没有更好的办法呢？我只是需要查询和插入的时候快就OK了，还有没有其
> 他的优化方法呢？
>
> > typedef unsigned int ValueType;
> > typedef unsigned int TimeType;
> > pair<ValueType, TimeType> DataType;
> > vector<DataType> table;
> > table.push_back(...);
> > vector<DataType>::iterator it = partition(table.begin(), table.end(),
> > PredOne()); // linear time
> > sort(table.begin(), it, PredTwo()); // N log N
> > Where PredOne and PredTwo are two functors, and have obvious behaviors.
> > Get result from range [table.begin(), it)
>
>
>
> --
> 使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/
>
>
> _______________________________________________
> Cpp mailing list
> Cpp at codingnow.com
> http://codingnow.com/mailman/listinfo/cpp
>
>

_______________________________________________
Cpp mailing list
Cpp at codingnow.com
http://codingnow.com/mailman/listinfo/cpp