Вторничный куб. Концепция.

Привет друзья.

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

1. Создание (Пишу на псевдо-языке который может быть C#/D/Rust/Java).

Cube cube = new MCube(2580,2580,2580).withStaticAllocation();

2. Наполнение фактами. В данном случае предикат isMutuallySimple утверждает что тройка чисел - взаимно простые.

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. Проверка куба.

cube.check(7,9,16) == true

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

Фак.

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

Цифры. Для куба с расходом памяти в 2Gbyte. (~17 179 869 184 boolean элемента)

Size Dimensions 131072 2 2580 3 362 4

Переводя на наш язык. Хранение таблицы фактов с тремя колонками с кардинальностью
порядка 2 с половиной тысячи потребует в самом худшем случае 2Г оперативы.

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

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

Еще поинты.

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

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

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

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

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

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

Пишите каменты. Имплементации пока нет.

Я так понимаю тоже самое можно получить создав тип

class my_type_t {
public:
  int i, j, k;
}

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

Или я что-то недопонимаю?

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

ИМНО ты биткарту N-мерную изобрел, тут достаточно индекс из N-мерной к одномерной привести и пользоваться как обычно.

Например по данным твоего примера:

   if (isMutuallySimple(i,j,k)) cube.set(i,j,k);

равносильно

if (isMutuallySimple(i,j,k)) bitmap[i * 2580 * 2580 + j * 2580 + k] = true;

Да. Верно. Эта задача решается хеш-табличкой но в моем варианте схема хранения данных расходует 1 bit на каждую запись.

Вообще. Это не куб. В общем случае это многмерный параллелепипед.

Dima T, я не изобрел многомерный массив. Я думаю о том как использовать всем известную структуру для храненя строковых ключей или ключей типа enum.

mayton
Dima T, я не изобрел многомерный массив.

ИМХО именно его изобрел. Точнее многомерную биткарту изобрел, а она по сути обычный массив, только элемент 1 бит.
Т.е. в итоге получение индекса нужного элемента сведется к его расчету по тем же правилам, как и в многомерных массивах.

mayton
Я думаю о том как использовать всем известную структуру для храненя строковых ключей или ключей типа enum.

enum отлично вписывается в твою систему. Их надо просто пронумеровать 0 ... N-1
Похуже впишутся ID сгенеренные счетчиками, но можно пооптимизировать.

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

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

Как понимаю в итоге твоя задача сводится к сравнению характеристик хэш-таблицы и биткарты. Или к изобретанию еще какого-то хранилища с похожими свойствами. Если так, то тут нет универсального решения, надо исходить из конкретного случая, т.е. нужна статистика использования конкретных данных.

Я не буду настаивать на универсализме. Его здесь нет. Я попробую вспомнить тот юзкейс с которого начал думать о биткарте.

Вещь может быть нужная. Если не тупо маппинг "многомерный массив" - "одномерный", а какие нибудь структуры предназначенные для работы с разряженными данными a la компрессия на лету.

Если посмотреть на табличку mayton'а, становится понятным, что при кол-ве исмерений >= 4, простейший куб становится ну уж очень маленьким, для любых осмысленных бизнес задач.

Лучше исходить из предположения что не все измерения одинаково большие. Поле gender будет иметь 2 значения male, female и это даст в хранилище просто удвоение биткарты. Но никак не умножение на 2000 как я нарисовал в учебном примере.

Мне нужен был в свое время некое подобие Subj. Но не биткарта. а куб целых чисел.

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

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

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

Но если бы была возможность куда-то сложить хотя бы биткарту, наверное было бы полезно. Но размерность у таких кубов в реальных бизнес задачах должна быть "дикая" (в моем случае, наверное, >10 измерений).