Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima T, 1. По первому пункту - да. Скорее всего. Массив очень разреженный. Терабайт или нет я не считал. Возможно больше. 2. По второму. Мысль интересная. Мне она напоминает арифметическое сжатие. Буду думать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.06.2018, 11:18 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
hVosttmayton, Поэтому и существуют такие индексы, как BRIN . В фасетном поиске, преимущественно используемом в интернет магазинах, используются интервалы значений. Никто не будет индексировать индивидуально каждую цену или дату. Что-то в Wiki вроде погорячились поддержку BRIN индексов в Oracle Database вписать ))). Ссылки из Wiki только на описание Exadata, да и то, очень понятно как соотносящиеся с BRIN индексами. Хотя, возможно, и ошибаюсь ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.06.2018, 14:02 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TИМХО Если для значения конкретной записи можно вывести уникальный индекс, который никогда не пересечется с другими значениями, то такой индекс отличная замена хэшу, т.к. исключается возможность коллизий и как следствие не нужно хранение исходных данных, т.к. для сравнения двух записей достаточно сравнить индексы. Для таблички OrderDetail Если существует функция типа f(a,b,c,d,e,f) которая отображает любой ключ на целое число (offset) в диапазоне от 0 до 70 тысяч триллионов то мы можем представить таблицу как множество этих чисел. Для удобства поиска их можно положить в хеш-табличку. Но учитывая что все они длинные и (предположительно) могут иметь префикс то возможно стоит подумать о какой-то структуре вроде префиксного дерева. Вообще... префиксность еще надо доказать. Или просто предположить что данные в табличке похожи (к примеру первое поле А имеет низкую кардинальность и содержит всего два значения {male, female} и в формуле поле стоит на старшей позиции. Отсюда кстати еще у меня возникает мысль о том что меняя порядок колонок можно получить некоторые новые характеристики. Например Код: sql 1. 2. 3. 4. 5. 6. поле ProductId определенно является внешним ключиком на родительский элемент Заказа и если его переставить в первую позицию что префиксные свойства будут более ярко выражены. Случайное сходство 10248/42 и 10248 это не более чем архитектурный нюанс. В других БД этого может не быть. Таким-же образом на 2 и 3 места можно передвинуть другие поля которые низко-кардинальны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.06.2018, 23:56 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonДля таблички OrderDetail Если существует функция типа f(a,b,c,d,e,f) Точно существует. Только надо знать кардинальность (количество возможных значений) каждого параметра. Обозначим кардинальность A, B, C, D, E, F, тогда Код: sql 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 08:22 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Надо бы автоматизировать получение формулы для любого числа измеренмй. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 08:39 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonНадо бы автоматизировать получение формулы для любого числа измеренмй. допустим i это значения, а K кардинальности, тогда формула для n измерений Код: plaintext ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 08:51 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
ИМХО тут другая проблема просматривается. Максимальное значение это произведение всех кардинальностей K 0 *...*K n , оно легко может выйти за пределы имеющихся целочисленных типов и тогда расчет станет достаточно ресурсоемким. Во-вторых хэши в контейнерах обычно имеют размерность size_t, т.е. 32 и 64 бита для x32 и x64 соответственно, т.е. подмена хэша усложняется. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 09:05 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Давай пока не будем думать о разрядности. Нужно просто собрать макет и хотя-бы убедится что он - работает - дает приемлемое время отклика (не более секунды к примеру) - занимает разумный объем памяти(не более гигабайт а) Проблему числовой разрядности решим через arbitrary-precision арифметику. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 11:11 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonДавай пока не будем думать о разрядности. Нужно просто собрать макет и хотя-бы убедится что он - работает - дает приемлемое время отклика (не более секунды к примеру) - занимает разумный объем памяти(не более гигабайт а) Проблему числовой разрядности решим через arbitrary-precision арифметику. Схематично так будет: Инициализация: по каждому полю делаем приведение к виду 0 ... K-1, например для OrderId Код: sql 1. 2. В рабочем состоянии индекс определяем по OrderId, т.е. Код: sql 1. 2. Для наполняемых счетчиками можно придумать алгоритм убирающий пропуски. В общем в итоге каждый параметр должен быть приведен к индексу в диапазоне 0 ... K-1, где K - кардинальность. Отдельно выносим функцию Код: sql 1. 2. 3. Затем заполняем таблицу Код: sql 1. В рабочем состоянии проверка - это получить *_idx каждого поля, затем проверить Код: sql 1. Сколько потребуется памяти можешь сам прикинуть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 12:49 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TИнициализация: по каждому полю делаем приведение к виду 0 ... K-1, например для OrderId [src sql] OrderId["10248"] = 0 OrderId["10249"] = 1 .... Да я ОК со всеми твоими тезисами. Только добавь плиз всместо int64 какой нить тип из Boost.Multiprecision. По поводу разрядной сетки. Когда будешь генерить справочники - добавь плиз счетчики для каждой полоски гистограммы. Надо их отсортировать по частоте. Поинт вот в чем. Самые частые популярные константы в колонке - надо закодить коротким целым числом. 0,1,2,3.... А самые редкие пойдут в .... 621882,621883. Это не Хаффман но что-то близкое. Если будем хранить на диске в тесте или в Json - это даст экономию. Экономия будет после использования формулы total_idx(..) И в памяти тоже будет экономия если заюзаем BCD, String, или один из типов буста. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 18:57 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonТолько добавь плиз всместо int64 какой нить тип из Boost.Multiprecision. а как же maytonДавай пока не будем думать о разрядности Забудь и забей на страшное слово "буст". Это проблема сишников, не надо ее на других проецировать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 21:00 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonСамые частые популярные константы в колонке - надо закодить коротким целым числом. 0,1,2,3.... Похоже ты не понял о чем речь, перечитай что я писал. Не поймешь - переспроси. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 21:04 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonДавай пока не будем думать о разрядности Забудь и забей на страшное слово "буст". Это проблема сишников, не надо ее на других проецировать. Как будет угодно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.06.2018, 22:20 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonСамые частые популярные константы в колонке - надо закодить коротким целым числом. 0,1,2,3.... Все надо надо закодить "коротким целым числом", иначе просто не заработает. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.06.2018, 08:28 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Ты ввел искусственное ограничение. И говоришь что надо делать так. Мне этот ход непонятен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.06.2018, 09:39 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonТы ввел искусственное ограничение. И говоришь что надо делать так. Мне этот ход непонятен. Мы же вроде говорили о кэшировании неизменяемых (малоизменяемых) данных. В этом случае ограничение кардинальности уместно. Можно небольшой запас добавить, т.е. оставить место на добавление нескольких значений в каждое измерение. Если не ограничивать, то уйдем в сторону бесконечности, т.е. классические решения будут эффективнее как по производительности, так и по памяти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.06.2018, 09:52 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Ещё раз проглядел топик, и кажется "уловил" предмет. По крайней мере у меня сложилась какая-то модель, из которой предложения от Dima T мне видны как ясные и понятные с точки зрения манеры реализации в виде конструкции, положенной в реляционную БД. (Мне так смотреть привычней). При условии что а) "измерениями" являются фиксированный набор категориальных переменных, каждая из которых обладает "обозримым" набором допустимых значений. Так, чтобы при сплошной нумерации всех подряд значений из всех категорий максимальный номер получался "обозримым". Ну, пусть, до 6 десятичных разрядов. Т.е., при создании такой структуры пункт 1) - зафиксировав последовательность входящих в "куб" измерений, последовательно перенумеровать все допустимые значения всех используемых в нем категорий, построив сплошной числовой уникальный идентификатор значений. При 10 измерениях, пусть со 100 значениями в каждом из них, получим номера от 1 до 1000 Это, например, даст возможность формировать строковый ключ фиксированной длины, позиционно кодирующий любую возможную комбинацию. Это простая детерминированная функция, в примере 10*100 возвращающая строку в 40 символов, являющаяся собственным свойством кубирующей комбинации переменных. б) в части кодирования "малыми числами" комбинации значений набора переменных, имхо, нужно отказаться от использования слова "функция" в смысле её детерминированности. У того, кто занимается кодированием фактического заполнения всей конструкции есть право идти не от навсегда повешенных по точкам вселенной чисел, а от конкретного состава текущего заполнения всей структуры. Просто выдавая следующий номер по мере необходимости. Это кодировка привязана к конкретно-историческому ходу процесса заполнения всей структуры. Вошедшему в кубирующий автобус дается билет. Кто в автобус не вошел - тому билет не нужен. Номер на отрывном талоне билета не напечатан в типографии, а рисуется вошедшему кондуктором прямо на талоне. Если вошедший обладает тем же цветом глаз, волос и формой подбородка, как и один из уже сидящих, номер на талоне такого берется из журнала зарегистрированных номеров присутствующих в салоне комбинаций признаков. А если еще не было вошедшей комбинации значений метрирующих категориальных переменных, то выделяется просто следующий последовательный номер. Это процесс последовательной нумерации фактически присутствующих в кубическом автобусе признаков малыми числами, путем ведения журнала фактически поступивших признаков. Как теперь искать рыжих и одновременно бородатых? В простом случае, когда всех выданных номеров "не очень много", достаточно просмотреть записанные результаты регистрации поступивших признаков у которых в позициях с 5й по 8ю стоит код '0075' - номер рыжего цвета в сплошной идентификации значений, а в позициях с 14 по 17-ю '0153' - номер признака наличия бороды в той же нумерации, выписать на листок выданные номера комбинаций, в которых он встречается и крикнуть в салон - Поднять руки всем, у кого талоны с номерами 7 и 31. При увеличении интенсивности пассажирооборота и удлинении маршрута, возможно умнее параллельно поддерживать множества смежности поступивших признаков. Может быть даже с весами присутствия, равными количеству зафиксированных экземпляров смежного признака. Ластик тут будет полезен, чтобы стирать из множества смежности полностью выбывшие из салона признаки, веса присутствия которых в списке смежности опустились до нуля. Но работа эта дополнительная и степень её целесообразности требует специального суждения, исходя из обстановки на маршруте. Все это основано на том, что в салоне число комбинаций присутствующих признаков, длиной от нуля до максимальной размерности кубирующего автобуса, всегда много-много меньше всех возможных абстрактно комбинаций. Стирать ли в процессе рейса из журнала нумерации комбинаций строку, резервирующую ей номер при полном выбытии комбинации - дело договоренности. Я, вероятно, надеялся бы на повторное использование до конца рейса. Но на конечной станции, по опустошении структуры салона, очистка всех журналов и заявление о том, что рейс в обратную сторону - новый - вполне имеет право на существование. как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.06.2018, 02:40 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonТы ввел искусственное ограничение. И говоришь что надо делать так. Мне этот ход непонятен. Мы же вроде говорили о кэшировании неизменяемых (малоизменяемых) данных. В этом случае ограничение кардинальности уместно. Можно небольшой запас добавить, т.е. оставить место на добавление нескольких значений в каждое измерение. Если не ограничивать, то уйдем в сторону бесконечности, т.е. классические решения будут эффективнее как по производительности, так и по памяти. Давай немножко шаг назад. Когда мы я говорил об ограничениях - работает - дает приемлемое время отклика (не более секунды к примеру) - занимает разумный объем памяти(не более гигабайта) я это постулировал как следующую цель. Я agree с тобой в части экономии ресурсов памяти и оптимизации. Но зачем мне себя ограничивать в целочисленной арифметике сейчас? Мне нужно экспериментировать с хранением в табличке произведений индексов справочников. Причем произведение будет не индексом а значеним (value). Вместо хранения 1,1,1,1,1 в качестве первого кортежа я буду хранить 1*(k1 * k2 .... ) + ... + 1 = X. И жонглируя гистограммой я пытаюсь с этого получить какие-то экономические выгоды в размере произведения. Мой мотив рационален? Рационален. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.06.2018, 23:00 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
maytonНо зачем мне себя ограничивать в целочисленной арифметике сейчас? С большими числами можно проще поступить: округлять кардинальности до ближайшей большей степени двойки. В таком виде мы получаем битовую структуру, где под каждое измерение будет целое число бит. Работать с такой структурой просто, быстро и никаких ограничений на ее размер. ИМХО эта избыточность не критична если общая кардинальность (произведение всех кардинальностей) выходит за разумные пределы, т.е. для биткарты много и как хэш нельзя использовать. В общем случае получается сжатие исходных данных и не более того, т.е. экономия памяти за счет того что сжатая форма занимает меньше места. Дальше используем сжатую форму стандартными способами. Например в хэш-таблице. maytonМне нужно экспериментировать с хранением в табличке произведений индексов справочников. Причем произведение будет не индексом а значеним (value). У тебя как-то перепутаны индекс и значение. Индекс это расположение в кубе, составной ключ в терминологии РСУБД, он никуда не девается, а value оно и сейчас есть, только выше у нас оно однобитное, но ничто не мешает сделать его N-бит, т.е. любого размера. maytonВместо хранения 1,1,1,1,1 в качестве первого кортежа я буду хранить 1*(k1 * k2 .... ) + ... + 1 = X. И жонглируя гистограммой я пытаюсь с этого получить какие-то экономические выгоды в размере произведения. Мой мотив рационален? Рационален. Если в моей формуле 21468543 скобки раскрыть то получим твою. Код: plaintext ИМХО вроде всё понятно: то что чаще повторяется надо выносить влево, т.е. в i 0 . Или по другому: чем меньше кардинальность - тем левее. Но это полезно если потом в биткарте использовать или вместо хэша в хэш-таблице, в этом случае есть смысл "скучковывания" индексов. Если общая кардинальность велика (см. выше) то пользы от этого ноль. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.06.2018, 08:27 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonНо зачем мне себя ограничивать в целочисленной арифметике сейчас? С большими числами можно проще поступить: округлять кардинальности до ближайшей большей степени двойки. В таком виде мы получаем битовую структуру, где под каждое измерение будет целое число бит. Работать с такой структурой просто, быстро и никаких ограничений на ее размер. Я вот думаю что может быть я был не прав насчет произведения ключей. Когда я стал имплементировать - оказалось что на этапе загрузки данных я еще не знаю кардинальностей пока данные загружаются. Тоесть алгоритм получается двух-фазный. 1) Анализ кардинальностей и генерация справочников. 2) Собственно наполнение хеш-таблички (или биткарты или куба не имеет значения) произведениями кодов. Вобщем если так делать то реляционная работа будет выглядеть как процесс ETL. А это усложняет использование. Я планировал так (это несуществующий псевдо язык просто чтоб показать концепцию): Код: sql 1. 2. 3. 4. 5. Здесь на 3-й строке куб должен быть уже инициализирован чтобы можно было сделать фактологический запрос. А я не могу делать расчет произведений пока не будет загружен весь amount 600 тысяч строк. В противном случае формула будет неверна т.к. не все кардинальности еще расчитаны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.06.2018, 15:21 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Dima TУ тебя как-то перепутаны индекс и значение. Индекс это расположение в кубе, составной ключ в терминологии РСУБД, он никуда не девается, а value оно и сейчас есть, только выше у нас оно однобитное, но ничто не мешает сделать его N-бит, т.е. любого размера. Да. Я уже в коде раза 3 перепутал все. Нужен agreement по терминологии. Поэтому. В данном топике Cube - многомерная структура данных которая является аналогом таблицы в БД. Поддерживает базовые операции DML такие как insert/update/delete. Выборка также поддерживается хотя сильно зависит от cube organization. Cube хрантся в оперативной памяти приложения. Cube organization(СО) - внутренняя архитектура куба. Представляет собой совокупность алгоритмов и структур данных нацеленных на реализацию базовых операций. В реализации нет ограничений кроме разумных рамок использования оперативной памяти, heap, стека. R/O data - данные из БД которые по своему смыслу - read/only в рамках решаемой прикладной задачи. Например - справочники стран. Языков. Почтовых кодов. Адресов. Гео-объектов. Классификаторы. (Данная трактовка достаточно широкая. В частности системы справочников работающие с суточным жизненным циклом могут также быть кандидатом в R/O data даже если они обновляются если их обновление технологически не нарушает бизнес-логики и укладывается в парадигму топика). Свойство R/O data является важной и неотъемлемой части постановки. Автор топика считает что отклонение от этого пункта - в корне меняет задачу вплоть до создания отдельных топиков или форков от темы. Primary goal - основная цель (топика). Исследовать возможности кеширования баз данных на стороне клиента для R/O data. Cube population process(CPP) - важная часть процесса. Предполагается что основной объем вычислений данной задачи будет исполнен в фазе наполнения таблицы source data. Source data size (SDS) - фактический объем данных (в байтах или символах) которые необходимо закешировать. (Здесь я рекомендую просто брать физический размер CSV-файла т.к. все прочие метрики хранения эти данных в БД могут быть спорными. Сегмент file-БД обычно разрежённый и Inmemory DBMS тоже хранят данные далеко не компактно). Destination data size (DDS) - объем оперативной памяти который необходимо потратить на наполнение Cube. Cube positive effect (CPE) - соотношение (SDS - DDS) / SDS. Грубо говоря если мы получили 1Мб куба на исходных 32М то (32 - 1) / 32 = 0.95 = 96%. Разумеется куб ушедший в отрицательный сегмент % CPE - нам не интересен. Он - не лучше чем БД. Other Cube time optons (CTO) - прочие свойства куба которые мы сформулируем чуть позже. Сюда в частности войдут характеристики отклика поисковых операций и стоимости cube population. Secondary goals - совокупность вторичных целей топика. Предполагается что помимо создания куба мы (участники) можем отклонятся от задачи и исследовать пользу от применения экзотических (стохастичных) структур данных для достижения основной цели. Cardinality - в контексте поля таблички БД или Cube кардинальность несет тот-же смысл что и в БД. Мощность уникального множества значений (values) которое хранит поле. Dictionary (Dict) - справочник уникальных значений поля. Число значений в справочнике == кардинальность. Языки программирования Cube - любые ЯП доступные пользователям sql.ru. (разумеется ЯП должен быть практичен для решения данной задачи. Брать к примеру javascript не имеет особого смысла) Прочие поинты. 1) В фазе CPP когда куб еще строится у разработчика есть большой арсенал возможностей по оптимизации размера. Биткарты, деревья, графы, конечные автоматы, хеш-таблички списки и прочее. Задача архивации - не ставится. Структура данных куба обязана сохранять приемлемые свойства отклика для поиска произвольного факта. 2) Итерируемость и поддержка полноценного интерфейса выборки. SELECT * FROM. Iterator. Iterable. e.t.c. 3) Анализ свойств куба. В процессе генерации СО можно делать глубокий анализ данных. Искать явные зависимости между полей. Детектировать булевы признаки. Низко-кардинальные. Интервальные признаки (диапазон дат). 4) Связи с OLAP. В констатирующей части можно заявить что технология ОЛАП не имеет никакого отношения к данному топику. Терминология в части кубов - случайное совпадение. Olap в оригинальной постановке хранит результат аналитики а данная задача оперирует исходными данными. Плюсаните если ОК. Или добавте ваши пожелания по улучшению. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.06.2018, 16:51 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Cube index (CI) - число. В декартовой форме организации куба CI уникально идентифицирует одну точку (ячейку) где лежит значение true/false. Существует формула перехода от измерений куба к CI и обратно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.06.2018, 17:11 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Source Table (ST) - исходные данные которые мы будем обрабатывать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.06.2018, 18:31 |
|
||
|
Вторничный куб. Концепция.
|
|||
|---|---|---|---|
|
#18+
Я в отпуске на неделю. Дети убили походный ноут, пишу с планшета, писать неудобно. Отвечу как вернусь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.06.2018, 21:12 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39656142&tid=1340101]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
172ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
| others: | 13ms |
| total: | 279ms |

| 0 / 0 |
