fight281 发表于 2021-7-27 17:45

MCU如何实现数据查找索引？

请教个大家一个问题，用STM32实现一个刷卡进门的项目，假设卡号都已经存储，如何快速查找对比当前刷卡卡号信息？

一周一天班 发表于 2021-7-27 18:56

卡号得到32位或16位累加和，把这个做数组索引，指向卡号信息地址。为避免重复，卡号多加两位自定义值，存储时检查是否有重复，有则自定义值加，直到唯一。

wood2qin 发表于 2021-7-27 19:40

数据排序存入。二分法查找。能省不少时间。顺序查太费了。

fight281 发表于 2021-7-27 21:43

一周一天班 发表于 2021-7-27 18:56
卡号得到32位或16位累加和，把这个做数组索引，指向卡号信息地址。为避免重复，卡号多加两位自定义值，存储 ...

谢谢！换成CRC16是否可行？

fight281 发表于 2021-7-27 21:43

wood2qin 发表于 2021-7-27 19:40
数据排序存入。二分法查找。能省不少时间。顺序查太费了。

好的，我学习一下，谢谢！

一周一天班 发表于 2021-7-27 22:31

可以，不建议二分法，因为数据是多字节的。采样数据库索引方式比较好。

coody 发表于 2021-7-28 09:56

类似的查找（我用得最多的是串口不定长字符命令），我都是对字符串计算CRC16校验，再加一个字符串映射序号。为了方便查找（比如二分法），对CRC16值进行排序。先计算字符串的CRC16值，读取其映射序号，再读取字符串比较，几万个记录，都可以几十us之内查到。

li880wert 发表于 2021-7-30 08:36

要想快按数据库像做索引，按位或字节分段，分开存放，

xyz549040622 发表于 2021-7-31 21:11

coody 发表于 2021-7-28 09:56
类似的查找（我用得最多的是串口不定长字符命令），我都是对字符串计算CRC16校验，再加一个字符串映射序号 ...

确实是个很好的办法，学习了，不过几十us的速度，有这么快吗？太不可思议了

William1994 发表于 2021-8-1 21:01

卡号高地位所有字节加起来，取0x37的余数，这个hash运算比crc要快。
然后留一个字节，给解决冲突的时候用。

coody 发表于 2021-8-2 16:08

xyz549040622 发表于 2021-7-31 21:11
确实是个很好的办法，学习了，不过几十us的速度，有这么快吗？太不可思议了 ...

几十us都是慢的了。
计算好CRC16，然后顺序排列好，假设有32768个，则2分法查找，只需要查15次，每次读出CRC16比较，现在的MCU通常不需要2us一次（比如用STC8系列的8位机，M0、M3、M4等等32位机），所以30us之内一定可以完成。
假设顺序查找32768次，最长也是在几十ms内。

m564522634 发表于 2021-8-2 19:18

哈希表

fight281 发表于 2021-8-6 16:08

m564522634 发表于 2021-8-2 19:18
哈希表

最近看到了哈希索引，感觉非常不错，哈希的索引速度还是不错的，就是还没有实验哈希的冲突多不多。

fight281 发表于 2021-8-6 16:11

William1994 发表于 2021-8-1 21:01
卡号高地位所有字节加起来，取0x37的余数，这个hash运算比crc要快。
然后留一个字节，给解决冲突的时候用。 ...

一个字节够么？按照目前项目的估算 模值应该是在2000左右，就是不晓得留多少余量，多留3个不知道够不够？

fight281 发表于 2021-8-6 16:17

li880wert 发表于 2021-7-30 08:36
要想快按数据库像做索引，按位或字节分段，分开存放，

如果这样的话 4个字节的数据是不是需要很大空间？计算机可以实现，但放单片机上太难了吧？外设的存储也没有这么大的。

m564522634 发表于 2021-8-9 09:11

fight281 发表于 2021-8-6 16:17
如果这样的话 4个字节的数据是不是需要很大空间？计算机可以实现，但放单片机上太难了吧？外设的存储也没 ...

上轻量级的数据库吧，flashDB， 或者sqlitt我建议你用flashDB稳定速度也不错，数据库本身就是做这个活的他们对搜索优化做的肯定不错，你自己也不用搞那么多的事出来。

fight281 发表于 2021-8-10 15:29

m564522634 发表于 2021-8-9 09:11
上轻量级的数据库吧，flashDB， 或者sqlitt我建议你用flashDB稳定速度也不错，数据库本身就是做这个活 ...

谢谢指点，我研究一下。

xinyue_z 发表于 2021-8-20 09:24

综合以上所有的回复得出的方法：首先对存储数据进行hash处理，然后按照hash值对存储的数据进行排序，这其中肯定有很多hash相同的。在相同的hash值的数据中使用第二种hash算法，对相同第一种hash的数据进行二次排序。最后为第一次hash建立一个索引（映射表：hash值多少存储地址从哪里开始）按hash值排序，在查找时计算刷卡的第一次hash值，二分法在索引中进行查找，找到首地址和尾地址（下一个hash值的首地址），如果相同的hash值比较多，再按照第二种hash算法二分法查找，如果比较少，就直接比较法查找

fight281 发表于 2021-9-7 11:48

xinyue_z 发表于 2021-8-20 09:24
综合以上所有的回复得出的方法：首先对存储数据进行hash处理，然后按照hash值对存储的数据进行排序，这其中 ...

感谢指点！在UINT32取值范围内取2000个数，第一次的hash我测试了一下，重复最多的找5~8之间，请问二次hash一般都怎么处理？

xinyue_z 发表于 2021-9-7 14:12

fight281 发表于 2021-9-7 11:48
感谢指点！在UINT32取值范围内取2000个数，第一次的hash我测试了一下，重复最多的找5~8之间，请问二次has ...

如果一次hash重复的数值比较少的话就没有必要做二次hash了，直接在相同的hash值序列中循环查找就行了。如果重复的很多，选择另一个hash算法，比如简单的单字节累加求和，异或等然后再相同的一次hash序列中按照二次hash的结果排序，在查找的时候，一次hash以后在相同的序列中折半查找。
页: [1]
查看完整版本: MCU如何实现数据查找索引？