精品在线一区,亚洲日韩最全色无码综合

標(biāo)題: 25Q32怎么跟二分法查找結(jié)合起來用？ [打印本頁(yè)]

作者: li1069136863 時(shí)間: 2024-8-15 18:23
標(biāo)題: 25Q32怎么跟二分法查找結(jié)合起來用？
1.25Q32中保留N條記錄，每條記錄包含時(shí)間加數(shù)據(jù)，時(shí)間是順序保存的。（數(shù)據(jù)量很大，Mbyte級(jí)別,不能讀到RAM中操作）
2.上位機(jī)發(fā)送指定時(shí)間加次數(shù)M，要求上報(bào)指定時(shí)間后的M次記錄。

想到的是二分法查找，不知道怎么結(jié)合用？大佬們還有更好的方法嗎？

作者: guobaox1981 時(shí)間: 2024-8-16 10:34
我提交GPT給的方案可以參考一下
你提到的需求是在一個(gè)大數(shù)據(jù)文件中查找指定時(shí)間后的N條記錄，由于數(shù)據(jù)量較大，無(wú)法將整個(gè)文件加載到內(nèi)存中，直接在磁盤上進(jìn)行操作。二分法結(jié)合順序讀取是一個(gè)合理的解決方案，以下是具體步驟：1. 二分查找定位指定時(shí)間由于時(shí)間是按順序保存的，二分查找可以幫助我們快速定位到接近目標(biāo)時(shí)間的記錄。讀取文件頭和尾部的記錄，通過它們的時(shí)間值計(jì)算中間位置（假設(shè)你可以通過文件指針直接跳到中間的位置）。二分查找：將中間位置的時(shí)間與目標(biāo)時(shí)間進(jìn)行比較。如果目標(biāo)時(shí)間大于當(dāng)前時(shí)間，繼續(xù)在后半部分查找；反之在前半部分查找。重復(fù)這個(gè)過程，直到找到目標(biāo)時(shí)間或最接近目標(biāo)時(shí)間的位置。2. 順序讀取N條記錄一旦找到了目標(biāo)時(shí)間的位置，接下來需要順序讀取指定數(shù)量的記錄。將文件指針移到二分查找到的位置，順序讀取接下來的N條記錄。由于時(shí)間是順序排列的，所以直接讀取M次就可以獲得所需數(shù)據(jù)。

總結(jié)使用二分查找快速定位到目標(biāo)時(shí)間的記錄。順序讀取目標(biāo)時(shí)間之后的N條記錄。這種方法的優(yōu)勢(shì)在于只需要在磁盤上進(jìn)行有限的讀取操作，避免了全量讀取數(shù)據(jù)到內(nèi)存中，可以有效處理大規(guī)模數(shù)據(jù)文件。

在STM32平臺(tái)上使用C語(yǔ)言進(jìn)行二分查找并讀取指定時(shí)間后的記錄，結(jié)合存儲(chǔ)器25Q32，可以參考以下方案：1. 環(huán)境準(zhǔn)備Flash類型: 25Q32是一種SPI Flash存儲(chǔ)器。你需要在STM32上配置SPI接口，確保可以通過SPI協(xié)議訪問25Q32存儲(chǔ)器。文件系統(tǒng)或裸操作: 如果數(shù)據(jù)是按照某種結(jié)構(gòu)直接存儲(chǔ)在Flash中的，你可能需要裸操作Flash存儲(chǔ)器，即通過特定的SPI指令讀取數(shù)據(jù)。2. 數(shù)據(jù)組織假設(shè)每條記錄的格式如下：struct Record {
uint32_t timestamp; // 時(shí)間戳，假設(shè)是4字節(jié)
uint8_t data[DATA_LENGTH]; // 數(shù)據(jù)部分
};假設(shè)每條記錄長(zhǎng)度固定為RECORD_SIZE。3. 二分查找算法實(shí)現(xiàn)為了從大文件中高效找到指定時(shí)間點(diǎn)后的數(shù)據(jù)，可以通過二分查找確定目標(biāo)時(shí)間的起始位置。以下是步驟：3.1 計(jì)算記錄總數(shù)你可以通過Flash的總?cè)萘砍悦織l記錄的大小來計(jì)算出記錄總數(shù)。#define FLASH_SIZE (4 * 1024 * 1024)  // 25Q32容量 4MB
#define RECORD_SIZE sizeof(struct Record)

