Black List — HackZona.Ru

Black List

Black List

Тип статьи:
Со старой ХакЗоны.
… Допустим мы имеем дело с терминалами, у которых страничная (DATA PAGE) организация памяти (например терминалы фирмы INGENICO).
Каждая DATA PAGE имеет размер памяти SIZE Кб. У нас есть несколько страниц N, на которых расположен Black List (то есть список карт, обработка которых терминалу запрещена).
Например:
....Card Nb............Exp.Date...FIRST and LAST NAME
4234567890123456.....0106.....PETR IVANOV
4234567890123457.....1205.....YURIY PANCHENKO
5338637890128..........0406.....ANDREY BOGATCHUK
-//--//--//--//--//--//--//--//--//--//--//--//--//--//-
6487387534729137.....1107.....VITALIY KLICHKO

… То есть информация упорядочена в порядке возрастания по полю, которое соответствует номеру карты клиента (номер карты может состоять минимум из 13 цифр, а максимум из 19 цифр).
… Приходит аналогичная информация расположенная на М страницах (также по SIZE Кб каждая). Но помимо двух этих полей имеется дополнительная информация по каждой карте, в которой указаны изменения (добавить (1) или удалить (0)) данную карту из Black List.
… При этом размер памяти в приборах обычно ограничен и нет возможности выйти за пределы более чем N+M DATA PAGE. Использовать динамическое распределение памяти нельзя. То есть все используемые массивы должны быть известного размера.
… Необходимо выполнить данные изменения в Black List.

… Списки Black List на страницах N и M, это списки ворованных или потерянных карт. И очень часто приходят обновления (нашли карту или опять кто ее лишился).
… Конечно под DATA PAGE можно понимать и обыкновенные файлы, что никак не убавляет и не осложняет поставленную задачу.

… Решение.
....I способ (сложность: N x M).
… Самое простое и крайне не эффективное решение: Берем первую пришедшую запись и обрабатываем ее. То есть ищем ее место, а потом удаляем (подтягивая весь оставшийся хвост) или добавляем (передвигая все остальные на один до конца). И так для всех пришедших карт на страницах М. То есть не трудно догадаться о сложности такого решения (NxM), а в этом мире борьба идет за секунды.

....II способ (Оптимальное решение. сложность: N).
… Допустим пришло три записи на страницах M с признаками {0, 1, 0}. То есть первую и третью удалить, вторую добавить.
1. Заведем одну переменную Temp и присвоим ей значение первой записи списка на страницах М.
2. Начинаем проход с самого начала по записям страниц N пока не доходим до записи соответствующей переменной Temp, то есть первой записи на страницах M.
3. Как ее обнаружили удаляем, а переменной Temp присваиваем значение второй записи со страниц М.
4. Продолжаем просмотр записей страниц N, одновременно передвигая их, так как была удалена одна запись и этот процесс продолжаем не до конца, а до места вставки переменной Temp, которая напоминаем уже соответствует второй записи страниц M.
5. В освободившееся место благополучно ее вставляем и присваиваем Temp последнюю третью запись со страниц М.
6. Продолжаем проход повторяя процесс описанный выше.

… Таким образом отсекаются проходы для каждой записи страниц M до конца по страницам N.

… Возникает справедливый вопрос: Как быть с таким алгоритмом, если пришли записи, которые надо только добавлять.
… Это порождает очередь (FIFO): первым пришел, первым ушел.
… Например: Пришли три записи и все три надо добавить. Добавили первую на страницы N, но одну запись с этой позиции помещаем в очередь так как не было свободного места. В следующую позицию ее добавляем, а оттуда запись помещаем в FIFO. В FIFO хранится одна запись. И так далее пока не добавим вторую запись. В FIFO появится две записи. При добавлении последней третей записи получаем FIFO из трех записей.
… Понятно данная FIFO будет существовать до конца, пока не обработаем все записи на страницах N. Но если бы пришли записи (а они наверняка есть), которые надо удалять, то эти записи уменьшали бы размер FIFO.
… Но все мы знаем, что такое очередь, и главный вопрос где ее хранить. Хранить мы ее будем на страницах M. В позициях уже рассмотренных элементов. Первая позиция освобождается благодаря буферу Temp, а размер FIFO никогда не превзойдет количества вставленных элементов и в худшем случае будет совпадать с этим количеством.
… А введя два дополнительных указателя (POINTER_1 и POINTER_2) на позиции будем знать с какой позиции взять запись, а в какую добавить.
… Таким образом наша очередь (FIFO), преследует (то увеличиваясь, то уменьшаясь или вовсе пропадая) исчезающую информацию на страницах M.

… Оптимизация данного алгоритма связана с поиском места Temp на страницах N и продолжение прохода начиная с этой позиции.
… Это применимо в двух случаях
— Всегда для первой записи со страниц M;
— в остальных случаях очередь должна быть нулевого размера (указатели POINTER_1 и POINTER_2 совпадают) и не надо двигать элемент со следующей позиции на предыдущую.

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

Комментарии

Нет комментариев. Ваш будет первым!