ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный куб. Концепция.
25 сообщений из 100, страница 1 из 4
  1  все
Вторничный куб. Концепция.
    #39652081
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет друзья.

Есть тема над которой я думаю последние несколько недель.
Я постараюсь не быть многословным (это мой косяк) и кидать snippets вместо множества букв.

1. Создание (Пишу на псевдо-языке который может быть C#/D/Rust/Java).
Код: sql
1.
Cube cube = new MCube(2580,2580,2580).withStaticAllocation();



2. Наполнение фактами . В данном случае предикат isMutuallySimple утверждает что тройка чисел - взаимно простые.
Код: sql
1.
2.
for(i in 0..2579) for (j in 0..2579) for (k in 0..2579) 
   if (isMutuallySimple(i,j,k)) cube.set(i,j,k);



3. Проверка куба .
Код: sql
1.
cube.check(7,9,16) == true


Дает истину т.к. 7 и 9 и 16 взаимно простые. Это просто пример. В предикате
может стоять ваша бизнес-логика. Проверка физ-лица. Предприятия. Тех-средства.

Фак.

Задлянафига. . Ответ - я искал аналог структурам данных типа HashTable. Возможный поинт - экономия.

Цифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента)
SizeDimensions1310722258033624
Переводя на наш язык. Хранение таблицы фактов с тремя колонками с кардинальностью
порядка 2 с половиной тысячи потребует в самом худшем случае 2Г оперативы.

Дальше - думайте. Прикидывайте.

Где применять. Хм... изначально я думал о кешах Хибернейт. Чуть позже задача стала более общая. Я стал думать о пользе кубиков.

Еще поинты.
Цифры - это не уныло. Нужен справочник строки - цифры.

Размерность куба должна быть гибкой. Ну... по крайней мере он не должен
падать при доступе к элементу с индексом 2581 в нашем кейсе. Я думаю над
этим.

Итератор. Собственно поддержать можно. Но будут накладные. Подумайте.

Что не ложится в куб. Вещественные величины. Даты. Время. Деньги.

Что круто ложится в куб. Перечисления. Справочники.

Ну вобщем все.

Пишите каменты. Имплементации пока нет.
...
Рейтинг: 0 / 0
29.05.2018, 22:01
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652209
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я так понимаю тоже самое можно получить создав тип
Код: sql
1.
2.
3.
4.
class my_type_t {
public:
  int i, j, k;
}


Прописать в нем необходимые операторы, а дальше использовать стандартные контейнеры. Например HashTable<my_type_t> или HashSet<my_type_t>

Или я что-то недопонимаю?
...
Рейтинг: 0 / 0
30.05.2018, 08:44
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652214
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЦифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента)
SizeDimensions1310722258033624
Переводя на наш язык. Хранение таблицы фактов с тремя колонками с кардинальностью
порядка 2 с половиной тысячи потребует в самом худшем случае 2Г оперативы.
ИМНО ты биткарту N-мерную изобрел, тут достаточно индекс из N-мерной к одномерной привести и пользоваться как обычно.

Например по данным твоего примера:
Код: plaintext
1.
   if (isMutuallySimple(i,j,k)) cube.set(i,j,k);


равносильно
Код: plaintext
1.
if (isMutuallySimple(i,j,k)) bitmap[i * 2580 * 2580 + j * 2580 + k] = true;
...
Рейтинг: 0 / 0
30.05.2018, 08:49
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652218
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Верно. Эта задача решается хеш-табличкой но в моем варианте схема хранения данных расходует 1 bit на каждую запись.

Вообще. Это не куб. В общем случае это многмерный параллелепипед.
...
Рейтинг: 0 / 0
30.05.2018, 08:53
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652224
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, я не изобрел многомерный массив. Я думаю о том как использовать всем известную структуру для храненя строковых ключей или ключей типа enum.
...
Рейтинг: 0 / 0
30.05.2018, 08:58
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652245
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima T, я не изобрел многомерный массив.
ИМХО именно его изобрел. Точнее многомерную биткарту изобрел, а она по сути обычный массив, только элемент 1 бит.
Т.е. в итоге получение индекса нужного элемента сведется к его расчету по тем же правилам, как и в многомерных массивах.
maytonЯ думаю о том как использовать всем известную структуру для храненя строковых ключей или ключей типа enum.
enum отлично вписывается в твою систему. Их надо просто пронумеровать 0 ... N-1
Похуже впишутся ID сгенеренные счетчиками, но можно пооптимизировать.

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

