通过最大值和ID检索的最佳数据结构? [英] Best data structure to retrieve by max values and ID?

查看:71
本文介绍了通过最大值和ID检索的最佳数据结构?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有很多固定大小的记录.每个记录都有很多字段,其中包括ID和Value.我想知道哪种数据结构最好,这样我就可以

I have quite a big amount of fixed size records. Each record has lots of fields, ID and Value are among them. I am wondering what kind of data structure would be best so that I can

  1. 通过ID(唯一)快速找到记录,

  1. locate a record by ID(unique) very fast,

列出具有最大值的100条记录.

list the 100 records with the biggest values.

最大堆似乎可行,但远非完美;您有更聪明的解决方案吗?

Max-heap seems work, but far from perfect; do you have a smarter solution?

谢谢.

推荐答案

混合数据结构最有可能是最好的.为了通过ID进行有效查找,良好的结构显然是哈希表.为了支持top-100迭代,最大堆或二叉树是一个很好的选择.插入和删除时,只需对两个结构都进行操作.如果迭代次数的100是固定的,则迭代会频繁发生,并且插入/删除不会严重倾斜到前100名,只需将前100名保留为有排序的数组,并溢出到最大堆即可.这不会改变结构的big-O复杂性,但是对于迭代情况,它将提供非常好的恒定因子加速.

A hybrid data structure will most likely be best. For efficient lookup by ID a good structure is obviously a hash-table. To support top-100 iteration a max-heap or a binary tree is a good fit. When inserting and deleting you just do the operation on both structures. If the 100 for the iteration case is fixed, iteration happens often and insertions/deletions aren't heavily skewed to the top-100, just keep the top 100 as a sorted array with an overflow to a max-heap. That won't modify the big-O complexity of the structure, but it will give a really good constant factor speed-up for the iteration case.

这篇关于通过最大值和ID检索的最佳数据结构?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