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

[Chen Shuo]

我没用过 VC 6 :)

VC 最早用的 7.1 (2003) 版，其他 C++ 编译器倒用过一些(bcc55、g++)。

On 3/22/06, 李慧霸 <magazine.lihuiba at 163.com> wrote:
> 我猜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
>
>
> _______________________________________________
> Cpp mailing list
> Cpp at codingnow.com
> http://codingnow.com/mailman/listinfo/cpp
>