Дизайн API для матричной библиотеки?

Question

[spiff]

Я довольно давно занимаюсь разработкой небольшой Java библиотеки для работы над задачами линейной алгебры и мне приходилось часто принимать решения по поводу дизайна публичного API. До этого момента все шло отлично. Но недавно появился один момент который не дает мне покоя. Хотелось бы узнать мнение сообщества о том как поступить в такой ситуации.


В чем суть. Есть разреженные матрицы, которые в основном хранят нули и лишь несколько значимых элементов. Сейчас я на пороге выбора добавлять ли в публичный API для разреженных матриц метод toArray(). С одной стороны у пользователя должна быть такая возможность (конвертировать матрицу в двумерный массив). С другой — эта операция прямо противоречит всей идеологии разреженных матриц — уменьшение используемой памяти.


Еще одна сторона медали — я решил разделить семейство плотных и разреженных матриц на уровне интерфейса. И сейчас я не могу придумать ни одного метода, который был бы характерен для плотных но не применим к разреженным. Метод toArray() очень подходит на эту роль, в то время как метод cardinality() — количество не нулевых элементов — явный претендент для API разреженных.


Резюмируя. Есть потребность придумать характерный метод для плотной матрицы. Есть кандидат — самый низко висящий фрукт — toArray(). Префекционист во мне говорит что toArray() должен быть у всех. Лентяй и костыльный программист — только у плотных.


Очень прошу совета у сообщества что делать со злополучным методом.

Answer 1

[Владимир Голованов]

Сразу: код не смотрел.

Однако по концепции я бы лично не стал выносить toArray() в общий интерфейс, т.к. слабо могу себе представить, где было бы необходимо преобразовывать разряженную матрицу в обычную. Лучше посмотреть сценарии, когда такое преобразование кажется логичным, и вынести в интерфейс операции, которые вынуждают Вас выносить toArray() в общий интерфейс. Для разряженных операций эта операция по определению дорогая, и, IMHO, в реальных задачах от этого не много смысла.

Comments

[Владимир Голованов]

P.S. Описанная выше идея с функторами — другое дело :-) Это гораздо лучше, чем «в тупую» преобразовывать в массивы. Программисты — тоже люди, если им дали интерфейс, то не всякий заглянет «под капот», особенно если прилететь может любая реализация. Будет toArray() — обязательно появится его использование для разряженных матриц, что посадит производительность. Не стоит рыть себе яму.

[spiff]

Большое спасибо за ваши мысли!

Вот собственно именно так я и думал, что метод toArray() — это абсолютно легальный способ подтолкнуть программиста работать со структурами не эффективно и идеологически не правильно.

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

Answer 2

[Artyushov]

Мне кажется, что метод toArray() должен быть реализован в обоих типах матриц. Если есть интерфейс Matrix, то в нём должен быть метод toArray(). Уже в конкретной реализации разреженной матрицы можно добавить метод, предствляющий матрицу в более компактном виде.

Специфичность разреженной матрицы должна быть на уровне реализации, например использование более оптимальных алгоритмов при перемножении и т.п. Это как LinkedList и ArrayList. Методы-то в них одинаковые, пользователь сам решает для чего он будет использовать список и выбирает реализацию. Кажется, что в вашем случае должно быть так же.

Comments

[spiff]

Спасибо за ответ!

Уже второй говорите о том, что toArray() нужен для всех. Может быть действительно так и надо поступить.

Answer 3

[Руслан Лопатин]

Что-то не увидел в API la4j таких очевидных, на мой взгляд, вещей, как итераторы (или функторы). Чтобы обрабатывать элементы матрицы построчно или по столбцам, например. Если это вообще нужно, конечно.

Вот перебор для разреженных матриц мог бы выглядеть несколько иначе, чем для плотных. Чтобы не перебирать каждый элемент разреженной матрицы можно было бы завести специальный итератор, который бы пропускал нулевые элементы. А для разреженной матрицы можно было бы использовать итератор попроще — не пропускающий элементы, «плотный». С ним и работать было бы легче.

