Arduino.ru

совет: малина

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

что за база, сортирована ли, тока я знаю 6 алгоритмов поиска, что говорить о профессионалах...на I-286  в несортированной базе поиск шел минуты (правда сначала делал сортировку)

Дак дибэйз сразу индексы правил при аппенде вроде. Зачем там доп.сортировка?

критично энергопотребление, поэтому nano. если не потянет то teensy 3.2

Вы бы для начала объем базы озвучили и требуемую скорость реакции. Может и полчаса - не срок.

объем базы - 5 тысяч 4х байтных ключей (UIDы mifare classic)

требуемая скорость - пара секунд

У milfare uid = 8 байт

прошу прощения, ошибся, вы правы

Базу нужно отсортировать, тогда поиск ключа осуществляется банальным делением пополам. Раз ключи уникальны, то и соответствующее им четырёхбайтное число - уникально. Двух секунд в этом случае хватит пробежаться раз дцать по базе, думаю.

8*5000=40000 байт. Как вы это в нану планировали запихать? Хотя бы на уровне идеи...

На уровне идеи - я планировал заплатить тому, кто сталкивался

Но если ткнуть пальцем в небо, то наверно действительно бы разделил базу на много частей, рассортировав на файлы скажем по первым двум байтам УИДа и плата бы загружала уже небольшой кусок для анализа.

Не надо на несколько частей - простенькая программка для компа для сортировки, и запись в файл. Дальнейший поиск тривиален: размер записи известен (8 байт). Читаем посередине, если прочитанный ключ больше, чем проверяемый - уходим в поиске влево, делим напополам там и т.д. Если меньше - уходим вправо, делим напополам там.

Вот: https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA

Делов - на полчаса, вместе с проверкой. Надо только отсортированный массив в файле.

40 килобайт это всего  80 секторов по 512 байт, думаю, даже в несортированной базе поиск в 2 секунды уложится. 

В самом худшем случае будет 80 чтений с SD и 64х80 сравнений uint64_t

Может, и справится, но линейный поиск - такое себе, с точки зрения эффективности... У линейного поиска - O(n), у бинарного - O(log(n)), емнип.

дак я за бинарный поиск и не спорю, он намного быстрее, я к тому, что даже если в лоб решать, перебором, мошт в 2 секунды и уложица, не привлекая внешний комп.  Ну а если можно привлечь и отсортировать на нем, тогда вапще проблемы никакой нет. 

на СТМ32 точно справится линейный поиск, с запасом, там полфайла сразу прокэшировать можно. ТС, не думал про СТМ?

Ещё специфисский вариант, приходящий в голову: делим диапазон на поддиапазоны, для каждого поддиапазона чисел - свой файл, можно несортированный. Выясняем, в какой поддиапазон входит искомый ключ, открываем нужный файл, ищем там линейным поиском. Хорошо канает в случае равномерного распределения ключей по поддиапазонам.

из-за других причин я могу пользоваться только nano или teensy

Парни, ну вот даже среди вас, собаку на этом съевших и то были разные мнения.

Ну чо я буду шишки набивать. Просто сделайте, а я буду благодарен

ну я так и представлял примерно, ведь если сделать 255 файлов (тупо по первому байту УИДа) то искать в файле совсем немного останется 

Так тебе как сделать? Линейным поиском? Давай так: могу проверить на Uno, сгенерировав твои 4000 записей и впихнув их на SD. Напишу линейный поиск, посмотрим, что по быстродействию. Стучись в скайп porokhnya_dmitry, даже цену обсудим - возможно, оно и не будет стоить озвученную тобой ;)

По первому байту UID'а - не покатит, будет ОООЧЕНЬ неравномерное распределение, посмотри сам на базу ключей ;)

По последнему. И читать задом-наперед. Заодно и враг не догадается.

это можно использовать для сокращения базы.

Меня прикололо заявление ТС, что Нано нужна "по причинам энергопотребления" :) На фоне этих слов условие использовать только Нано или Тенси выглядит высосанным из пальца.

Я бы "голубую таблетку" СТМ32 взял - она и по размеру не сильно больше Нано. и по "энергопотреблению" :) Зато у нее 128К флеша и 20К оперативки, в ней можно работать с базой в несколько раз больше требований ТС

Или пусть ТС четко озвучит, почему именно Нано?(диплом? :)) - потому что я не вижу смысла трахаться стоя в гамаке, когда рядом удобная кровать :)

в свое время при выборе полагались на эту таблицу:

где нано на CH340 выглядит неплохо. Сейчас их просто партия имеется и в куче устройств уже установлены. Зачем лезть в кровать, когда и в гамаке всех устраивает?

ну, во-первых. даже в этой табличке Нано никак не выделяется экономичностью.

Во-вторых, если вопрос энергопотребления реально важен для проекта, то в готовом виде ардуины никто не использует. Немного доработав плату, потребление любой из ардуино можно понизить в тысячи раз (я не ошибся - именно в тысячи - от одной батарейки плата будет работать годами). Поэтому, на самом деле - эти данные абсолютно "ни о чем". То. что вы на них ориентируетесь - доказывает как раз то. что энергосбережения в вашем проекте нет вовсе :)

