:: Игры Разума
Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Это не про внутренние ID значения в базе данных, а внешние. Немного искусственный пример:
- компания заключает договора с клиентами
- договора имеют целочисленный номер
- желательно экономить номера
- допускается повторно использовать незадействованные номера ("дырки", далее Д)
Вот задача и состоит в поиске этих дырок в БД.

Итак, что есть Д? Это последовательность занятых номеров (хотя бы один занятый номер), а за ним - последовательность незанятых, условленной минимальной длины (ну, потому-что 1-2 незанятых номера - это у нас норма, а >10 это выделенный диапазон номеров, но по разным причинам - неиспользованный) - такая последовательность далее названа "ступенька вниз".

Далее, как определить наличие Д: это такая серия: 1 задействованный номер + несколько незадействованых. Оказалось, что работает технология из электроники - "цифровой фильтр с линией задержки (далее ЛЗ)" - т.е. мы (при помощи ЛЗ приводим нужные номера в одну точку, и суммируем эти приведенные номера на предмет события, что должно быть: 1 присутстсвующий номер, AND столько-то отсутствующих. ЛЗ в данном случае - это всего лишь оператор "номер=номер+-1". Эти операции ЛЗ и суммирования оказалось можно выполнить в SQL-SELECT операторе, в его WHERE (т.к. WHERE применяется к каждой записи таблицы)

Вот получился код, как ни странно, он ищет Д, даже правильно (ну, у нас есть бумажный журнал Д, вот она его повторят, и правильно ищет границы занятости номеров в выделенных агентам диапазонах номеров)... далее см. комментарии в коде...
Часть текста скрыта
* Далее - поиск внутрилежащих (не первой и не последней) дырок. Вообще, дырку найти практически невозможно за короткое время. Например, представь:
* 100 тыс номеров, причем известно, что есть дырки в <1 тыс номеров где-нибудь посередке, их несколько
* Значит надо сделать > 100тыс/1тыс=100 проверок, - долго, а дырки нужно найти и на порядок меньшие...
* Автокорреляция последовательности занятых номеров! Сначала выберем ВСЕ использованные номера в курсор, но не просто номера, а:
* ...номер-4, номер-3, номер-2, номер-1 (-0 - НЕ НАДО!) Обьединим эти выборки UNION [DISTINCT] в "курсор"
* далее: SELECT номер WHERE номер NOT IN (SELECT * FROM "курсор") - вся фишка в "NOT" - значит антикорреляция
* смягчить реакцию на одиночные "всплески" номеров можно добавлением в UNION-курсор нескольких значений: номер+1, номер+2...
* этим самым получим особые точки - ГРАНИЦЫ перехода из блока (серия использованных номеров) в дырку (прогал в использованных номерах) !
* Хорошо работает, если номера заняты кучно - получается небольшые массивы особых точек (например, после кампани1 печати серийно нумерованых договоров)
* Плохо получается, если номера заняты шумоподобно - массив особых точек большой (реально заключенные договора по заранее нумерованным и напечатанным)...
* Вобщем, вышеописанное - это "цифровой фильтр" с линиями задержки (ЛЗ) и на выходе с сумматором (здесь OR/AND-оператор) с весовыми коэфф. от каждого:
* Пусть, во всей выборке номеров (ВсНо), мы хотим отловить сигнал "ступенька вниз", т.е. такие места в ВсНо, где наблюдается последовательность:
* - непрерывная последовательность N присутствующих номеров (ПрНо)
* - затем непрерывная последовательность M отсутствующих номеров (ОтНо)
* - в результате мы хотим получить TRUE на выходе фильтра в особой точке - граничном номере (ГН), ПОСЛЕДНИМ ПрНо ПЕРЕД НАЧАЛОМ ОтНо
* Чтобы получить TRUE (отфильтровать) ТОЛЬКО ГН "ступенька вниз", можно построить логическое произведение,
* состоящее из N+M рядом лежащих с ГН номеров, которые мы их "видим" в одной "временной" точке - ГН - при помощи отводов от ЛЗ:
* - ПрНо: наличия сигналов (номеров) на N отводах ЛЗ, причем отводов, превращающих мЕньшие номера в бОльшие (номер+1, номер+2...),
* - ОтНо: факт отсутствия сигналов (номеров) на M отводах ЛЗ, превращающих бОльшие номера в мЕньшие (номер-1, номер-2...).
* Представим последовательность номеров на оси абсцисс, (горизонтальная ось, где откладывается номер,
* Представим задержку в ЛЗ как перемещение на линии абсцисс, (горизонтальная ось, где откладывается номер,
* по оси ординат, соответственно, только 1/0 - наличие/отсутствие этого номера). Тогда операция "задержка" выражается как операция суммирования:
* номер+1, или номер-1 и т.п.
* Эти элементарные операции - задержка (и булевы операции) - можно выполнять в WHERE:
* SELECT WHERE номер [NOT] IN (SELECT номер-1...)
* а значит для ВСЕХ ПрНо ОДНОВРЕМЕННО, в одной команде SELECT!Итак:
RELEASE B && в этот массив соберем и вернем особые точки, ГН
LOCAL m.ВсНо, m.ПрНо, m.ОтНо && это курсор всех исходных занятых номеров (ВсНо), курсоры ПрНо и ОтНо (внимание! буквы в именах - русские)
m.д = Самовызов("дырка") && дырка д.б. больше этого размера (мин. размер низины "ступени вниз")
m.б = Самовызов("блок") && макс. расстояние от ГН до ближайшего номера вверх, чтобы считать их оба одной серией номеров
m.з = Самовызов("заполнение") && мин. заполнение вершины "ступени вниз", в процентах (%), чтобы отсеять слабозаполненные серии номеров
m.п = Самовызов("переход") && минимальный размер НЕПРЕРЫВНОЙ серии ПрНо (вкл. сам ГН) перед переходом вершины в низину "ступени вниз"
m.u = Самовызов("UNION") && ограничение на кол. UNION-операторов в VFP (в VFP - вроде не лимитировано, но: длина строки, время выполнения, все такое...)
m.ВсНо = SYS(2015)
SELECT 0
SELECT номер INTO CURSOR (m.ВсНо) READWRITE NOCONSOLE
INDEX ON номер TAG номер && последующим SELECTам этот индекс не сильно нужен, похоже, они их сами на-лету создают, если им надо
* Далее делаем UNION-SELECTы из ВсНо, которые сразу и DISTINCT-обьединяют, т.к.
* Учти, количество UNION пропорционально увеличивает время выполнения (на каждую добавляемую запись идет поиск на существование номера,
* в нашем случае размер курсора на 1м же UNION примерно стабилизируется, поэтому - пропорционально...)
* Практика показывает, что СОЗДАНИЕ этих UNION-курсоров и занимает основное время всего алгоритма, хотя и выполняется в локальном курсоре...
* Собственно в этих выборках и происходит "низкочастотная фильтрация" (ЛЗ,UNION) последовательности входных номеров
m.s = "" && макрострока UNION-SELECTов для ПрНо-фильтра: номер IN (эта выборка) - это будет часть фильтра ПрНо
* создаем макростроку ПрНо: UNION-набор SELECTов с выбираемыми значениями с N отводов для поиска ПрНо {номер+1, номер+2, номер+3...номер+N}
FOR m.i=1 TO MIN(m.б, m.u) && создаем макростроку ПрНо - UNION-набор SELECTов
m.s = SRAZDS(m.s, " UNION ", "SELECT номер+"+TRANSFORM(m.i)+" FROM "+m.ВсНо)
ENDFOR && создавали макростроку ПрНо - UNION-набор SELECTов
SELECT 0 && выполняем макростроку - выбираем ПрНо-курсор
m.ПрНо = SYS(2015)
&s INTO CURSOR (m.ПрНо) NOCONSOLE
m.s = "" && макрострока UNION-SELECTов для ОтНо-фильтра: номер NOT IN (эта выборка) - это будет часть фильтра ОтНо
* создаем макростроку ОтНо: UNION-набор SELECTов с выбираемыми значениями с M отводов для поиска ОтНо {номер-1, номер-2, номер-3...номер-M}
FOR m.i=1 TO MIN(m.д, m.u) && создаем макростроку ОтНо - UNION-набор SELECTов
m.s = SRAZDS(m.s, " UNION ", "SELECT номер-"+TRANSFORM(m.i)+" FROM "+m.ВсНо)
ENDFOR && создавали макростроку ОтНо - UNION-набор SELECTов
SELECT 0 && выполняем макростроку - выбираем ОтНо-курсор
m.ОтНо = SYS(2015)
&s INTO CURSOR (m.ОтНо) NOCONSOLE
m.s = "" && макрострока AND-фильтра IN-SELECTов для ПрНо, которые должны НЕПРЕРЫВНО прилегать к ГН слева (чтобы отсеять одиночные и небольшие всплески...)
* создаем макростроку ОтНо: AND-набор SELECTов с выбираемыми значениями с M отводов для поиска ОтНо {номер+1, номер+2, номер+3...}
FOR m.i=1 TO MIN(m.п-1, m.u) && создаем макростроку ПрНо - AND-набор SELECTов
m.s = m.s + " AND " + " номер IN (SELECT номер+"+TRANSFORM(m.i)+" FROM "+m.ВсНо+")"
ENDFOR && создавали макростроку ПрНо - AND-набор SELECTов
* Собственно Автокорреляция (основной выборки номеров ВсНо с ПрНо-курсором и ОтНо-курсором), сумматор отводов с ЛЗ с нужными весовыми коэфф.
* Получаем массив особых точек, ГН, из ВсНо
* Свойства этой выборки, вернее, свойства полученных ГН:
* - гарантировано присутствуют в исходном списке (т.е. точно существующие номера)
* - гарантировано после них присутствует "прогал" в номерах, длиной в кол. UNION-операторов в m.ОтНо
* - гарантировано имеют до себя хотя бы 1 номер на длине в кол. UNION-операторов в m.ПрНо... как бы сделать счетчик номеров в "вершине ступени"
* - на концах исследуемого диапазона (1..m.h) извлечение не произведено по естественным причинам (не достаточно данных для определения ГН)
* - гарантирована НЕПРЕРЫВНАЯ последовательность ПрНо перед ГН, которая есть количество фильтров "номер IN (SELECT номер+1,2,3..."
RELEASE G
SELECT * FROM (m.ВсНо); && при любом фильтре исходным набором являются ФИЗИЧЕСКИ присутствующие номера
WHERE BETWEEN(номер, m.l+m.б+1, m.h-m.д-1) AND; && это просто фильтр на границы возвращаемых номеров (не анализируем края диапазона номеров)
номер NOT IN (SELECT * FROM (m.ОтНо)) AND; && фильтр на ОТСУТСТВИЕ ОтНо на низине "ступеньки вниз"
номер IN (SELECT * FROM (m.ПрНо)); && фильтр на ПРИСУТСТВИЕ ПрНо на вершине "ступеньки вниз"
&s; && в точке ГН обязательна НЕПРЕРЫВНАЯ последовательность вот стольких ПрНо
INTO ARRAY G;
ORDER BY 1; && мЕньшие номера - в начало массива
NOCONSOLE
IF _TALLY>0
* =massedit(@G, 1, m.a)
DIMENSION G[ALEN(G)] && ранее это был 2-массив [k,1], превратим его в 1-массив
=ASORT(G)
* Удалим некоторые найденные ГН, "ступени вниз", не полностью соответствующие условиям (т.к. мы нашли немного лишних)
SELECT (m.ВсНо)
FOR m.i=1 TO ALEN(G) && анализатор найденных ГН
m.x = G[m.i] && очередная ГН
COUNT FOR BETWEEN(номер, m.x-m.б+1, m.x+0) TO m.n && число ПрНо в вершине "ступени вниз" (д.б. в меру заполнено)
COUNT FOR BETWEEN(номер, m.x+1, m.x+m.д-1) TO m.m && число ПрНо в низине "ступени вниз" (д.б. =0)
IF m.n<m.б*(m.з/100) .OR.; && плохо заполнена вершина "ступени вниз"
m.m>0 && в низине "ступени вниз" есть ПрНо
LOOP
ENDIF
* заполняем выходной 2-массив [ГН, длина_дырки], вернуть количество его строк
LOCATE FOR номер=m.x && не проверяем на FOUND, т.к. однозначно это есть "ступень вниз"...
SKIP && измеряем длину дырки (ищем следующий занятый номер). Тоже не проверяем на нахождение, т.к. это д.б. "внутренняя" дырка...
m.r = m.r+1
DIMENSION parDOP1[m.r,3]
parDOP1[m.r,1] = m.x
parDOP1[m.r,2] = номер-m.x-1
ENDFOR && анализатор найденных ГН
=ASORT(parDOP1,1) && окончательная сортировка
ENDIF && выборка номеров не пуста
RELEASE G
DO CLOSER WITH m.ВсНо, m.ПрНо, m.ОтНо

Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
Олег, привет - ничего не понимаю в Селектах

ps убрал лишние строчки


------------------
Тяжело согнать курсором муху с монитора ...




Исправлено 2 раз(а). Последнее : Равиль, 22.12.13 18:15
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Равиль, не вьехал, что значит "я не понимаю в SELECT"-х, Ты это должен прекратить, и наоборот, говорить, что мол, ваши селекты д.б. более правильные, вот таие типа ...

Я предложл полуматематическое "решение", я не смог санализировать корректность механики счета дырок, хотел услышать мнение... хммм...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
of63
Равиль, не вьехал, что значит "я не понимаю в SELECT"-х, Ты это должен прекратить, и наоборот, говорить, что мол, ваши селекты д.б. более правильные, вот таие типа ...

Когда-то тестили скорость работы селектов с аналогичными решениями без них - селекты частенько проигрывают по времени исполнения.
Думаю у сторонников селектов есть шанс опровергнуть это утверждение

of63
.. Я предложл полуматематическое "решение", я не смог санализировать корректность механики счета дырок, хотел услышать мнение... хммм...

Значит решил "поверить музой алгебру" - тебе это удалось


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Равиль, рад тебя видеть, я блин, блин... "алгебры множеств Ли", ты не представялешь, как это интересно !Все интересно, что и пытаюсь показать... )))
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
of63
Равиль, рад тебя видеть, я блин, блин... "алгебры множеств Ли", ты не представялешь, как это интересно !Все интересно, что и пытаюсь показать... )))

