Столкнулся по работе с реальной задачей, которую пока не совсем знаю как оптимально решить.
Ведется запись телефонных разговоров в call center. Есть таблица hystory в которую записываются данные о разговорах.
Среди прочих полей там есть время начала и окончания разговора. Телефонов, разговоры которых записываются довольно много.
Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца).
Количество разговоров в неделю ~70 тыс.
У таблицы есть поле ID, которое проиндексировано. И записи с большей ID соответствует большее(точнее не меньшее) время начала разговора.
Здравствуйте, SergeyBi, Вы писали:
SB>Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца).
В PostgreSQL можно построить соответствующий сложный индекс
Здравствуйте, SergeyBi, Вы писали:
SB>Столкнулся по работе с реальной задачей, которую пока не совсем знаю как оптимально решить.
SB>Ведется запись телефонных разговоров в call center. Есть таблица hystory в которую записываются данные о разговорах. SB>Среди прочих полей там есть время начала и окончания разговора. Телефонов, разговоры которых записываются довольно много. SB>Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца). SB>Количество разговоров в неделю ~70 тыс.
SB>У таблицы есть поле ID, которое проиндексировано. И записи с большей ID соответствует большее(точнее не меньшее) время начала разговора.
SB>Заранее спасибо за варианты.
Подсчитываешь количество разговоров в начальный момент времени init_count.
Формируешь список моментов времени из моментов начала и конца разговоров, которые входят в нужный тебе период времени.
Сортируешь его.
Инициализируешь максимальное количество разговоров max_count = init_count
и текущее количество разговоров count = init_count
Проходишь по этому списку {
если момент времени - начало разговора
count++
если конец
count--
обновляем максимум: max_count = max(max_count, count);
}
max_count - результат
N>Подсчитываешь количество разговоров в начальный момент времени init_count.
Можно считать что равно 0.
N>Формируешь список моментов времени из моментов начала и конца разговоров, которые входят в нужный тебе период времени.
N>Сортируешь его.
Считаем что у меня есть записи только из этого промежутка. Они отсортированы по времени начала разговора.
N>Инициализируешь максимальное количество разговоров max_count = init_count
N> и текущее количество разговоров count = init_count
N>Проходишь по этому списку {
N> если момент времени - начало разговора
N> count++
N> если конец
N> count--
N> обновляем максимум: max_count = max(max_count, count);
N>}
Вот тут я не понял. Что такое "момент времени" при обходе этого списка? Список содержит в себе записи у каждой есть время начала и окончания...
N>max_count - результат
N>
N>>Подсчитываешь количество разговоров в начальный момент времени init_count.
SB>Можно считать что равно 0.
N>>Формируешь список моментов времени из моментов начала и конца разговоров, которые входят в нужный тебе период времени.
N>>Сортируешь его.
SB>Считаем что у меня есть записи только из этого промежутка. Они отсортированы по времени начала разговора.
Но концы не отсортированы Можно конечно отсортировать только концы разговоров и потом слить списки началов и концов. Нам важно получить список моментов времени, когда изменяется количество подключений.
N>>Инициализируешь максимальное количество разговоров max_count = init_count
N>> и текущее количество разговоров count = init_count
N>>Проходишь по этому списку {
N>> если момент времени - начало разговора
N>> count++
N>> если конец
N>> count--
N>> обновляем максимум: max_count = max(max_count, count);
N>>}
SB>Вот тут я не понял. Что такое "момент времени" при обходе этого списка? Список содержит в себе записи у каждой есть время начала и окончания...
N>>max_count - результат
N>>
s[] - массив начал разговоров
e[] - массив окончаний разговоров
n - количество разговоров
minE - того же типа что и время в массивах
int maxC=0;
for(int i=0; i<n; i++)
{
minE = e[i]
int c = 1;
for(int j=i+1; ;j++)
{
if( s[j]>minE )
break;
c++;
minE = min( e[i], e[j] );
}
if (c>maxC)
maxC = c;
}
maxC - ответ
P>s[] - массив начал разговоров
P>e[] - массив окончаний разговоров
P>n - количество разговоров
P>minE - того же типа что и время в массивах
P>int maxC=0;
P>for(int i=0; i<n; i++)
P>{
P> minE = e[i]
P> int c = 1;
P> for(int j=i+1; ;j++)
P> {
P> if( s[j]>minE )
P> break;
P> c++;
P> minE = min( e[i], e[j] );
P> }
P> if (c>maxC)
P> maxC = c;
P>}
P>maxC - ответ
P>
P>вроде так
Неправильно и неоптимально
вот простой тест:
1 8
2 3
4 7
5 6
Выдает 2, хотя на промежутке 5-6 3 соединения. Да и работает O(N^2), когда в моем варианте самой тяжелой операцией является сортировка, которая во всех языках реализована за O(NlogN).
Здравствуйте, Nev0, Вы писали:
N>Неправильно и неоптимально N>вот простой тест: N>
N>1 8
N>2 3
N>4 7
N>5 6
N>
N>Выдает 2, хотя на промежутке 5-6 3 соединения. Да и работает O(N^2), когда в моем варианте самой тяжелой операцией является сортировка, которая во всех языках реализована за O(NlogN).
Насчет сложности — предыдущий вариант сложность не N^2 , a N*c, где с < среднего количества одновременных разговоров.
Согласен, не правильно, если изменить, вроде должно заработать, вот здесь уже сложность N^2? если не больше
int maxC=0;
for(int i=0; i<n; i++)
{
minE = e[i]
int c = 1;
for(int j=0; ;j++)
{
if( s[j]>minE || (s[i]<s[j] && e[i]>s[j]) )
break;
c++;
minE = min( e[i], e[j] );
}
if (c>maxC)
maxC = c;
}
Здравствуйте, pivoo, Вы писали:
P>если честно, алгоритма не понял P>это случайно не количество незавершившихся звонков на момент окончания контрольного времени получается ?
N>Но концы не отсортированы Можно конечно отсортировать только концы разговоров и потом слить списки началов и концов. Нам важно получить список моментов времени, когда изменяется количество подключений.
Я все понял. Отличная идея. Сначала недооценил. Действительно остается только отсортировать время окончания.
Кстати, а как проще всего посчитать среднее колличество(по времени) одновременных разговоров?
Приходит в голову мысль посчитать сумарное время разговоров и поделить эт на реальное время.
Здравствуйте, SergeyBi, Вы писали:
SB>Столкнулся по работе с реальной задачей, которую пока не совсем знаю как оптимально решить.
SB>Ведется запись телефонных разговоров в call center. Есть таблица hystory в которую записываются данные о разговорах. SB>Среди прочих полей там есть время начала и окончания разговора. Телефонов, разговоры которых записываются довольно много. SB>Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца). SB>Количество разговоров в неделю ~70 тыс.
SB>У таблицы есть поле ID, которое проиндексировано. И записи с большей ID соответствует большее(точнее не меньшее) время начала разговора.
Я так понимаю от тебя требуют статистику за определенный период и максимальная загрузка — одна из форм отчетности
Может имеет смысл завести еще одну таблицу, куда можно перегнать данные из history в виде
время — количество звонков в это время
для этого выбираешь оптимальный временной промежуток, скажем 5 минут и подсчитываешь количество запросов в эти 5 минут:
преимущество в том что такую таблицу тебе придется формировать всего один раз в отчетный период, а уже из нее можно графики загрузки рисовать, максимумы-минимумы выдавть и т.п.
если в history пишется ~10 тыс записей в сутки, то в эту базу попадет 288 записей (для 5-мин. интервала), что гораздо быстрее обработать
SB>Заранее спасибо за варианты.
Здравствуйте, SergeyBi, Вы писали:
SB>Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца).
Полагаю, время в таблице хранится с точностью до секунд? Вот и надо для каждой секунды в интересующем нас периоде подсчитать количество одновременных разговоров, а потом взять максимум.
Для эффективного поиска надо создать такой индекс: (start, end, ID). Для каждого момента времени делаем запрос:
select count(ID) from history
where :time between start and end
and start <= :time - :max_duration
где max_duration — максимальная продолжительность разговора, которую надо посчитать заранее. И считаем максимум. Для скорости все это лучше делать в хранимой процедуре, если СУБД позволяет. Кстати, какая СУБД?
Для еще большей скорости можно взять интервал не в секунду, а больше, скажем 5 секунд. Со всеми вытекающими.
Здравствуйте, wildwind, Вы писали: SB>>Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца).
W>Полагаю, время в таблице хранится с точностью до секунд? Вот и надо для каждой секунды в интересующем нас периоде подсчитать количество одновременных разговоров, а потом взять максимум.
W>Для эффективного поиска надо создать такой индекс: (start, end, ID). Для каждого момента времени делаем запрос: W>
W>select count(ID) from history
W> where :time between start and end
W> and start <= :time - :max_duration
W>
где max_duration — максимальная продолжительность разговора, которую надо посчитать заранее. И считаем максимум. Для скорости все это лучше делать в хранимой процедуре, если СУБД позволяет. Кстати, какая СУБД? W>Для еще большей скорости можно взять интервал не в секунду, а больше, скажем 5 секунд. Со всеми вытекающими.
В общем-то правильно. Думаю с таким индексом сложность задачи будет примерно N*log(N). Но в этой ветке было предложено решение без индекса, с как максимум такой же сложностью А минимум с линейной(если индекс на время добавить).
Здравствуйте, wildwind, Вы писали:
W>Здравствуйте, SergeyBi, Вы писали:
SB>>Задача: определить максимальное количество одновременных разговоров за некоторый период времени(например 3 месяца).
W>Полагаю, время в таблице хранится с точностью до секунд? Вот и надо для каждой секунды в интересующем нас периоде подсчитать количество одновременных разговоров, а потом взять максимум.
W>Для эффективного поиска надо создать такой индекс: (start, end, ID). Для каждого момента времени делаем запрос: W>
W>select count(ID) from history
W> where :time between start and end
W> and start <= :time - :max_duration
W>
где max_duration — максимальная продолжительность разговора, которую надо посчитать заранее. И считаем максимум. Для скорости все это лучше делать в хранимой процедуре, если СУБД позволяет. Кстати, какая СУБД? W>Для еще большей скорости можно взять интервал не в секунду, а больше, скажем 5 секунд. Со всеми вытекающими.
Здравствуйте, SergeyBi, Вы писали:
SB>В общем-то правильно. Думаю с таким индексом сложность задачи будет примерно N*log(N).
Так какая СУБД? Для некоторых можно оптимизировать...
Здравствуйте, wildwind, Вы писали:
W>Здравствуйте, SergeyBi, Вы писали:
SB>>В общем-то правильно. Думаю с таким индексом сложность задачи будет примерно N*log(N). W>Так какая СУБД? Для некоторых можно оптимизировать...
Можно конечно отсортировать только концы разговоров и потом слить списки началов и концов. Нам важно получить список моментов времени, когда изменяется количество подключений.