И тот и другой вид итераторов можно реализовать для обоих видов матриц, но понятно, что «плотный» итератор неэффективен в применении к разреженным матрицам.

Задача API не только в том, чтобы давать возможности, но и подталкивать к выбору правильных решений. А использование «плотного» итератора для разреженных матриц — неправильное решение, так что его можно было бы в интерфейс разреженных матриц не добавлять совсем.

Comments

[Руслан Лопатин]

А для разреженной матрицы можно было бы использовать итератор попроще

для плотной матрицы, конечно же

[spiff]

Итераторы — это вещи совершенно не свойственные матрицам вот в чем дело. Все базовые алгоритмы линейной алгебры построены именно на произвольном доступе по (i, j). Итераторы для коллекций применимы в большей степени. Т.е. там где хранимый объект имеет бОльший смысл чем сама коллекция и может быть обработан автономно. С матрицами все не так. Отдельные значения мало кого интересую — интересна вся матрица целиком. Сложно назвать обычную матрицу с double значениями коллекцией чисел — это скорее самостоятельный, неделимый объект.

Честно сказать, я встречал итераторы по матрицам у Apache Common Math. Но там другая история — Матрица там дейтсвительно коллекция с generic типом. Т.е. может хранить обычные объекты. В таком случае сложно представить использование такой матрицы в каком-нибудь SVD разложении. С la4j ситуация другая — это чистой воды математическая библиотека для матриц вещественных чисел.

[Руслан Лопатин]

Это понятно. Ну а как реализуются, например, сложение или умножение матриц? Поэлементно. Для разреженных и плотных матриц реализации должны быть разными, а иначе — неэффективно. А новые матричные операции как реализовывать? Опять несколько вариантов делать?

Так что если не итераторы, то функторы пригодились бы. Возможно. С функторами можно написать один алгоритм операции, но разные реализации перебора. Их выполнение можно было бы и распараллеливать, что актуально для больших объёмов данных…

Впрочем, зависит от конечных потребностей, конечно же.

[spiff]

Вообщем-то всерьез задумался над вашими рассуждениями. Вот к чему это привело: code.google.com/p/la4j/source/detail?r=174.

Может быть действительно пользователям пригодится такой функционал. По крайней мере, я его хочу использовать для нового IO. Спасибо за идею :)

Answer 4

[1nd1go]

Есть разреженные матрицы, которые в основном хранят нули и лишь несколько значимых элементов. <...> С другой — эта операция прямо противоречит всей идеологии разреженных матриц — уменьшение используемой памяти.

toArray() в данном случае, можно понимать как сериализацию, соответственно, то, что вы выдадите массив заполненный сплошными значениями (в том числе и 0), ничего противоестественного не произойдет. Понятно, что хранить и совершать операции пользователь будет над оптимальной структурой.

Разделять матрицы на уровне интерфейса если вы не можете придумать действительно значимые различия, может быть неправильным. Вспомните интерфейс List и имплментации LinkedList и ArrayList. Было бы странно их разделять на уровне интерфейса.

Comments

[spiff]

Да, я согласен с тем, что toArray() имеет некоторый смысл для разреженных матриц, но все таки не думаю что он будет широко использоваться. Если говорить о сериализации — то я поддерживаю ее на уровне Java Serialization API.

Что касается интерфейсов. Пример со списками не очень удачный. И ArrayList и LinedList — это реализации. В то время как, SparseMatrix и DenseMatrix — интерфейсы различный видов матриц, которые имею реализации. Например CSR (Compressed Sparse Row) для разреженные и 1D Array — реализация плотной матрицы на основе одномерного массива. Т.е. реализаций может быть много для каждого отдельного вида.

В любом случае, спасибо за ответ!