Как сохранить матрицу в БД?
Как правильно сохранить в postgresql экземпляр вот такого класса:
@Table(name="matrix") class Matrix < @Id @GeneratedValue private Long id; private int[][] data; // getters, setters etc. >Каждый экземпляр этого класса может содержать матрицу различных размеров, число строк и столбцов варьируются.
Для записи поля data, как бинарного блоба, какие аннотации и типы данных в БД использовать? Буду рад любым примерам.
pol01 ☆
13.02.19 20:06:03 MSK
anonymous
( 13.02.19 20:07:37 MSK )
Ответ на: комментарий от anonymous 13.02.19 20:07:37 MSK
Это я уже всё прочитал. Вопрос, как в java чтение и запись организовать.
pol01 ☆
( 13.02.19 20:08:58 MSK ) автор топика
anonymous
( 13.02.19 20:12:03 MSK )
Ответ на: комментарий от anonymous 13.02.19 20:12:03 MSK
Пример @Lob и сохранения int[][] можешь привести?
pol01 ☆
( 13.02.19 20:19:19 MSK ) автор топика
Ответ на: комментарий от pol01 13.02.19 20:19:19 MSK
Гуглится по site:github.com @Lob @Entity @Id «[][]»
Aber ★★★★★
( 13.02.19 20:39:32 MSK )
Нафига тебе [][] вообще? Матрица это простой массив int[] если не используется компрессия колонок/строк/etc
anonymous
( 13.02.19 21:51:33 MSK )
Ответ на: комментарий от Aber 13.02.19 20:39:32 MSK
pol01 ☆
( 13.02.19 22:03:30 MSK ) автор топика
Ответ на: комментарий от anonymous 13.02.19 21:51:33 MSK
А как можно свернуть и развернуть int[][] в int[] ?
pol01 ☆
( 13.02.19 22:04:27 MSK ) автор топика
Ответ на: комментарий от pol01 13.02.19 22:04:27 MSK
рядом хранить величину первой размерности, вычислять на лету вторую координату
bvn13 ★★★★★
( 13.02.19 22:07:36 MSK )
Я решал задачу хранения матницы в БД, но к сожалению у меня кода нету под рукой. Я делал все по аналогии с этой статьей https://vladmihalcea.com/how-to-map-java-and-sql-arrays-with-jpa-and-hibernate/ насколько я помню там достаточно заменить int[] на int[][] и все будет работать.
mythCreator
( 14.02.19 01:22:46 MSK )
Сериализуй в XML и храни в поле text
Legioner ★★★★★
( 14.02.19 01:34:29 MSK )
Ответ на: комментарий от Legioner 14.02.19 01:34:29 MSK
В текст согласен, но зачем такое порно с xml? Верно подсказывают — пусть просто числа в ряд, если матрица квадратная — так и подавно.
anonymous
( 14.02.19 10:44:44 MSK )
Постгрес поддерживает и одномерные, и двумерные массивы. Если массив двумерный, но элементы разного размера, можно хранить в json(b)
Выбрось недорм и аннотации, пиши на sql.
nikolnik ★★★
( 14.02.19 10:47:19 MSK )
Ответ на: комментарий от Legioner 14.02.19 01:34:29 MSK
А почему не сразу в xlsx и не хранить как бинарный блоб?
nikolnik ★★★
( 14.02.19 10:49:07 MSK )
Чтобы БД жизнь сахаром не казалась, храни каждый элемент отдельной записью. Если понадобятся разреженные матрицы, это может даже оказаться правильным решением, лол.
Алсо, у иклипслинка есть такая шляпа. Не помню, правда, из стандарта она или кастом.
Deleted
( 14.02.19 11:05:48 MSK )
Последнее исправление: Deleted 14.02.19 11:06:02 MSK (всего исправлений: 1)
Ответ на: комментарий от nikolnik 14.02.19 10:47:19 MSK
Я смотрел в сторону json(b). Как понял, там вся фишка, что можно внутри этого json искать будет. Мне этого не нужно.
pol01 ☆
( 14.02.19 11:13:52 MSK ) автор топика
Ответ на: комментарий от pol01 14.02.19 11:13:52 MSK
Фишка json(b) в том, что это json, по которому можно искать и строить индексы. Так же жсон позволяет хранить данные в произвольном порядке. Если ты в постгресе попытаешься в [][]ARRAY положить , , то оно тебе не разрешит, т.к. все массивы должны быть одинаковой длины, в случае с матрицами — это ок, в других случаях приходиться изощряться через жсон.
Форум пользователей MySQL
Насколько мне известно в Maria DB появился механизм для работы с графами (OQGRAPH).
А чем, к слову, Вам не нравится идея сохранения пар смежных вершин?
Зеленый свет для слабаков, долги отдают только трусы, тру гики работают только в консоли.
#3 23.07.2011 17:35:27
nikolajtesla Завсегдатай Зарегистрирован: 12.10.2010 Сообщений: 25
Re: Как хранить матрицу в БД
Про Maria DB — огромное спасибо.
На счет не нравится — это слишком сильно сказано. Я просто иду другие варианты для хранения и пытаюсь узнать в каких случаях они могут быть более эффективны.
Ведь принимая во внимание, что в для простого графа матрица смежности симметрична и состоит только из возможно есть смысл использовать для ее хранения методы для разряженных матриц
#4 23.07.2011 17:40:25
deadka Администратор Зарегистрирован: 14.11.2007 Сообщений: 2420
Re: Как хранить матрицу в БД
Хм. Ну, всяческие хитрые форматы типа разреженно-строчного — у них же своя структура, свои массивы, и нет нужды хранить всю матрицу целиком — можно хранить в базе эти самые определяющие матрицу массивы.
А графы, в которых мало ребер я бы хранил скорее в списках смежности .
Структуры данных для хранения и работы с матрицами
Доброго времени суток!
Есть матрица, у которой надо периодически удалять то столбец целиком, то строку.
Вариант «вектор векторов» дает возможность удалять либо строки, либо столбцы.
Если нужно и так и так, то приходится для чего-то одного(например, удаление строк) выбирать удаление вектора, а для другого(удаление столбцов) — создавать новую матрицу.
Собственно вопрос: существуют ли какие-то уже готовые структуры, с которыми можно осуществлять подобные операции над матрицами?
Собственно, принимаются любые варианты, лишь бы это было быстро и не тратило много памяти.
Поиск в гугле по ключевым словам, увы, ни к чему толковому не привел.
Заранее спасибо всем откликнувшимся!
Отслеживать
задан 9 авг 2013 в 21:09
miramentis miramentis
508 5 5 серебряных знаков 17 17 бронзовых знаков
@miramentis, почему Вы считаете, что при удалении столбца в методе «вектор векторов» (т.е. вектор указателей на вектора, каждый из которых представляет строку) требуется создание новой матрицы? Операция будет проводиться «по месту» (без переписывания данных в новую память). Конечно, время удаления столбца квадратично от размера матрицы («хвост» каждой строки придется сдвигать), но IMHO эта операция по сравнению с доступом к i,j-м элементам в целом алгоритме наверняка редка. А вот реализация тривиальна (программа останется понятной).
11 авг 2013 в 20:08
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Можно не удалять фактически элементы, а просто хранить индексы удаленных столбцов и строк. Пользователю класса предоставлять интерфейс, который будет мимикрировать под матрицу меньшего размера.
В качестве структуры данных для хранения удаленных индексов и бысрого нахождения соответствия нового индекса к исходному можно использовать немного модифицированное дерево отрезков поверх массива, хранящего 0 или 1, в зависимости от того удален элемент или нет. Подробнее можно прочитать в статье, пункт «Поиск префикса массива с заданной суммой».
Особенности ( N — линейный размер исходной матрицы, n — новой):
- Произвольный доступ за O(log(N)) , вместо O(1) .
- Итерация по строке/столбцу стоит O(N) , вместо O(n) . Но кажется, что итерирование по столбцу, если строки хранятся в векторах, сильно не пострадает.
- Удаление строки или столбца можно делать за O(log(N)) .
- Оверхед по памяти O(N) , что не сильно влияет на общий размер O(N^2) .
- Можно использовать для быстрого конструирования подматрицы исходной матрицы. Это может пригодиться, если мы захотим выполнить какой-то алгоритм над подматрицей, например верхней правой четвертью.
- Можно за лагарифм возвращать строки и столбцы обратно.
UPD Оказалось, что обход строки и столбца можно делать за O(n) , если я конечно правильно оценил асимптотику. Алгоритм простой: обходим листья дерева отрезков, в которых записана 1. При этом не заходим в поддеревья, у которых в корне записан 0, так как у них не может быть ненулевых листьев. Набросал демострационную программку на Python:
import random import sys def build(arr, tree, v, l, r): if l == r: tree[v] = arr[l] return c = (l + r) / 2 build(arr, tree, v * 2, l, c) build(arr, tree, v * 2 + 1, c + 1, r) tree[v] = tree[v * 2] + tree[v * 2 + 1] def traverse(tree, v, l, r, counter=[0]): counter[0] += 1 if l == r: yield l return c = (l + r) / 2 if tree[v * 2]: for i in traverse(tree, v * 2, l, c, counter): yield i if tree[v * 2 + 1]: for i in traverse(tree, v * 2 + 1, c + 1, r, counter): yield i length = int(sys.argv[1]) arr = [int(random.random() > 0.99) for i in xrange(length)] tree = [0] * length * 4 build(arr, tree, 1, 0, len(arr) - 1) slow = [i for (i, e) in enumerate(arr) if e == 1] counter = [0] fast = [i for i in traverse(tree, 1, 0, len(arr) - 1, counter)] assert(slow == fast) print "Total number:", len(arr) print "Number of non-deleted:", sum(arr) print "Number of visited nodes:", counter[0] Тут мы «удаляем» 99% элементов и строим список индексов неудаленных. В первом случае (slow), мы просто пробегаемся по всему массиву длиной length (1000000), и выводим индексы ненулевых элементов. Во втором случае (fast) мы обходим дерево. Результаты для разных length следующие:
Total number: 10000 Number of non-deleted: 103 Number of visited nodes: 802 Total number: 100000 Number of non-deleted: 1021 Number of visited nodes: 8016 Total number: 1000000 Number of non-deleted: 10060 Number of visited nodes: 78413 Total number: 10000000 Number of non-deleted: 99706 Number of visited nodes: 783587 Как видим сложность обхода вроде бы линейная, для полной уверенности нужно еще поварьировать процент удаленных узлов, но мне лень.
Хотя алгоритм и имеет меньшую сложность, не факт, что его стоит применять вообще. Как уже ниже заметили, в реальной жизни в алгоритмах на матрицах большую роль играет локальность чтения данных. Поэтому для строк такой «ускоренный» обход имеет смысл применять только в случае когда большая часть элементов удалена (тут надо эксперементировать, чтобы найти точные критерии).
Хранение матриц в БД и их выборка, реально?
В БД не очень хорошо разбираюсь, есть в какой ни будь БД поле с типом данных Матрица?
Допустим у меня есть 2 очень похожих матрицы с минимальной разницей
5 5 5
5 5 5
5 5 5
и
5 5 6
5 5 5
5 5 5
Есть какой-то алгоритм что бы быстро найти похожие матрицы, или найти максимально похожую матрицу на эту и т.п.?
- Вопрос задан более трёх лет назад
- 911 просмотров
Комментировать
Решения вопроса 0
Ответы на вопрос 2
Ответ написан более трёх лет назад
DrunkMaster @DrunkMaster Автор вопроса
Как именно, в какой БД?
DrunkMaster: Да в любой, наверно.
Обработка, разумеется, будет зависеть от выбранной СУБД и способа хранения.
Если РСУБД — заведите в таблице столько столбцов, сколько надо для размещения матрицы. Для обработки или процедуру пишите или переложите на ЯП, какой используете. Варианты разные есть: например, обрабатывать сами данные в R.
Можно и, например, в JSON хранить, если так больше устраивает.
Есть специализированные СУБД: www.paradigm4.com (по описанию, вроде, подходит).
DrunkMaster @DrunkMaster Автор вопроса
AVKor: благодарю за развернутый ответ! В mysql поля для матриц нет, по столбцам думал имитировать но боюсь запросы на выборку в этом случае станут слишком тяжёлыми, за ссылки отдельное спасибо, обязательно знакомлюсь.