Я не понимаю куда можно применить изобретение твое? В терминах РСУБД ты изобрел проверку составного первичного ключа. Есть/нет.

Как понимаю в итоге твоя задача сводится к сравнению характеристик хэш-таблицы и биткарты. Или к изобретанию еще какого-то хранилища с похожими свойствами. Если так, то тут нет универсального решения, надо исходить из конкретного случая, т.е. нужна статистика использования конкретных данных.
...
Рейтинг: 0 / 0
30.05.2018, 09:33
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652265
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не буду настаивать на универсализме. Его здесь нет. Я попробую вспомнить тот юзкейс с которого начал думать о биткарте.
...
Рейтинг: 0 / 0
30.05.2018, 09:53
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652319
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Вещь может быть нужная. Если не тупо маппинг "многомерный массив" - "одномерный", а какие нибудь структуры предназначенные для работы с разряженными данными a la компрессия на лету.

Если посмотреть на табличку mayton'а, становится понятным, что при кол-ве исмерений >= 4, простейший куб становится ну уж очень маленьким, для любых осмысленных бизнес задач.
...
Рейтинг: 0 / 0
30.05.2018, 11:10
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652444
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Лучше исходить из предположения что не все измерения одинаково большие. Поле gender будет иметь 2 значения male, female и это даст в хранилище просто удвоение биткарты. Но никак не умножение на 2000 как я нарисовал в учебном примере.
...
Рейтинг: 0 / 0
30.05.2018, 13:11
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652457
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Мне нужен был в свое время некое подобие Subj. Но не биткарта. а куб целых чисел.

Есть перелет на самолете. Есть набор его характеристик. Нужно из сотен миллионов вариантов перелета выбрать "оптимальный"

Т.е. своего рода куб, где измерения собственно характеристики (цена билета, время полета, кол-во пересадок, время пересадок, дневные/ночные пересадки), значение - получевшийся некая оценка "оптимальности" данного варианта.

Другое дело, что мне хранение всех вариантов было не нужно. Просто при проходе расчетов хранил "100 лучших", все, что заведомо хуже этих "лучших", сразу же отбрасывал. Если менялись критерии оценки, запускал поиск на графе повторно.

Но если бы была возможность куда-то сложить хотя бы биткарту, наверное было бы полезно. Но размерность у таких кубов в реальных бизнес задачах должна быть "дикая" (в моем случае, наверное, >10 измерений).
...
Рейтинг: 0 / 0
30.05.2018, 13:33
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652637
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsev,

Хм. Интересно. А насколько плотно ваш куб заполнялся внутри? И был-ли какой-то ранг его осей? Ну тесть. Мой вариант куба предполагает полное отсутствие критериев близости двух фактов.
...
Рейтинг: 0 / 0
30.05.2018, 15:58
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652663
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonLeonid Kudryavtsev,

Хм. Интересно. А насколько плотно ваш куб заполнялся внутри? И был-ли какой-то ранг его осей? Ну тесть. Мой вариант куба предполагает полное отсутствие критериев близости двух фактов.

Куба в памяти как такового не было (хранил только 100 или даже меньше значений), куб был "логический" во время вычислений.

Ранг и критерии были, в этом и была главная идея. Ранг (вес) отдельных характеристик менялись в зависимости от выбора пользователя/интерфейса (в прод не ушло, т.ч. дизайн был так себе). В том числе, вес можно было сделать "0" или "очень много", тогда система понимала, что все варианты с этой характеристикой нужно или отбросить как совсем неподходящие или, наоборот, пытаться искать варианты с такой характеристикой.

Большинство характеристик были представлены как дискретные значения по определенному измерению в кубе. Например цена - просто с шагом в 10$ (шаг динамически менялся, т.е. реализация была не настолько "топорно", но идея ровно такая), время - с шагом в 15 мин., кол-во пересадок от 0 до 7 (были найдены такие маршруты, где меньше чем за 8 рейсов "кусочков" не долететь!, конкуренты такие маршруты вообще находить не умели/ют).

Ряд характеристик передавал как список. Например аэропорты, где осуществляется пересадка. Т.ч. даже запросы типа "не хочу лететь через Лондон", выполнялись по той же схеме.

