Возникла проблема, имею N массивов содержащих пары: (временная метка; значение), массивы внутри упорядочены по возрастанию временной метки. Нужно сформировать таблицу из 1+N столбцов
(временная метка и N столбцов значений) и Х строк (кол-во неповторяющихся временных меток).
Сейчас для определения положения вставки элемента в таблицу использую метод
деления попалам LowerBound, но меня не устраивает скорость. Может посоветуете что то более
быстрое.
SeAlG wrote: > Здравствуйте! > > Возникла проблема, имею N массивов содержащих пары: (временная метка; > значение), массивы внутри упорядочены по возрастанию временной метки. > Нужно сформировать таблицу из 1+N столбцов > (временная метка и N столбцов значений) и Х строк (кол-во > неповторяющихся временных меток). > Сейчас для определения положения вставки элемента в таблицу использую метод > деления попалам LowerBound, но меня не устраивает скорость. Может > посоветуете что то более > быстрое. > > Спасибо.
Ой.. Ну, наверное, можно (если память позволяет) сделать общий массив
записей <метка; данные; исходный массив> и отсортировать его за
N*X*(logN+log_X). После чего идти по нему и создавать таблицу по
порядку. Или отсортировать минимальные элементы массива в упорядоченное
дерево (см. сортировку деревом), после чего создавать общесортированный
массив выбирая минимальный элемент из минимальных в массивах и заменяя в
дереве вершину (цена замены — log_N), что даст N*X*log_N, но чуть
сложнее. Быстрее этого нельзя (асимптотически, формально говоря). А что
Вы подразумеваете под LowerBound?
Здравствуйте, SeAlG, Вы писали:
SAG>Возникла проблема, имею N массивов содержащих пары: (временная метка; значение), массивы внутри упорядочены по возрастанию временной метки. Нужно сформировать таблицу из 1+N столбцов SAG>(временная метка и N столбцов значений) и Х строк (кол-во неповторяющихся временных меток). SAG>Сейчас для определения положения вставки элемента в таблицу использую метод деления попалам LowerBound, но меня не устраивает скорость. Может посоветуете что то более быстрое.
Не очень понял, что должна содержать эта таблица, почему именно N+1 столбец. Расскажи поподробнее.
Кодт wrote: > Здравствуйте, SeAlG, Вы писали: > > SAG>Возникла проблема, имею N массивов содержащих пары: (временная > метка; значение), массивы внутри упорядочены по возрастанию временной > метки. Нужно сформировать таблицу из 1+N столбцов > SAG>(временная метка и N столбцов значений) и Х строк (кол-во > неповторяющихся временных меток). > SAG>Сейчас для определения положения вставки элемента в таблицу > использую метод деления попалам LowerBound, но меня не устраивает > скорость. Может посоветуете что то более быстрое. > > Не очень понял, что должна содержать эта таблица, почему именно N+1 > столбец. Расскажи поподробнее. > > А вообще, здесь дело пахнет слиянием массивов.
А как можно ещё понять вопрос? N+1: столбец для метки плюс в значение из
каждого массива попадает в свой мтолбец в строку с этой меткой. Или —
если в массиве такого нет — туда ничего не попадает. Автор темы меня
поправит, если что..
Здравствуйте, Кодт, Вы писали:
К>Не очень понял, что должна содержать эта таблица, почему именно N+1 столбец. Расскажи поподробнее.
ОК. У меня есть история изменения во времени N параметров (достаю их SQL'я).
Мне нужно сформировать таблицу отображающую изменение этих параметров во временни.
1-ий столбец время и дата и дальше N столбцов (по кол-ву параметров) содержащих
значения каждого параметра в определенный момент времени. Каждая строка содержит значение параметра в определенный момент времени, если в этот момент параметр был измерен.
Интервалы измерений у разных параметров различны.
К>А вообще, здесь дело пахнет слиянием массивов.
Можно и так сказать.
SeAlG wrote: > Возникла проблема, имею N массивов содержащих пары: (временная метка; > значение), массивы внутри упорядочены по возрастанию временной метки. > Нужно сформировать таблицу из 1+N столбцов > (временная метка и N столбцов значений) и Х строк (кол-во > неповторяющихся временных меток). > Сейчас для определения положения вставки элемента в таблицу использую метод > деления попалам LowerBound, но меня не устраивает скорость. Может > посоветуете что то более > быстрое.
Извините, в прошлом моём ответе неточность — это надо искать как
пирамидальную сортировку (с модификациями, описанными в сообщении).
Это же — heap sort.
Здравствуйте, raskin, Вы писали:
R>Ой.. Ну, наверное, можно (если память позволяет) сделать общий массив R>записей <метка; данные; исходный массив> и отсортировать его за R>N*X*(logN+log_X). После чего идти по нему и создавать таблицу по R>порядку.
Проблематично формировать промежуточный массив и памяти много надо и долго.
Параметров может быть до 100 у каждого до 50000 значений.
R>Или отсортировать минимальные элементы массива в упорядоченное R>дерево (см. сортировку деревом), после чего создавать общесортированный R>массив выбирая минимальный элемент из минимальных в массивах и заменяя в R>дереве вершину (цена замены — log_N), что даст N*X*log_N, но чуть R>сложнее. Быстрее этого нельзя (асимптотически, формально говоря).
Спасибо попробую, но кажеться это не даст сильного выигрыша, кол-во действий
меньше но они сложнее (формирование дерева дорогое удовольствие).
R> А что Вы подразумеваете под LowerBound?
Вариации реализации деления попалам.
LowerBound — ищем в массиве первый элемент, не меньший указанного, и возвращаем его номер.
UpperBound — ищет в массиве первый элемент, строго больший указанного. и возвращаем его номер.
Если такого элемента нет, то возвращается N — номер несуществующего элемента.
SeAlG wrote: > Здравствуйте, Кодт, Вы писали: > > К>Не очень понял, что должна содержать эта таблица, почему именно N+1 > столбец. Расскажи поподробнее. > > ОК. У меня есть история изменения во времени N параметров (достаю их > SQL'я). > Мне нужно сформировать таблицу отображающую изменение этих параметров во > временни. > 1-ий столбец время и дата и дальше N столбцов (по кол-ву параметров) > содержащих > значения каждого параметра в определенный момент времени. Каждая строка > содержит значение параметра в определенный момент времени, если в этот > момент параметр был измерен. > Интервалы измерений у разных параметров различны. > > К>А вообще, здесь дело пахнет слиянием массивов. > Можно и так сказать.
Так что такое LowerBound? Асимптотически быстрейший алгоритм —
N*T*(logT). Заведите N-элементный массив для сортировки (order) и такой
же (pointer) для номеров текущих элементов. Заполните первый числами по
порядку, а второй единицами/нулями — как удобнее. Произведите этап
построения дерева из пирамидальной сортировки (значениями при сравнении
i и j в первом массиве служат timestamp[i][pointer[i]] и
timestamp[j][pointer[j]]). После чего повторяете процедуру — взять
вершину дерева (минимальный элемент), добавить в таблицу (в последнюю
строку, возможно, придётся создать новую), сделать по тем же правилам
FixHeap (в терминологии algolib.narod.ru)/downHeap (algolist.manual.ru).
в конце надо всё аккуратно проверять на завершение. А что у Вас?
SeAlG wrote: > > Спасибо попробую, но кажеться это не даст сильного выигрыша, кол-во действий > меньше но они сложнее (формирование дерева дорогое удовольствие). >
Нет-нет, оно же полное бинарное. см. algolist.manual.ru — это всего лишь
массив + 3 функции (return a >> 1; return 2*a+1; return 2*a+2). А в
массиве живут всего лишь целые числа от 0 до N-1 / от 1 до N
> R> А что Вы подразумеваете под LowerBound? > > Вариации реализации деления попалам. > LowerBound — ищем в массиве первый элемент, не меньший указанного, и > возвращаем его номер. > UpperBound — ищет в массиве первый элемент, строго больший указанного. и > возвращаем его номер. > Если такого элемента нет, то возвращается N — номер несуществующего > элемента.
Спасибо. Это, наверное, заставляет вставлять в середину таблицы, и
тогда сложность может быть квадратичной.
Здравствуйте, raskin, Вы писали:
R>Нет-нет, оно же полное бинарное. см. algolist.manual.ru — это всего лишь R>массив + 3 функции (return a >> 1; return 2*a+1; return 2*a+2). А в R>массиве живут всего лишь целые числа от 0 до N-1 / от 1 до N
Да я уже посмотрел.
R>Спасибо. Это, наверное, заставляет вставлять в середину таблицы, и R>тогда сложность может быть квадратичной.
Да заставляет, но мне кажеться что это я компенсирую это тем что массивы я получаю асинхронно
с формированием таблицы (тащу из SQL'я на другом сервере, пока выбирающий поток сидит в
SQL'е запросе по уже выбранным массивам строю таблицу, в другом потоке).
Еще раз спасибо, попробую дождаться выборки всех массивов и воспользоваться
вашим алгоритмом может и правда быстрее будет.
Здравствуйте, SeAlG, Вы писали:
SAG>ОК. У меня есть история изменения во времени N параметров (достаю их SQL'я). SAG>Мне нужно сформировать таблицу отображающую изменение этих параметров во временни. SAG>1-ий столбец время и дата и дальше N столбцов (по кол-ву параметров) содержащих SAG>значения каждого параметра в определенный момент времени. Каждая строка содержит значение параметра в определенный момент времени, если в этот момент параметр был измерен. SAG>Интервалы измерений у разных параметров различны.
Если таблица нужна для показа пользователю, печати и т.п (как я понял), то можно поступить след. образом. Сливаем все в один массив, упорядоченный по времени и по номеру параметра (необязательно). Если данные тянутся из базы, это еще проще, можно сразу в такой массив и писать. Потом прямо из этого массива и отображаем постранично на экран или куда угодно. Допустим, надо отобразить строки с метками от t1 до t2. Проходим по элементам с меткой t1 и заполняем столбцы. Дальше в массиве идет диапазон со следующей по времени меткой — заполняем следующую строку, и т.д.
Здравствуйте, wildwind, Вы писали:
W>Если таблица нужна для показа пользователю, печати и т.п (как я понял), то можно поступить след. образом. Сливаем все в один массив, упорядоченный по времени и по номеру параметра (необязательно). Если данные тянутся из базы, это еще проще, можно сразу в такой массив и писать. Потом прямо из этого массива и отображаем постранично на экран или куда угодно. Допустим, надо отобразить строки с метками от t1 до t2. Проходим по элементам с меткой t1 и заполняем столбцы. Дальше в массиве идет диапазон со следующей по времени меткой — заполняем следующую строку, и т.д.
Не не пойдет, каждый параметр лежит в отдельной таблице (это не я придумал и с этим уже ничего не сделать )
и если делать их объеденение средствами SQL то это еще дольше чем то что я сейчас имею. Таблицу (а по сути это
двумерный массив указателей на те куски памяти которые заполнены данными из SQL) я формирую в памяти
и затем использую виртуальный грид (который для отрисовки ячейки через эту ссылочную таблицу получает доступ к данным). Сливать в один массив своими средствами после выборки нет смысла: долго и очень много памяти надо.
SAG>Не не пойдет, каждый параметр лежит в отдельной таблице (это не я придумал и с этим уже ничего не сделать ) SAG>и если делать их объеденение средствами SQL то это еще дольше чем то что я сейчас имею. Таблицу (а по сути это SAG>двумерный массив указателей на те куски памяти которые заполнены данными из SQL) я формирую в памяти SAG>и затем использую виртуальный грид (который для отрисовки ячейки через эту ссылочную таблицу получает доступ к данным). Сливать в один массив своими средствами после выборки нет смысла: долго и очень много памяти надо.
Фишка в том, что сливать надо во время выборки. Не вижу проблем с этим: открываешь N запросов и сливаешь. Тогда будет и быстро и экономно по памяти, дополнительная структура из указателей не нужна, грид будет работать с одним массивом.
Более того, можно пойти дальше и не тащить все данные сразу, а подгружать их по мере навигации. Для этого надо рассчитать "окно" во времени, то есть интервал для меток, и запросить данные с этим условием. В этом случае из каждой таблицы выбирается немного записей, и их можно эффективно объединить на сервере и вытянуть одним запросом, если правильно написать SQL.
Перекуём баги на фичи!
) 