Ну а СТМ32 я предлагаю не просто так. Она реально занчительно лучше подходит под задачу.

я ему про это еще в #19 удочку закидывал

ну, ТС похоже заранее закупился кучей Нано, не подумав. что вообще использование отладочных плат в готовых проектах - само по себе бред. А теперь ему надо эти Наны использовать. иначе будет убыток :)

Короче: решили с ТС вопрос, тупой линейный поиск по базе из 4000 ключей - 300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

Генерация 4000 8-байтовых ключей с записью на SD - 600 миллисекунд, за это брать не стал :))))

Что-то такое адское я припоминаю. Это система, к которой выходили кривые обновления с опозданиями и приходилось вручную прямо в коде писать с какого года рождения пенсию насчитывать по новым правилам?

Вот.  Я, значить, не ошибса. 

300 рублей? :)))

вы конечно философы тут, потроллить ТС каждый может) а человек за 10 минут сделал

Угу :) Поддержка в комплекте - бесценно :)))

Ты б бревно сначала вытащил бы, а потом уже философов благодарил.

ну это уважуха однозначно - я бы 2 дня только собирался бы :)

Хорош троллить :)

извините, не имела заметить, решена)
господин DIYMan, извините

р е а л и з у е м о - maslachenko767@mail.ru

Это было очень давно, версия под ДОС  - 1.07 ))) под винды ничего не писал, на ней кстати сделал расчет таблиц цистерн с горючкой удоженных на бок с измерением мерной динейкой через 1 миллиметр )))

Надо бы название темы откорректировать: 5000 - это не огоромная база, огромная начинается от 4294967297. С учетом того, что SD сейчас до 256 Гб - вполне реальная задача.

  не получается исправить)

Вот и спроси у ТС - разрешит - выложу.

если это кому то пригодится - я только "за"

Ок, чуть позже выложу - сейчас не за рабочим компом.

Собственно, вот весь код для генерации 4000 ключей и тупого поиска наихудшего варианта (т.е. перебором всей БД):

//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// настройки прошивки
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#define KEY_SIZE 8 // размер ключа, байт
#define KEY_FILE F("keys.db") // имя файла с ключами на карточке
#define SD_CS_PIN 10 // номер пина CS для SD-карты
#define SERIAL_SPEED 57600 // скорость работы с Serial
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#include <SD.h>
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
typedef uint8_t KEY[KEY_SIZE];
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
bool generate(uint16_t count) // генерируем ключи
{
  File workFile = SD.open(String(KEY_FILE).c_str(),FILE_WRITE | O_TRUNC);

  KEY record = {0};
  uint16_t val = 0;
  if(workFile)
  {
    for(uint16_t i=0;i<count;i++)
    {
      val++;
      memcpy(record,&val,min(sizeof(val),KEY_SIZE));
      workFile.write(record,sizeof(record));
    }

    workFile.close();
    return true;
  }
  return false;
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
bool linearFind(KEY& needle) // линейный поиск
{
  bool result = false;
  File workFile = SD.open(String(KEY_FILE).c_str(),FILE_READ);

  if(workFile)
  {

    KEY record;
    while(workFile.available())
    {
      workFile.read(record,sizeof(record));
      
      if(!memcmp(needle,record,sizeof(needle)))
      {
        result = true;
        break; 
      }
    }
    workFile.close();
  }

  return result;
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void setup() 
{
  Serial.begin(SERIAL_SPEED);
  if(!SD.begin(SD_CS_PIN))
  {
    Serial.println(F("CAN'T INIT SD!"));
    while(true);
  }

  // генерируем ключи
  Serial.println(F("Generating 4000 keys..."));
  uint32_t start = millis();
  bool generated = generate(4000);
  uint32_t elapsed = millis() - start;
  Serial.print(F("Generate time, ms: "));
  Serial.println(elapsed);

  if(!generated)
  {
    Serial.println(F("ERROR GENERATING KEYS!"));
    while(true);
  }
  // конец генерации ключей


  // линейный поиск, существующий ключ
  KEY toFind = {0xA0,0x0F,0,0,0,0,0,0}; // 4000
  Serial.println(F("Find last PRESENT key..."));
  start = millis();
  bool found = linearFind(toFind);
  elapsed = millis() - start;
  if(found)
    Serial.print(F("FOUND"));
  else
    Serial.print(F("NOT FOUND"));
    
  Serial.print(F(", search time, ms: "));
  Serial.println(elapsed);
  // конец линейного поиска существующего ключа

  // линейный поиск, не существующий ключ
  KEY toFind2 = {0xA0,0x0F,0xFD,0xFF,0x12,0x34,0x7D,0xED};
  Serial.println(F("Find last NOT PRESENT key..."));
  start = millis();
  found = linearFind(toFind2);
  elapsed = millis() - start;
  if(found)
    Serial.print(F("FOUND"));
  else
    Serial.print(F("NOT FOUND"));
    
  Serial.print(F(", search time, ms: "));
  Serial.println(elapsed);
  // конец линейного поиска не существующего ключа
  

}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void loop() 
{

}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------