Я тоже рад !
Олег, чтоб заценить твой подход нужно потрогать практический работающий пример.


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Ну, я стеснняюсь, инда ... Про потенциалы?
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
of63
.. Про потенциалы?
а я в электронике без потенции ...


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
я тоже, хз, хочулия, могулия, но не важно! Электроники и без нас выживут )))
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Пытался найти, что-то приличсчисвующеке слуявай, Равиль, привет )))
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Это как www.youtube.com
все5 не так "http://www.youtube.com/watch?v=Qm9gUNbSqlk"
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
Олег приезжай в Екатеринбург в мае!


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
[color=Red][/color]ВсетакиЮ нужно лично общнуться, вот не вижу продолжненияч п-разговора.

Оказалось, в аскен, не работаюи интуитивные и-ы"...Как же достучаться до Равиля...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Приехать не реально, и смысла не вижу, (все умирает, а в процессе смерти - нет смысла мотаться по стране)
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Боянистый вопрос...
LOCAL lnMaxInterval
lnMaxInterval = 10
CREATE CURSOR test (ID i)
INSERT INTO test (ID) VALUES (1)
INSERT INTO test (ID) VALUES (2)
INSERT INTO test (ID) VALUES (4)
INSERT INTO test (ID) VALUES (5)
INSERT INTO test (ID) VALUES (6)
INSERT INTO test (ID) VALUES (9)
INSERT INTO test (ID) VALUES (10)
INSERT INTO test (ID) VALUES (11)
INSERT INTO test (ID) VALUES (12)
INSERT INTO test (ID) VALUES (120)
SELECT p1.Start, p2.End ;
FROM ;
(SELECT RECNO() rn, Start ;
FROM (SELECT t1.ID + 1 Start ;
FROM test t1 ;
LEFT JOIN test t2 ;
ON t1.ID = t2.ID - 1 ;
WHERE t2.ID IS NULL) a1) p1 ;
INNER JOIN ;
(SELECT RECNO() - 1 rn, End ;
FROM (SELECT t1.ID - 1 End ;
FROM test t1 ;
LEFT JOIN test t2 ;
ON t1.ID = t2.ID + 1 ;
WHERE t2.ID IS NULL) a2) p2 ;
ON p1.rn = p2.rn ;
WHERE p2.End - p1.Start < m.lnMaxInterval


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
of63
Автор