uint32_t total_records = FLASH_SIZE / RECORD_SIZE;3.2 實(shí)現(xiàn)二分查找二分查找用于找到指定時(shí)間戳的位置。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; // 找到精確時(shí)間
      }
}

return low; // 沒有精確匹配，返回最接近的記錄位置
}3.3 從指定位置讀取M條記錄找到目標(biāo)位置后，可以順序讀取接下來的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讀操作實(shí)現(xiàn)在STM32上實(shí)現(xiàn)SPI讀取25Q32 Flash中的數(shù)據(jù)，需要使用STM32的HAL庫(kù)或直接操作寄存器。4.1 SPI Flash讀記錄的實(shí)現(xiàn)void read_record(uint32_t index, struct Record *record) {
uint32_t address = index * RECORD_SIZE;

// 使用SPI讀取數(shù)據(jù)
uint8_t cmd[4];
cmd[0] = READ_COMMAND;          // 讀取命令（通常為0x03）
cmd[1] = (address >> 16) & 0xFF; // 地址高字節(jié)
cmd[2] = (address >> 8) & 0xFF;  // 地址中字節(jié)
cmd[3] = address & 0xFF;       // 地址低字節(jié)

HAL_GPIO_WritePin(GPIOB, GPIO_PIN_12, GPIO_PIN_RESET); // 拉低片選（CS）
HAL_SPI_Transmit(&hspi1, cmd, 4, HAL_MAX_DELAY);    // 發(fā)送讀命令和地址
HAL_SPI_Receive(&hspi1, (uint8_t*)record, RECORD_SIZE, HAL_MAX_DELAY); // 讀取數(shù)據(jù)
HAL_GPIO_WritePin(GPIOB, GPIO_PIN_12, GPIO_PIN_SET); // 拉高片選（CS）
}5. 總結(jié)使用二分查找算法在SPI Flash中查找指定時(shí)間戳的位置。從該位置開始順序讀取指定數(shù)量的記錄。在STM32上通過SPI接口實(shí)現(xiàn)對(duì)25Q32的讀操作。這個(gè)方案在STM32平臺(tái)上效率較高，能夠處理大規(guī)模數(shù)據(jù)存儲(chǔ)器中的查找和讀取操作。

作者: dhjmw 時(shí)間: 2024-8-16 11:07
如果時(shí)間是均勻的，計(jì)算即可；如果是隨機(jī)的，除了二分法，還有黃金分割法更優(yōu)，你不妨試試。不過Mbyte也不是很大，二分法也不錯(cuò)。

作者: li1069136863 時(shí)間: 2024-8-16 11:53

dhjmw 發(fā)表于 2024-8-16 11:07
如果時(shí)間是均勻的，計(jì)算即可；如果是隨機(jī)的，除了二分法，還有黃金分割法更優(yōu)，你不妨試試。不過Mbyte也不 ...

時(shí)間不是規(guī)律增加的，因?yàn)橥獠靠梢栽O(shè)置這個(gè)時(shí)間間隔，間隔在1-99內(nèi)。

作者: glinfei 時(shí)間: 2024-8-19 15:12
1、我覺得二分法就不錯(cuò)的；
2、但更建議使用插值法，因?yàn)殡m然時(shí)間間隔可調(diào)但估計(jì)不會(huì)頻繁調(diào)整所以時(shí)間隨機(jī)性不那么大適合插值法；
3、前邊提的黃金分割法是不是需要構(gòu)建斐波那契數(shù)列啊，這在單片機(jī)上需要消耗不少內(nèi)存��；
4、如果插值法不能滿足要求，還可以試試先用分塊法粗篩，再用插值法。

