最佳访问/插入关联数组 [英] optimal access/insertion associative array
问题描述
嗨
我正在寻找一个最佳的数据结构来替换
地图< int，float> ;.
我用它作为某种稀疏数组表示。
事实：
- 数据结构中的人口数可能大于10 ^ 6
- 元素的最大数量（上限）已知并且已修复
- 键是一个整数，元素是一个浮点值
- 我需要做很多访问/插入操作，但我不在乎
关于他们的订购
欢迎任何帮助。
如果这篇文章不适合这个群体，请告诉我。
谢谢。
Tom
Tom写道：我正在寻找一个最佳的数据结构来替换
map< int，float> ;.
我用它作为某种稀疏数组表示。
事实：
- 数据结构中的人口可以大于10 ^ 6
1.1 * 10 ^ 6更大，因此是10 ^ 100。我们说的话要多大一点
大概？
- 元素的最大数量（上限）已知且固定
它与人口规模有何关系？在编译时或运行时是否知道
？
- 键是一个整数，该元素是一个浮点值
- 我需要做很多访问/插入操作，但我不在乎他们的订购
你看过hash_map吗？
V
感谢您快速回答Victor
1.1 * 10 ^ 6更大，所以是10 ^ 100。我们谈的是多大？
假设上限为10 ^ 9。但它通常包含在10 ^ 5到10 ^ 6之间的
。
它与人口规模有什么关系？
它是一样的。
它是在编译时还是在运行时知道的？
上限在运行时已知。
你看过hash_map吗？
尚未，因为它似乎< hash_map>不适用于Visual C ++。
Tom写道：感谢您快速回答Victor
1.1 * 10 ^ 6更大，因此是10 ^ 100。我们谈的是多大？
让我们说上限是10 ^ 9。但它通常包含在10 ^ 5和10 ^ 6之间。
单个集合是否会增长？在开始插入之前，你知道有多少元素会在特定的集合中出现吗？
那怎么办？它与人口规模有关吗？
它是一样的。
我当时不明白。你说阵列很稀疏。在这种情况下，你不希望保留额外的价值（这将使实际的b / b
远小于指数的上限）。或key）或
您需要以某种方式表明某个值是缺失。那么，这是什么
呢？比如说，你的上限值为100，而且人口数量不会超过10美元。你可以使用100个值的数组，其中只有
到10值是有效的，你可以通过
验证另一个（小）有效索引数组的有效性。我不认为这是一个很好的想法，因为如果我理解正确，你需要一个10 ^ 9 FP
值的数组，这个数字相当大，当只使用大约10 ^ 5到10 ^ 6时。
只存储与人口中的值一样多的值。要求
数组排序以便快速检索。这就是地图给你的东西，
种类。顺便说一句，''地图''有什么问题？它还不够快吗？
您未指定的另一个要求：您的收藏品是否达到了b
，无需再更改，之后你只需要检索
值并且不要插入新的值？你是否需要从集合中删除任何值
？
在编译时或运行时是否已知-time？
上限在运行时是已知的。
你对b的定义是什么？上限？我以为当你说10 ^ 9
这意味着1000000000 _is_上界。
你看过吗？一个hash_map？
还没有，因为它似乎< hash_map>不适用于Visual C ++。
对，它不是。您需要获取SGI的STL版本或在其他库中找到
a hash_map实现（Boost可能有它）。
V
Hi
I am looking for an optimal data-structure in order to replace a
map<int,float>.
I use it as some kind of sparse array representation.
The facts:
- the population in the data-structures can be bigger than 10^6
- the maximum number of elements (upper bound) is known and fixed
- the key is an integer, the element is a float value
- I need to do lots of access/insertion operations, but I don''t care
about their ordering
Any help is welcome.
If this post is not adapted to this group, please let me know.
Thanks.
Tom
Tom wrote:I am looking for an optimal data-structure in order to replace a
map<int,float>.
I use it as some kind of sparse array representation.
The facts:
- the population in the data-structures can be bigger than 10^6
1.1 * 10^6 is bigger, and so is 10^100. How much bigger are we talking
about?
- the maximum number of elements (upper bound) is known and fixed
And how does it relate to the size of the population? Is it known at
compile-time or at run-time?
- the key is an integer, the element is a float value
- I need to do lots of access/insertion operations, but I don''t care
about their ordering
Have you looked at a hash_map?
V
Thanks for the quick answer Victor
1.1 * 10^6 is bigger, and so is 10^100. How much bigger are we talking about?
Let''s say the upper bound is 10^9. But it is very often comprised
between 10^5 and 10^6.
And how does it relate to the size of the population?
it is the same.
Is it known at compile-time or at run-time?
the upper bound is known at run-time.
Have you looked at a hash_map?
Not yet because it seems <hash_map> is not available with Visual C++.
Tom wrote:Thanks for the quick answer Victor1.1 * 10^6 is bigger, and so is 10^100. How much bigger are we talking about?
Let''s say the upper bound is 10^9. But it is very often comprised
between 10^5 and 10^6.
Does a single collection ever grow? Do you know how many elements are
going to be in a particular collection before you start inserting?
And how does it relate to the size of the population?
it is the same.
I don''t understand then. You said the array is sparse. In that case you
either don''t want to keep the extra values (which would make the actual
population much smaller than the upper limit of the "index" or "key") or
you need to somehow indicate that a certain value is "missing". So, which
is it? Say, you have the upper value 100, and the population is no larger
than 10. You could then use an array of 100 values out of which only up
to 10 values would be valid, and the validity you could verify through
another (small) array of "valid indices". I don''t think this is a good
idea because if I understood correctly, you would need an array of 10^9 FP
values, which is rather big, when only using about 10^5 to 10^6 of them.
Storing only as many values as you have in the "population" requires that
the "array" is sorted for quick retrieval. That''s what ''map'' gives you,
kind of. BTW, what''s wrong with ''map''? Is it not fast enough?
Another requirement you left unspecified: does your collection ever reach
the point of "no need to change any longer", after which you only retrieve
values and don''t insert new ones? Do you ever need to remove any values
from the collection?
Is it known at compile-time or at run-time?
the upper bound is known at run-time.
What''s your definition of "upper bound"? I thought that when you say 10^9
that means that 1000000000 _is_ the upper bound.
Have you looked at a hash_map?
Not yet because it seems <hash_map> is not available with Visual C++.
Right, it isn''t. You need to get the SGI''s version of STL or find
a hash_map implementation in some other library (Boost probably has it).
V
这篇关于最佳访问/插入关联数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