Сообщений: 25256
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Блин, Игорь, какого года баян?
Я тебе вобще скажу - ты убиваешь положительное самомнение слушателей тебя... Ты хоть под..и немного

Вобще - от отсутсвия самоценности - убиться можно... Тебе сколько лет?



Исправлено 2 раз(а). Последнее : of63, 22.12.13 22:50
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
Игорь, у меня твой запрос выдает нечто ... или так задумано ))


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
Равиль
Игорь, у меня твой запрос выдает нечто ... или так задумано ))

Игорь, извиняюсь - сейчас глянул еще - запрос правильно отрабатывает - не обратил внимание, что у тебя в условии стоит знак "меньше" (< m.lnMaxInterval), из контекста задачи ожидалось условие "больше".


------------------
Тяжело согнать курсором муху с монитора ...
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
У меня он выдаёт не "нечто", а курсор с 2 записями. Работает, естественно, только в VFP9, т.к. тут сплошные подзапросы во FROM. В старых версиях то же самое нужно делать отдельными запросами (5 шт. выйдет - ну или 3 запроса и 2 UPDATE для прописывания "номеров строк" - т.к. RECNO() в многотабличном запросе не работает).
start end
3     3
7     8
Что соответствует поставленному условию поиска пропусков номеров. Интервал "дырок" 13-119 не попадает т.к. он "слишком большой".


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Поиск "дырок" в (автоинкрементных) номерах ID
Равиль

Сообщений: 6555
Откуда: Уфа
Дата регистрации: 01.08.2003
Igor Korolyov
У меня он выдаёт не "нечто", а курсор с 2 записями ...
Да, это я успел заметить, см. выше.
Интересно было сравнить скорость - накидал тест - у меня запрос работает в 1,4 - 1,5 раза медленнее скана:


------------------
Тяжело согнать курсором муху с монитора ...




Исправлено 1 раз(а). Последнее : Равиль, 23.12.13 16:31
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 16 (Гостей: 16)

© 2000-2024 Fox Club 
Яндекс.Метрика