Easyelectronics.ru

Электроника для всех
Текущее время: 22 фев 2019, 13:27

Часовой пояс: UTC + 5 часов




Начать новую тему Ответить на тему  [ Сообщений: 11 ] 
Автор Сообщение
 Заголовок сообщения: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 10:27 
Только пришел
Аватара пользователя

Зарегистрирован: 30 май 2011, 18:31
Сообщения: 18
Откуда: Москва
1. Сразу скажу, что я осЁл, поэтому буду рад любым советам, в т.ч. тыканьем в гугол (по делу), т.к. самому подобрать ключевые слова для гугла не получилось.

2. Изобретаю блокиратор нежелательных звонков для городского телефона. Т.к. имеющиеся в продаже на нашем сраном МГТС работают через раз и я эту проблему решил, но осталась сабжевая. По-сути это Caller ID АОН с расширенным черным списком. Аппаратная часть состоит из ардуины про мини, дисплея 16х2, 5-и кнопок висящих на АЦП, пищалки, декодера на HT9032 с дополнительной обвязкой в виде детектора звонка и устройства захвата линии и EEPROM'а на I2C 24C64. В данный момент работает просто как обычный АОН. Списог входящих реализован во встроенной EEPROM на 48 ячеек, в формате 21-го байта, пример:
1 байт порядковый номер в списке (1-48)
1 байт признак черного списка (0x2A, "*")
8 байт дата/время от оператора
11 байт номер телефона от оператора

3. Планируется хранить номера черного списка во внешней EEPROM в формате 11-байт, т.е. просто телефонный номер в виде: 84951234567 за ним следующий и т.д.
24С64 хватает, чтобы набить туда >700 номеров, соответственно нужен быстрый поиск по этим 700 номерам, в первую очередь это нужно при входящем звонке, чтобы определить сидит ли номер в черном списке или нет, вторично это нужно для установки признака черного списка в списке входящих.
Как это можно реализовать? Если ограничиваться строго российскими звонками, то восьмерка в начале будет всегда, а дальше 10 цифр могут быть какие угодно.

_________________
Life is a long jump, from the cunt to the grave...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:00 
Только пришел

Зарегистрирован: 20 июн 2016, 15:31
Сообщения: 13
За таблицей с номерами в ЕЕПРОМ создать индексную таблицу и по ней искать .
Правда придется ее пересчитывать каждый раз когда меняется основная.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:05 
Старожил

Зарегистрирован: 16 ноя 2012, 07:47
Сообщения: 2748
поставить FRAM. Чтение/запись на скорости SPI, никаких задержек. Flash тоже достаточно быстро читается.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:20 
Старожил
Аватара пользователя

Зарегистрирован: 05 фев 2013, 00:58
Сообщения: 3406
Откуда: Тольятти
Отвести первые 700 байт под хэши, искать по ним. В редчайшем случае, если хэш совпадает, делать 2 сравнения строк вместо одного.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:29 
Старожил
Аватара пользователя

Зарегистрирован: 06 ноя 2013, 16:07
Сообщения: 613
Откуда: Германия
А сколько времени занимает полное чтение/запись 24С64?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:52 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 5477
Вариант:
1. Удавить жабу
2. Взять STM32F030F4
3. В качестве хранилища использовать Flash. ~20K хватит на много номеров
4. Телефонный номер - это число из десятичных цифр. Значит - храните не ASCII, а именно то ЧИСЛО, что есть. Выйдет 2x uint32_t. Для борьбы с значащими нулями, номер обрамлять фиксированными цифрами - 8 = начало.
5. Оптимизация поиска - Flash, это uint16_t, поэтому первый проход делать по сравнению начального uint16_t номеров. (Мод - сравнивать не по 0 слову, а по 1. В 0 слове лежит код города, а он не уникален)
Без оптимизаций, выйдет < 1к чтений/проверок для нахождения номера. Короче, "пара ms".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 12:35 
Заглядывает иногда
Аватара пользователя

Зарегистрирован: 23 июл 2010, 09:54
Сообщения: 182
Откуда: Чебоксары
john1770 писал(а):
За таблицей с номерами в ЕЕПРОМ создать индексную таблицу и по ней искать .
Правда придется ее пересчитывать каждый раз когда меняется основная.


Или перед таблицей номеров (все равно максимальное кол-во номеров ограничено). Каждый раз переписываете индексную таблицу, упорядочивая по возрастанию или по убыванию номера телефона. К этой таблице можно будет применить методы быстрого поиска, например метод деления пополам.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 14:19 
Старожил

Зарегистрирован: 08 авг 2013, 09:43
Сообщения: 1460
На самом деле даже диапазон номеров 81000000000-89999999999 занимает 34 бита. Но DEF коды у нас ведь определенные. Т.е. 3,4,8 и 9 после 8ки может идти только. Уже опять же если по этой цифре отделить, то остаток уже легко в uint32_t вписывается. Можно 4 отдельных таблички завести. А там уже может и последовательно считывать всю табличку достаточно быстро будет.
Если нет - то наверное оптимальнее хэш-таблицу поиска сделать. Например брать CRC8, где результат будет позиция номера в массиве, а оставшуюся половину таблицы (у нас 64K / 4 табилицы = по 512 х 4-байтовых ячейки можно хранить, а CRC = 256 ячееек) использовать для разрешения коллизий.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 15:52 
Старожил

Зарегистрирован: 08 авг 2013, 09:43
Сообщения: 1460
Еще как вариант: Фильтр Блума. Но возможны ложно-положительные срабатывания и посмотреть текущий список номеров никак нельзя будет. Хотя ложноположительных я прикинул даже банально для 1 функции CRC16 будет шанс коллизии менее 0.002%.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 16:17 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3113
отсортировать строки по возрастанию при записи, причём можно отдельно хранить отсортированные индексы чтобы каждый раз при добавлении всё не перелопачивать, хотя тоже не особо большая проблема. ну а дальше бинарный поиск и тогда прочитать надо будет максимум десяток номеров.
хотя все 64кбит даже на 400кГц целиком прочитаются за 150мс в чём сложность просто читать всё и на ходу сравнивать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 17:37 
Старожил

Зарегистрирован: 08 авг 2013, 09:43
Сообщения: 1460
Ну это если список не изменять с самого ус-ва. Только я тогда вообще не вижу смысла в EEPROM внешней, когда можно в прошивку (flash) захардкодить номера. Вон с помощью gperf можно сгенерить идеальную хеш функцию сразу на C/C++ по заданному списку номеров, для быстрого поиска )


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: M340


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB