没有你的车你就没有那么坚强。最快的查找列表
我有一个结构集合。每个结构有 2 个键。如果我使用键 #1 查询，我应该得到键 #2 作为回报，反之亦然。
当您拥有 .NET Framework 的强大支持时，可以轻松地在桌面上编写代码。我正在 .NET Micro Framework 中编写代码，这是一个非常非常有限的框架子集。例如，就集合而言，我只有数组和 ArrayList 对象可供使用。
例如，这里是结构列表：
Key #1 Key #2
6 A
7 F
8 Z
9 B
因此，当我查询 8 时，我应该得到 Z。 当我查询 Z 时，我应该得到 8。
我希望使用数组或 ArrayList 进行最快且处理器密集程度最低的查找。我正在编码的设备是低端 ARM 处理器，因此我需要尽早优化。
I have a collection of structures. Each structure has 2 keys. If I query using key #1, I should get key #2 in return and vice versa.
It's easy to write code on the desktop when you have the power of the .NET Framework behind you. I am writing code in the .NET Micro Framework, which is a very very limited subset of framework. For instance, as far as collections, I only have arrays and ArrayList objects at my disposal.
So for example here is the list of structures:
Key #1 Key #2
6 A
7 F
8 Z
9 B
So when I query for 8, I should get Z.
When I query for Z, I should get 8.
I am looking to do the fastest and least processor intensive lookup using either arrays or ArrayList. The device I am coding against is a low-end ARM processor, thus I need to optimize early.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
如果该集合是固定的，请查看完美哈希函数。
If the set is fixed, look into perfect hash functions.
你有什么理由不能编写自己的哈希图吗？
Any reason you can't write your own hashmap?
这取决于条目数量和您的访问模式。
鉴于您的访问模式是随机访问，如果您没有太多元素，您可以拥有 2 个对数组，然后使用
It depends on the number of entries and your access pattern.
Given that your access pattern is random access if you don't have too many elements you could have 2 Arrays of Pairs and then use
好吧...如果您想要最快并且不太关心内存，只需使用两个哈希表即可。一个人往一个方向走，一个人往另一个方向走。不确定是否有一种更有效的内存方式...
或者只使用一个哈希表，但其中有两个方向的条目。
Well... if you want the fastest and aren't too concerned about memory, just use two hash tables. One going one way, one going to other. Not sure if there's a more memory efficient way...
Or use just one hash table but have the entries for both directions in there.
它不是那么简单吗：
我会尽可能保持简单，只需迭代您的数组正在寻找。如果您的列表（从空气中提取数字）超过 1k+ 元素，您可能只会看到实现一些散列例程的好处，并且您自己的散列例程增加的复杂性会在一定程度上减慢速度。
Is it not as simple as :
I would keep it as simple as possible and just iterate through the array you're searching. You'll probably only see a benefit from implementing some hashing routines if your list is (plucks figure from air) over 1k+ elements, with the added complexity of your own hashing routines slowing things down somewhat.
几种解决方案：
object.GetHashCode() % numBuckets将项目映射到存储桶。Several solutions:
object.GetHashCode() % numBuckets.如果是固定集，请考虑使用
switch。请参阅此处类似问题的答案。If it's a fixed set, consider using
switch. See the answer to a similar question here.几年前，我在编写 C 语言时遇到了这个问题，我们需要在大约 10,000 行中快速找到条形码（数字）（当时，使用文件作为数据库 - 因为它是一个手持设备）
我创建了自己的搜索总是从中间开始，而不是逐一迭代...
在 10000 个项目堆栈中搜索 4050
...
直到获得值...您将需要搜索大约 14 次，而不是
关于字母的 4050 次迭代...它们也都代表一个数字.. 。
希望有帮助
I had this problem several years ago when programming C, that we need to find a barcode (numeric) quickly in about 10 thousand rows (in that time, using a file as the Database - as it was a hand device)
I created my own search that instead of iterate one by one would start always in the middle...
searching for 4050 in 10000 item stack
...
until you get the value... you will need to search about 14 times instead 4050 iterations
about the letters ... they all represent a numeric number as well...
Hope it helps