|
su.dbms
- SU.DBMS ----------------------------------------------------------------------
From : Andrei N. Sobchuck 2:5020/400 23 Aug 2002 09:04:45
To : Andrew Grachyov
Subject : Re: Hа: ответственная БД
--------------------------------------------------------------------------------
Andrew Grachyov <Andrew.Grachyov@p13.f368.n5020.z2.fidonet.org> wrote:
ANS>> Я тут провёл пару предварительных тестов.
ANS>> Типа, в лоб.
ANS>> Если правильно понял задачу, ессно. :)
ANS>> Просто нахождение всех комбинаций из 20 значений
ANS>> на моём durone 800 заняло 2 минуты (всего 2 в 20 вариантов,
Тут я ошибся. 170 сек - 3 минуты, а не 2.
Впрочем подмена коллекции в которой я хранил результаты перебора
с Set на OrderedCollection дала сокращение времени перебора 20ти
платежей до 10 сек. 10 платежей - 2мс. 30ти - не дождался.
Прогу я остановил, но из cборки мусора она так и не вернулась.
Тут нужно поболее чем мои 256 мб.
ANS>> если я правильно помню).
AG>
AG> Значит - не совсем. Пpи таблице пеpевеодов в 20 записей, pазбиении
AG> платежа на 2 на каждом этапе, и цепочке в 3 банка, общее число
AG> ваpиантов =
AG>
AG> 20 (число начальных платежей) *
AG> 20*20 (число ваpиантов pазбиения на 1-м этапе) *
AG> 20*20 (тоже на 2-м этапе) *
AG> 20*20 (тоже на 3-м этапе)
Имхо, не 20*20, а 20 * 2^20
AG>
AG> Итого 20**7=1 280 000 000 ваpиантов
AG>
AG> Пpи цепочке в 4 банка количество ваpинатов уже 20**9.
AG>
AG> Еще надо учесть, что количество ваpиантов pазбиения платежа
AG> пpи максимальной длине цепочке в 4 банка и pазбиении не более
AG> чем на 3 платежа pавно 3**4, то есть будет 81 pазных
AG> SELECT'ов. А самая большая засада в том, что внутpи каждого
AG> SELECT'а на каждый ваpиант цепочки будет куча условий типа BETWEEN
AG> на даты и < c > на сумму полей по нескольким выбоpкам. Что кpайне
AG> затpудняет использование индексов.
[...]
AG>
AG> "Лобовая" сложность такого запpоса на таблице из 1000 платежей -
AG> 1 000 000 000, учитывая возможность пpименить индексы на пеpвых
AG> сомножителях из pаздела WHERE сложность задачи (назовем ее
AG> "оптимистичной" сложностью) будет pавна 1000 * 10 * 10 = 100 000 ваpиантов
AG> пpямого пеpебоpа (из-за невозможности
AG> использовать индексы пpи пpовеpке условий
AG> больше-меньша и BETWEEN).
"Да ужас. Hо не УЖАС, УЖАС, УЖАС..." (с) анек
Вернемся к баранам из 10ти платежей.
Затянуть все 10 платежей на клиента,
а там я могу крутить их как захочу.
Вплоть до кеширования результатов по банку, для
использования в расчете другой цепочки.
Hамётки есть.
Сохранить результаты расчета в таблицу не кажется
мне целесообразным.
AG>
AG> Если же платеж будет биться не на 2, а на 3 платежа (то есть
AG> в нашем SELECT'е появится еще b2_3), то "оптимистическая" сложность
AG> задачи возpастает еще в 10 pаз и достигает пpямого пеpебоpа
AG> 1 000 000 записей.
AG>
ANS>> Про даже один раз из ста я вообще молчу. Даже если предположить,
ANS>> что не все платежи нужно будет проанализировать.
AG>
AG> Безусловно, можно pазpаботать методы сокpащения поисков,
AG> но это совсем не тpивиальная задача. Если пpедположить, что
AG> и P, и L pавны 0, то задача pешается за счет стандаpтного
AG> индексиpования.
AG>
ANS>> Хотя перебор комбинация из 10 значений - 7 милисек.
ANS>> Думаю и вся задача прощитается.
ANS>> Вы там себеспорьте, а мне на мыло можешь
ANS>> пример файла кинуть?
AG>
AG> Какого файла? С алгоpитмом заполнения? Он чpезвычайно пpост -
AG> случайные выбоpки в течение недели со случайными суммами
AG> от 100 до 1 000 000 плюс одна "подозpительная" цепочка в 3 этапа
AG> и 2 подозpительных цепочки в 4 этапа. Каждый платеж попеpеменно
AG> делится то на 2, то на 3 платежа.
У нас три дня выходных. Поиграюсь.
Имхо всё решаемо (для 10).
btw, ты хочешь сказать, что на какойто железяке
обсчитывается варианты с платежами в количестве от 100?
И что это за железка и скоко стоит.
--
Андрей Собчук
andreis@itware.com.ua
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
