map vector

 标  题: [合集] map或vector进行搜索时的效率差别有多大？
发信站: BBS 水木清华站 (Wed May 12 18:58:19 2004), 站内

☆─────────────────────────────────────☆
   epoh (epoh) 于  (Sun Mar 14 16:36:19 2004)  提到:

我的程序要读入一些字符串，记录它们出现的次数
我每次读入一个字符串时，需要搜索已有记录，已有记录则+1，没有记录则添加一个记录


我的问题是，用什么来记录不同字符串的出现情况呢？

用map在搜索时效率会比用vector高很多吗？（如果用vector我就自己用iterator遍历，直
到发现有相同的字符串）


☆─────────────────────────────────────☆
   CtrlF (孤竹王子) 于  (Sun Mar 14 16:59:41 2004)  提到:

是不是
N         
- vs log N 
2       2
呀，
大侠指点吧
【 在 epoh (epoh) 的大作中提到: 】
: 我的程序要读入一些字符串，记录它们出现的次数
: 我每次读入一个字符串时，需要搜索已有记录，已有记录则+1，没有记录则添加一个记录
: 我的问题是，用什么来记录不同字符串的出现情况呢？
: 用map在搜索时效率会比用vector高很多吗？（如果用vector我就自己用iterator遍历，直
: 到发现有相同的字符串）




☆─────────────────────────────────────☆
   epoh (epoh) 于  (Sun Mar 14 17:09:08 2004)  提到:

我不确定map是否对记录排序。如果排序的话，搜索时应该是N/2  vs  log2（N）

但是如果每次加入新记录（也就是每次遇到新字符串时）之后都排序，这样效率也不高吧
？
如果是vector，加入新记录只要简单bush_back就可以了
但是如果是map，新记录加入后会有什么动作？
请指教

【 在 CtrlF (孤竹王子) 的大作中提到: 】
: 是不是
: N         
: - vs log N 
: 2       2
: 呀，
: 大侠指点吧
: 【 在 epoh (epoh) 的大作中提到: 】
: : 我的程序要读入一些字符串，记录它们出现的次数
: : 我每次读入一个字符串时，需要搜索已有记录，已有记录则+1，没有记录则添加一..
: : 我的问题是，用什么来记录不同字符串的出现情况呢？
: ...................



☆─────────────────────────────────────☆
   TOP30 (生是软件人，死是软件的死人) 于  (Sun Mar 14 17:14:26 2004)  提到:

还是用map吧，虽然我没有用过，不过我觉得这种情况应该用map。
【 在 epoh (epoh) 的大作中提到: 】
: 我不确定map是否对记录排序。如果排序的话，搜索时应该是N/2  vs  log2（N）
: 但是如果每次加入新记录（也就是每次遇到新字符串时）之后都排序，这样效率也不高吧
: ？
: 如果是vector，加入新记录只要简单bush_back就可以了
: 但是如果是map，新记录加入后会有什么动作？
                 会排序，不过很快，因为已经找到位置了。
: 请指教




☆─────────────────────────────────────☆
   Hyena2000 (小老虎（嗷嗷）^_^) 于  (Sun Mar 14 18:21:32 2004)  提到:

有的Map是采用平衡二叉树完成的，效率应该没有问题。

【 在 epoh (epoh) 的大作中提到: 】
: 我的程序要读入一些字符串，记录它们出现的次数
: 我每次读入一个字符串时，需要搜索已有记录，已有记录则+1，没有记录则添加一个记录
: 我的问题是，用什么来记录不同字符串的出现情况呢？
: 用map在搜索时效率会比用vector高很多吗？（如果用vector我就自己用iterator遍历，直
: 到发现有相同的字符串）




☆─────────────────────────────────────☆
   cpu8088 (wu) 于  (Sun Mar 14 18:56:27 2004)  提到:

当然使用map了，map的搜索效率是log2N，
如果vector是有序的话，那么它的搜索效率等同于map，
不过，考虑到需要向vector中加入新的字符串，如果还想要保持log2N
的搜索效率，就得考虑vector中插入字符串的问题，这是vector所忌讳的
，因为得移动插入点后面所有的元素，
而map则不存在这样的问题，插入的同时就保证了顺序，大多的map都以
平衡二叉树或类似的形式实现的，所以在处理这些问题时，效率很高的



【 在 epoh (epoh) 的大作中提到: 】
: 我的程序要读入一些字符串，记录它们出现的次数
: 我每次读入一个字符串时，需要搜索已有记录，已有记录则+1，没有记录则添加一个记录
: 我的问题是，用什么来记录不同字符串的出现情况呢？
: 用map在搜索时效率会比用vector高很多吗？（如果用vector我就自己用iterator遍历，直
: 到发现有相同的字符串）




☆─────────────────────────────────────☆
   epoh (epoh) 于  (Sun Mar 14 19:02:30 2004)  提到:

3x!说得很明白
【 在 cpu8088 (wu) 的大作中提到: 】
: 当然使用map了，map的搜索效率是log2N，
: 如果vector是有序的话，那么它的搜索效率等同于map，
: 不过，考虑到需要向vector中加入新的字符串，如果还想要保持log2N
: 的搜索效率，就得考虑vector中插入字符串的问题，这是vector所忌讳的
: ，因为得移动插入点后面所有的元素，
: 而map则不存在这样的问题，插入的同时就保证了顺序，大多的map都以
: 平衡二叉树或类似的形式实现的，所以在处理这些问题时，效率很高的
: 
: 
: 
: ...................



☆─────────────────────────────────────☆
   marxlee (Guide me with your grace) 于  (Sun Mar 14 19:02:41 2004)  提到:

建议使用hash table ，这样会快非常多。

【 在 epoh (epoh) 的大作中提到: 】
: 我的程序要读入一些字符串，记录它们出现的次数
: 我每次读入一个字符串时，需要搜索已有记录，已有记录则+1，没有记录则添加一个记录
: 我的问题是，用什么来记录不同字符串的出现情况呢？
: 用map在搜索时效率会比用vector高很多吗？（如果用vector我就自己用iterator遍历，直
: 到发现有相同的字符串）




☆─────────────────────────────────────☆
   RoachCock (chen3feng) 于  (Sun Mar 14 19:05:46 2004)  提到:

hash不是标准库里的东西

【 在 marxlee (Guide me with your grace) 的大作中提到: 】
: 建议使用hash table ，这样会快非常多。




☆─────────────────────────────────────☆
   marxlee (Guide me with your grace) 于  (Sun Mar 14 19:07:20 2004)  提到:

但在这里效率会非常高
【 在 RoachCock (chen3feng) 的大作中提到: 】
: hash不是标准库里的东西




☆─────────────────────────────────────☆
   RoachCock (chen3feng) 于  (Sun Mar 14 19:32:15 2004)  提到:

比map高一些,单数数据量不大的话显不出什么优势

【 在 marxlee (Guide me with your grace) 的大作中提到: 】
: 但在这里效率会非常高