Анекдот.
antilamer поместил у себя в посте ссылку про решение многих задач на графах с помощью матричных операций.
Хочу по этому поводу рассказать анекдот из опыта моих коллег.
Мы занимаемся моделированием цифровых схем и для его ускорения желательно отрезать от схемы всё лишнее - не нужные вычисления, повторяющиеся вычисления и тому подобное. Мой молодой коллега, когда я объяснил ему задачу и сказал, что это типичная графовая задача, воодушевился, откопал лекции и написал алгоритм.
- Работает, - говорит. - Только, Серёг... - мнётся.
- Что такое?
- Немного медленно работает. 19 минут на нашей тестовой схеме. Это нормально?
Мой прикидочный вариант, написанный на коленке, работал 12 секунд на той же схеме.
- Нет, - говорю, - не нормально. Очень медленно. Ты как это сделал?
- На матрицах, на умножении.
- Ты лучше на множествах сделай. Проще считать.
И мой коллега переделал решение на множествах. Через два дня его решение работало 19 секунд. Я спросил его, смотрел ли он профайлером на свой код. Он смотрел. Просто коллекции Java не давали возможности работать быстрее.
На том и остановились.
Проблема с поиском фиксированной точки в том, что умножение не совсем уж тривиальных матриц делает результат более плотным, чем исходные матрицы. Поэтому работа с разреженным представлением становится всё менее и менее выгодным. К тому же легко выбрать неправильное представление и словить O(N2) (что у нас и произошло).
Хочу по этому поводу рассказать анекдот из опыта моих коллег.
Мы занимаемся моделированием цифровых схем и для его ускорения желательно отрезать от схемы всё лишнее - не нужные вычисления, повторяющиеся вычисления и тому подобное. Мой молодой коллега, когда я объяснил ему задачу и сказал, что это типичная графовая задача, воодушевился, откопал лекции и написал алгоритм.
- Работает, - говорит. - Только, Серёг... - мнётся.
- Что такое?
- Немного медленно работает. 19 минут на нашей тестовой схеме. Это нормально?
Мой прикидочный вариант, написанный на коленке, работал 12 секунд на той же схеме.
- Нет, - говорю, - не нормально. Очень медленно. Ты как это сделал?
- На матрицах, на умножении.
- Ты лучше на множествах сделай. Проще считать.
И мой коллега переделал решение на множествах. Через два дня его решение работало 19 секунд. Я спросил его, смотрел ли он профайлером на свой код. Он смотрел. Просто коллекции Java не давали возможности работать быстрее.
На том и остановились.
Проблема с поиском фиксированной точки в том, что умножение не совсем уж тривиальных матриц делает результат более плотным, чем исходные матрицы. Поэтому работа с разреженным представлением становится всё менее и менее выгодным. К тому же легко выбрать неправильное представление и словить O(N2) (что у нас и произошло).