作者: li1069136863 時(shí)間: 2024-8-19 20:36

glinfei 發(fā)表于 2024-8-19 15:12
1、我覺得二分法就不錯(cuò)的；
2、但更建議使用插值法，因?yàn)殡m然時(shí)間間隔可調(diào)但估計(jì)不會(huì)頻繁調(diào)整所以時(shí)間隨機(jī) ...

目前遇到個(gè)難題，就是在FLASH空間內(nèi)，如果存儲(chǔ)到盡頭，會(huì)從起始地址開始覆蓋回滾覆蓋存，這樣就會(huì)出現(xiàn)整個(gè)存儲(chǔ)空間，地址從小到大的數(shù)據(jù)，其記錄的時(shí)間并不是按先后順序的，總不能把所有記錄數(shù)據(jù)讀出來排序吧

作者: coody_sz 時(shí)間: 2024-8-20 15:42
二分法用于間隔恒定的單調(diào)參數(shù)有效，時(shí)間順序雖然單調(diào)，但是間隔不恒定，效果欠佳，但還是可以用。
更好的辦法是時(shí)間和數(shù)據(jù)分開存放（類似電腦文件系統(tǒng)的目錄項(xiàng)、鏈表、數(shù)據(jù)），特別是數(shù)據(jù)比較大時(shí)特別有效，讀出時(shí)間查找，然后讀出對(duì)應(yīng)的數(shù)據(jù)、

作者: glinfei 時(shí)間: 2024-8-21 08:56

li1069136863 發(fā)表于 2024-8-19 20:36
目前遇到個(gè)難題，就是在FLASH空間內(nèi)，如果存儲(chǔ)到盡頭，會(huì)從起始地址開始覆蓋回滾覆蓋存，這樣就會(huì)出現(xiàn)整 ...

運(yùn)行一段時(shí)間，必然一直按你說的這種情況存儲(chǔ)，可以理解順序是 CDAB ，A<B<C<D,而且C=B+1；如果沒有做數(shù)據(jù)索引，那就先看在AB段還是在CD段即（X>C還是X<B）,然后再二分法去找，當(dāng)然分后的新中點(diǎn)要先對(duì)分段，比如X在AB段，二分后的新點(diǎn)E如果大于B，那就丟棄再找。這里有很多可以優(yōu)化的地方，比如利用一次是刪除多少等條件，迅速發(fā)現(xiàn)DA點(diǎn)，及其X是否在記錄中；或者刪除舊數(shù)據(jù)時(shí)直接記錄一下，可以省不少時(shí)間。

作者: li1069136863 時(shí)間: 2024-8-21 14:19

glinfei 發(fā)表于 2024-8-21 08:56
運(yùn)行一段時(shí)間，必然一直按你說的這種情況存儲(chǔ)，可以理解順序是 CDAB ，A

是做了索引，索引保存的是記錄的總次數(shù)，還有最新的一條記錄跟基地址的偏移量，主要是這兩個(gè)變量。我先按照你的思路捋一下

作者: glinfei 時(shí)間: 2024-8-21 15:51

li1069136863 發(fā)表于 2024-8-21 14:19
是做了索引，索引保存的是記錄的總次數(shù)，還有最新的一條記錄跟基地址的偏移量，主要是這兩個(gè)變量。我先按 ...

那就相當(dāng)于分兩個(gè)塊，分別搜索啊，但有個(gè)問題，查找A的偏移要注意，因?yàn)閯h除是按頁(yè)面刪的，所以會(huì)有空白區(qū)，可以理解DA之間有空白區(qū)，

歡迎光臨 (http://www.torrancerestoration.com/bbs/)

<samp id="ka8wm"></samp>