Поиск

Бинарный поиск


Погуглив какое-то время и не найдя готовое, решил самостоятельно набросать коды ошибок CANopen, заодно сделав бинарный поиск по структуре.

Сам список нашел в интернете в виде таблички, ее необходимо преобразовать в удобный вид. Удалив sed’ом пустые строки, стал гуглить, как мне нечетные строки с четными объединить. Узнал о команде paste (никогда раньше ее не использовал). paste - - делает как раз то, что нужно, используя вместо обоих файлов стандартный вход. Если написать paste a b, то на выходе получим строки, каждая из которых есть объединение соответствующей нечетной строки файла a и четной строки файла b.
Итоговое форматирование получилось так:

while read l; do N=$(echo $l|awk '{print $1 $2}'); R=$(echo $l|awk '{$1=$2=""; print substr($0,3)}'|sed 's/\.//'); echo -e "{0x$N, \"$R\"},"; done < codes.b


В итоге вот такая штука получилась:

typedef struct{ uint32_t code; char *errmsg;
} abortcodes; static const abortcodes AC[] = { {0x05030000, "Toggle bit not alternated"}, {0x05040000, "SDO protocol timed out"}, {0x05040001, "Client/server command specifier not valid or unknown"}, {0x05040002, "Invalid block size (block mode only)"}, {0x05040003, "Invalid sequence number (block mode only)"}, {0x05040004, "CRC error (block mode only)"}, {0x05040005, "Out of memory"}, {0x06010000, "Unsupported access to an object"}, {0x06010001, "Attempt to read a write only object"}, {0x06010002, "Attempt to write a read only object"}, {0x06020000, "Object does not exist in the object dictionary"}, {0x06040041, "Object cannot be mapped to the PDO"}, {0x06040042, "The number and length of the objects to be mapped would exceed PDO length"}, {0x06040043, "General parameter incompatibility reason"}, {0x06040047, "General internal incompatibility in the device"}, {0x06060000, "Access failed due to a hardware error"}, {0x06070010, "Data type does not match; length of service parameter does not match"}, {0x06070012, "Data type does not match; length of service parameter too high"}, {0x06070013, "Data type does not match; length of service parameter too low"}, {0x06090011, "Sub-index does not exist"}, {0x06090030, "Value range of parameter exceeded (only for write access)"}, {0x06090031, "Value of parameter written too high"}, {0x06090032, "Value of parameter written too low"}, {0x06090036, "Maximum value is less than minimum value"}, {0x08000000, "General error"}, {0x08000020, "Data cannot be transferred or stored to the application"}, {0x08000021, "Data cannot be transferred or stored to the application because of local control"}, {0x08000022, "Data cannot be transferred or stored to the application because of the present device state"}, {0x08000023, "Object dictionary dynamic generation fails or no object dictionary is present"},
};


Бинарный поиск реализуется элементарно:

const char *ACtext(uint32_t abortcode, int *n){ int idx = ACmax/2, min_ = 0, max_ = ACmax, newidx = 0, iter=0; do{ ++iter; uint32_t c = AC[idx].code; printf("idx=%d, min=%d, max=%d\n", idx, min_, max_); if(c == abortcode){ if(n) *n = iter; return AC[idx].errmsg; }else if(c > abortcode){ newidx = (idx + min_)/2; max_ = idx; }else{ newidx = (idx + max_ + 1)/2; min_ = idx; } if(newidx == idx || min_ < 0 || max_ > ACmax){ if(n) *n = 0; return NULL; } idx = newidx; }while(1);
}


первый параметр здесь — искомый код, второй — количество итераций, за которое его нашли в таблице (если не нашли, возвращается NULL и нуль вместо количества).
Вот такая функция перебирает все известные коды и выводит среднее количество итераций (нужно только для отладки — проверить, нет ли багов):

void check_all(){ int iter = 0, N; for(int i = 0; i <= ACmax; ++i){ printf("code 0x%X: %s\n\n", AC[i].code, ACtext(AC[i].code, &N)); iter += N; } printf("\n\ntotal: %d iterations, mean: %d, (%d for direct lookup)\n", iter, iter/(ACmax+1), (ACmax+1)/2);
}


В итоге получилось:

total: 119 iterations, mean: 4, (14 for direct lookup)

Если бы я использовал прямой поиск по списку, было бы в среднем 14 итераций (точней — 14.5), а бинарный поиск дал 4 (точней — 4.1).
Ну и функция main для тестов:

int main(int argc, char **argv){ if(argc != 2){ check_all(); return 0; } uint32_t x = (uint32_t)strtol(argv[1], NULL, 0); printf("x=0x%X\n", x); const char *text = ACtext(x, NULL); if(text) printf("%s\n", text); else printf("Unknown error code\n"); return 0;
}


eddy_em.livejournal.com

Добавить комментарий