25Q32怎么跟二分法查找结合起来用？ -

标题: 25Q32怎么跟二分法查找结合起来用？ [打印本页]

作者: li1069136863 时间: 2024-8-15 18:23
标题: 25Q32怎么跟二分法查找结合起来用？
1.25Q32中保留N条记录，每条记录包含时间加数据，时间是顺序保存的。（数据量很大，Mbyte级别,不能读到RAM中操作）
2.上位机发送指定时间加次数M，要求上报指定时间后的M次记录。

想到的是二分法查找，不知道怎么结合用？大佬们还有更好的方法吗？

作者: guobaox1981 时间: 2024-8-16 10:34
我提交GPT给的方案可以参考一下
你提到的需求是在一个大数据文件中查找指定时间后的N条记录，由于数据量较大，无法将整个文件加载到内存中，直接在磁盘上进行操作。二分法结合顺序读取是一个合理的解决方案，以下是具体步骤：1. 二分查找定位指定时间由于时间是按顺序保存的，二分查找可以帮助我们快速定位到接近目标时间的记录。读取文件头和尾部的记录，通过它们的时间值计算中间位置（假设你可以通过文件指针直接跳到中间的位置）。二分查找：将中间位置的时间与目标时间进行比较。如果目标时间大于当前时间，继续在后半部分查找；反之在前半部分查找。重复这个过程，直到找到目标时间或最接近目标时间的位置。2. 顺序读取N条记录一旦找到了目标时间的位置，接下来需要顺序读取指定数量的记录。将文件指针移到二分查找到的位置，顺序读取接下来的N条记录。由于时间是顺序排列的，所以直接读取M次就可以获得所需数据。

总结使用二分查找快速定位到目标时间的记录。顺序读取目标时间之后的N条记录。这种方法的优势在于只需要在磁盘上进行有限的读取操作，避免了全量读取数据到内存中，可以有效处理大规模数据文件。

在STM32平台上使用C语言进行二分查找并读取指定时间后的记录，结合存储器25Q32，可以参考以下方案：1. 环境准备Flash类型: 25Q32是一种SPI Flash存储器。你需要在STM32上配置SPI接口，确保可以通过SPI协议访问25Q32存储器。文件系统或裸操作: 如果数据是按照某种结构直接存储在Flash中的，你可能需要裸操作Flash存储器，即通过特定的SPI指令读取数据。2. 数据组织假设每条记录的格式如下：struct Record {
uint32_t timestamp; // 时间戳，假设是4字节
uint8_t data[DATA_LENGTH]; // 数据部分
};假设每条记录长度固定为RECORD_SIZE。3. 二分查找算法实现为了从大文件中高效找到指定时间点后的数据，可以通过二分查找确定目标时间的起始位置。以下是步骤：3.1 计算记录总数你可以通过Flash的总容量除以每条记录的大小来计算出记录总数。#define FLASH_SIZE (4 * 1024 * 1024)  // 25Q32容量 4MB
#define RECORD_SIZE sizeof(struct Record)

uint32_t total_records = FLASH_SIZE / RECORD_SIZE;3.2 实现二分查找二分查找用于找到指定时间戳的位置。uint32_t binary_search(uint32_t target_time) {
uint32_t low = 0;
uint32_t high = total_records - 1;

while (low <= high) {
      uint32_t mid = (low + high) / 2;
      struct Record record;
      read_record(mid, &record); // 从flash读取第mid条记录

      if (record.timestamp < target_time) {
         low = mid + 1;
      } else if (record.timestamp > target_time) {
         high = mid - 1;
      } else {
         return mid; // 找到精确时间
      }
}

return low; // 没有精确匹配，返回最接近的记录位置
}3.3 从指定位置读取M条记录找到目标位置后，可以顺序读取接下来的M条记录。void read_next_n_records(uint32_t start_index, uint32_t n) {
for (uint32_t i = 0; i < n; ++i) {
      struct Record record;
      read_record(start_index + i, &record); // 读取并处理记录
      // process_record(&record);
}
}4. SPI Flash读操作实现在STM32上实现SPI读取25Q32 Flash中的数据，需要使用STM32的HAL库或直接操作寄存器。4.1 SPI Flash读记录的实现void read_record(uint32_t index, struct Record *record) {
uint32_t address = index * RECORD_SIZE;

// 使用SPI读取数据
uint8_t cmd[4];
cmd[0] = READ_COMMAND;          // 读取命令（通常为0x03）
cmd[1] = (address >> 16) & 0xFF; // 地址高字节
cmd[2] = (address >> 8) & 0xFF;  // 地址中字节
cmd[3] = address & 0xFF;       // 地址低字节

HAL_GPIO_WritePin(GPIOB, GPIO_PIN_12, GPIO_PIN_RESET); // 拉低片选（CS）
HAL_SPI_Transmit(&hspi1, cmd, 4, HAL_MAX_DELAY);    // 发送读命令和地址
HAL_SPI_Receive(&hspi1, (uint8_t*)record, RECORD_SIZE, HAL_MAX_DELAY); // 读取数据
HAL_GPIO_WritePin(GPIOB, GPIO_PIN_12, GPIO_PIN_SET); // 拉高片选（CS）
}5. 总结使用二分查找算法在SPI Flash中查找指定时间戳的位置。从该位置开始顺序读取指定数量的记录。在STM32上通过SPI接口实现对25Q32的读操作。这个方案在STM32平台上效率较高，能够处理大规模数据存储器中的查找和读取操作。

