84669 person learning
152542 person learning
20005 person learning
5487 person learning
7821 person learning
359900 person learning
3350 person learning
180660 person learning
48569 person learning
18603 person learning
40936 person learning
1549 person learning
1183 person learning
32909 person learning
现有10w级的数据量,需求频繁的查询,频繁排序,该如何设计好的数据结构?因为数据变化频繁,初步考虑用map映射表索引查询,修改数据,但是修改之后数据又要根据一定的规则重新排序,显然map又不适用。如果采用vector容器可以解决排序,但查询修改数据的效率太过低下了,现在纠结该如何提高效率?用list不知道如何?大概的数据结构如下:
struct { int index; std::string name; }
由于学艺不清,在此请教各位前辈。
人生最曼妙的风景,竟是内心的淡定与从容!
感觉是用树 来解决
1、首先查询,最差的情况是O(n),最好的情况是O(1),O(n)只需要一个线性的结构就可以了,数组、链表都ok,想要达到O(1),就像你说的,必须用空间换时间,哈希表是一种常见做法。除此之外还有一些时间复杂度居中的结构,二分查找是一种常见的做法,可以很方便的把原本需要O(n)的结构加速成O(lgn),数组、链表、树都可以采用这种做法;2、然后是修改,修改其实是先查询,再修改,查询的时间复杂度已经说过了,具体数据修改的复杂度得看你的数据是什么样的;3、最后是排序,排序的时间复杂度已经被说烂了,基于比较的排序算法的时间复杂度下限是O(nlgn),有多种结构可以实现它。看你的需求想要做快速查询,然后想要做实时排序。假定你的修改是多于查询的,建议查询不必追求O(1),排序求一个下限,用堆或者跳表的结构可以达到目的。假如你的查询是频繁的,修改是少量的,那么可以建立一个哈希表用于查询,排序直接用数组二分甚至用链表都可以。
C++中std::map是用红黑树实现的,也就是输出时按key排序好。为什么会
但是修改之后数据又要根据一定的规则重新排序,显然map又不适用?
如果需要多种排序方式,是不是可以每一种排序都用一个std::map来保存相应的引用?
感觉是用树 来解决
1、首先查询,最差的情况是O(n),最好的情况是O(1),O(n)只需要一个线性的结构就可以了,数组、链表都ok,想要达到O(1),就像你说的,必须用空间换时间,哈希表是一种常见做法。除此之外还有一些时间复杂度居中的结构,二分查找是一种常见的做法,可以很方便的把原本需要O(n)的结构加速成O(lgn),数组、链表、树都可以采用这种做法;
2、然后是修改,修改其实是先查询,再修改,查询的时间复杂度已经说过了,具体数据修改的复杂度得看你的数据是什么样的;
3、最后是排序,排序的时间复杂度已经被说烂了,基于比较的排序算法的时间复杂度下限是O(nlgn),有多种结构可以实现它。
看你的需求想要做快速查询,然后想要做实时排序。
假定你的修改是多于查询的,建议查询不必追求O(1),排序求一个下限,用堆或者跳表的结构可以达到目的。假如你的查询是频繁的,修改是少量的,那么可以建立一个哈希表用于查询,排序直接用数组二分甚至用链表都可以。
C++中std::map是用红黑树实现的,也就是输出时按key排序好。为什么会
如果需要多种排序方式,是不是可以每一种排序都用一个std::map来保存相应的引用?