Собственно по итогам, критерий близости/дальности и получался. Собственно "близкие" варианты "схлопывались" (т.к. размерность была дискретной, близкие варианты просто попадали в одно "ячейку" и оставался наилучший), самые "левые/мусорные" - отбрасывались, остаток ранджировался.
...
Рейтинг: 0 / 0
30.05.2018, 16:17
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652673
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonплотно ваш куб заполнялся внутри
Совершенно не плотно.
...
Рейтинг: 0 / 0
30.05.2018, 16:27
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652746
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsev,

Мощно. Это похоже на транспортную задачу. Но не в плоскости а в объеме.
...
Рейтинг: 0 / 0
30.05.2018, 17:56
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652772
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
maytonLeonid Kudryavtsev,

Мощно. Это похоже на транспортную задачу. Но не в плоскости а в объеме.

Ну в общем задача и была "транспортой"

Найти маршрут из A в B

Проблема была в критериях. Т.к. изначально задача ставилась "самое дешевое", но по ходу работы выяснилось, что "кругосветный перелет с 5 пересадками в течение недели за 15 $ " - это круто, но для большинства пользователей, вряд ли нужная вещь )))

И критериев оценки стало очень много
...
Рейтинг: 0 / 0
30.05.2018, 18:36
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652797
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
Leonid Kudryavtsev,

Это простая задача
...
Рейтинг: 0 / 0
30.05.2018, 19:29
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652810
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Она не простая в целевой функции. Быстро и дешево. Это уже набор взаимоисключающих критериев. И нужна новая целевая функция.
...
Рейтинг: 0 / 0
30.05.2018, 20:04
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652848
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
mayton,

быстро потом дешево (самый дешевый из самых быстрых)
дешево потом быстро (самый быстрый из самых дешевых)
скорость * w1 + стоимость * w2 (тут надо очень хорошо подобрать w1;w2)
у меня еще и качество добавлено в расписании (семантически : выбраны лучшие - оборудование, материал, персонал из возможных)
...
Рейтинг: 0 / 0
30.05.2018, 21:47
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39652863
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В продолжение темы кубика. Как вообще возникла постановка.

Кейс №1

Лет несколько назад я оптимизировал приложение. Крупный банк. Веб. Система управления HR.
Там была базейка. Схема безопасность. Связка таблиц многие-ко-многим. Через промежуточную.

Вобщем

Код: sql
1.
Entitlement <-> Entitlement2UiElement <-> UiElelement



Сущность Entitilement это что-то вроде роли или привилегии в системе. Или группы ролей хрен их знает.
Они связаны многие-ко-многим. Далее по теме меня могут спросить - асху яли... почему ты не сделал группы.
Я отвечу что это и есть группы. Просто все сложно.

Честь ентайтлментов была в работе. Часть сдохла. Часть дублировала другую честь. И были UI элементы которые
не имели вообще возможности отображаться. Не суть. Вобщем. Это матрица. Технически Хибернейт решал эту задачу.
Был Дао который извлекает пользователя потом его ентайтлмент и потом его графические элементы. Но поскольку
я - перфекционист то я думал о путях оптимизации. Биткарта - как частный случай. По сути Дао должен отвечать
на вопрос. Можно ли отобразить данный ID UI элемента для данного энтайтлмента данного пользователя.

Я не успел имплементировать матричное решение. Проект завершился. Но убежден что кеш на базе гипер-куба
был-бы удачен. Условия - были благоприятны. Политики ентайлтлемнтов менялись редко. Раз в сутки система перегружалась.
Тоесть даже без управления обновлениями кеш был-бы эффективен.

Кейс №2

Таблица с булевыми атрибутами. Следующая постановка - не реальна а скорее переосмысление.
Есть класс задач где индексы БД - неэффективны. Например физ-лица и некоторые атрибуты.

IDNameGenderIsClientCreditWorthyAdultDrawnToCriminalDrivingACarWasAbroadSocialClass0maytonmalennnnnnExtra1DimamaleyyyyynClassic2LeonidmaleynynynExtra
Имеет место 9-мерный куб с неравномерной кардинальностью. В 9-мерном пространстве - это
вытянутый "брусок" где наибольшая размерность соответствует ID пользователя. Далее - класс
соц-страхования (может быть 10-20 записей в справочнике хрен знает сколько но явно меньше
чем клиентов). Остальные атрибуты - двумерные. Несмотря на кажущуюся невообразимость
и сложность представления - биткарта хавает. И хранит весь объем информации достаточно
легко. Как я уже говорил данная структура данных плохо поддерживает итератор да нам и не надо.
Извлечение факта. Тоесть проверка к примеру того что Мэйтон не был судим и не был за границей
занимает - микросекунды и ложится умеренный объем ресурсов.