作者: dhjmw 时间: 2024-8-16 11:07
如果时间是均匀的，计算即可；如果是随机的，除了二分法，还有黄金分割法更优，你不妨试试。不过Mbyte也不是很大，二分法也不错。

作者: li1069136863 时间: 2024-8-16 11:53

dhjmw 发表于 2024-8-16 11:07
如果时间是均匀的，计算即可；如果是随机的，除了二分法，还有黄金分割法更优，你不妨试试。不过Mbyte也不 ...

时间不是规律增加的，因为外部可以设置这个时间间隔，间隔在1-99内。

作者: glinfei 时间: 2024-8-19 15:12
1、我觉得二分法就不错的；
2、但更建议使用插值法，因为虽然时间间隔可调但估计不会频繁调整所以时间随机性不那么大适合插值法；
3、前边提的黄金分割法是不是需要构建斐波那契数列啊，这在单片机上需要消耗不少内存啊；
4、如果插值法不能满足要求，还可以试试先用分块法粗筛，再用插值法。

作者: li1069136863 时间: 2024-8-19 20:36

glinfei 发表于 2024-8-19 15:12
1、我觉得二分法就不错的；
2、但更建议使用插值法，因为虽然时间间隔可调但估计不会频繁调整所以时间随机 ...

目前遇到个难题，就是在FLASH空间内，如果存储到尽头，会从起始地址开始覆盖回滚覆盖存，这样就会出现整个存储空间，地址从小到大的数据，其记录的时间并不是按先后顺序的，总不能把所有记录数据读出来排序吧

作者: coody_sz 时间: 2024-8-20 15:42
二分法用于间隔恒定的单调参数有效，时间顺序虽然单调，但是间隔不恒定，效果欠佳，但还是可以用。
更好的办法是时间和数据分开存放（类似电脑文件系统的目录项、链表、数据），特别是数据比较大时特别有效，读出时间查找，然后读出对应的数据、

作者: glinfei 时间: 2024-8-21 08:56

li1069136863 发表于 2024-8-19 20:36
目前遇到个难题，就是在FLASH空间内，如果存储到尽头，会从起始地址开始覆盖回滚覆盖存，这样就会出现整 ...

运行一段时间，必然一直按你说的这种情况存储，可以理解顺序是 CDAB ，A<B<C<D,而且C=B+1；如果没有做数据索引，那就先看在AB段还是在CD段即（X>C还是X<B）,然后再二分法去找，当然分后的新中点要先对分段，比如X在AB段，二分后的新点E如果大于B，那就丢弃再找。这里有很多可以优化的地方，比如利用一次是删除多少等条件，迅速发现DA点，及其X是否在记录中；或者删除旧数据时直接记录一下，可以省不少时间。

作者: li1069136863 时间: 2024-8-21 14:19

glinfei 发表于 2024-8-21 08:56
运行一段时间，必然一直按你说的这种情况存储，可以理解顺序是 CDAB ，A

是做了索引，索引保存的是记录的总次数，还有最新的一条记录跟基地址的偏移量，主要是这两个变量。我先按照你的思路捋一下

作者: glinfei 时间: 2024-8-21 15:51

li1069136863 发表于 2024-8-21 14:19
是做了索引，索引保存的是记录的总次数，还有最新的一条记录跟基地址的偏移量，主要是这两个变量。我先按 ...

那就相当于分两个块，分别搜索啊，但有个问题，查找A的偏移要注意，因为删除是按页面删的，所以会有空白区，可以理解DA之间有空白区，

欢迎光临 (http://www.51hei.com/bbs/)