Технически БД решает эту задачу путем построение специальный bitmap-индексов.
Но (мы то знаем) что они эффективны только R/O и в совокупности с выборкой по другим
признакам. Вобщем БД - не рулит. Б-деревья плохо работают с выборкой низкой кардинальности.
Здесь можно долго теоретизировать но как факт - возьмите большую (овер миллиард записей)
таблицу и попробуйте проиндексировать совокупность признаков. Забегая вперед я скажу
что знаю еще один workaround типа фасетного поиска - но тема не об этом. Тема - кубики
и низкая кардинальность. Мы с вами можем разве-что разойтись в количественых оценках.
Кому 10 - низкая. А кому и 100 тысяч. Вобщем. Думайте.

Я прошу прощения за некую натянутость и синтетичность постановки но я далее ожидаю
предложений по использованию именно от вас. От мемберов форума.
...
Рейтинг: 0 / 0
30.05.2018, 22:14
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653073
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Как понимаю в обоих случаях задача сводится к проверке некоторых свойств конкретного объекта, причем набор свойств у каждого объекта одинаков.

Можно вместо многие-ко-многим свести к одной таблице: {id, name, attr1, attr2, attr3 ...}, собственно второй пример так показан. По-сути это обычная денормализация.

В целях экономии памяти можно пойти дальше, заменить {attr1, attr2, attr3 ...} на битовое представление, т.е. биткарту + описание структуры, например attr1 - 0й бит, attr2 - 1й и т.д. Для атрибутов не вмещающихся в один бит можно выделять несколько.

В итоге получаем что надо кэшировать {id, bitmap}, т.е. для организации кэша достаточно ассоциативного массива.
...
Рейтинг: 0 / 0
31.05.2018, 10:25
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653076
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В общем я к тому что надо кэш хранить в виде: один объект - одна биткарта с его свойствами.
...
Рейтинг: 0 / 0
31.05.2018, 10:33
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653083
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonТехнически БД решает эту задачу путем построение специальный bitmap-индексов.
Но (мы то знаем) что они эффективны только R/O и в совокупности с выборкой по другим
признакам. Вобщем БД - не рулит. Б-деревья плохо работают с выборкой низкой кардинальности.
Здесь можно долго теоретизировать но как факт - возьмите большую (овер миллиард записей)
таблицу и попробуйте проиндексировать совокупность признаков. Забегая вперед я скажу
что знаю еще один workaround типа фасетного поиска - но тема не об этом. Тема - кубики
и низкая кардинальность. Мы с вами можем разве-что разойтись в количественых оценках.
Кому 10 - низкая. А кому и 100 тысяч. Вобщем. Думайте.
Как понимаю тут ты рассуждаешь над обратной задачей: найти объект(ы) по свойствам, если так то был такой топик
...
Рейтинг: 0 / 0
31.05.2018, 10:41
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653133
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я бы не хотел тащить сюда фасетный поиск. Его постановка другая. Мы находим множество товаров обладающих сетом свойств.

А куб просто проверяет что существует 1 такой бизнес факт. И все.
...
Рейтинг: 0 / 0
31.05.2018, 11:50
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653270
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Считать всю ночь в СУБД, а утром задавать вопросы и получать ответы. Если подсчитывать на лету, в БД может быть постоянно актуальный кубешник
...
Рейтинг: 0 / 0
31.05.2018, 13:54
| Ответить | Цитировать | Написать  
Вторничный куб. Концепция.
    #39653290
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я добавлю чего куб не любит.

1. Изменения размера осей. Тоесть реорганизация куба это в общем случае - пересоздание нового. Поэтому лучше заложить +20 длины осей про запас.

2. Редкое заполнение. В этом случае его польза неочевидна и программисту лучше взять hashtable.

3. Поиск по неполному набору атрибутов. Вместо поиска точки мы будем искать множество фактов на гипер-прямой или гиперплоскости и т д. O(1) превращается в линейный или полиномиальный.
...
Рейтинг: 0 / 0
31.05.2018, 14:16
| Ответить | Цитировать | Написать  
25 сообщений из 100, страница 1 из 4
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный куб. Концепция.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]