Рефакторинг Сложных алгоритмов
От: vvv848165@ya.ru  
Дата: 04.11.19 10:36
Оценка:
А такое вобще возможно без особого вреда для производительности?

Сколько не смотрел всяких реализаций алгоритмов — рефакторинг там проводится крайне редко (только в спец отраслях — типа распознования изображений)

посоветуйте на примере "Transform" https://github.com/VVVaSoft/Fast-Fourier-transform/blob/master/FFTCooleyTukey.cs что можно сделать?
Re: Рефакторинг Сложных алгоритмов
От: Quadri  
Дата: 04.11.19 14:14
Оценка:
Здравствуйте, vvv848165@ya.ru, Вы писали:

VYR>А такое вобще возможно без особого вреда для производительности?


VYR>Сколько не смотрел всяких реализаций алгоритмов — рефакторинг там проводится крайне редко (только в спец отраслях — типа распознования изображений)


VYR>посоветуйте на примере "Transform" https://github.com/VVVaSoft/Fast-Fourier-transform/blob/master/FFTCooleyTukey.cs что можно сделать?


Рефакторинг нужен что бы облегчить будущее внесение изменений в код. Для реализаций алгоритмов как правило таких требований нет.
Re: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.11.19 14:00
Оценка: 1 (1)
Здравствуйте, vvv848165@ya.ru, Вы писали:
VYR>посоветуйте на примере "Transform" https://github.com/VVVaSoft/Fast-Fourier-transform/blob/master/FFTCooleyTukey.cs что можно сделать?
А чего вы хотите?
Рефакторинг, by definition — это преобразование кода с сохранением его функциональности, но изменением нефункциональных характеристик.
Обычно этой характеристикой выступает готовность к внесению каких-то изменений.
Ну там — хочется, скажем, иметь возможность применять не только Fourier Transform, но и Laplace Transform. Тогда выделяем общую базу, FFT становится наследником, и всё такое.
После рефакторинга — коммит (проверенный тестами на предмет сохранения функциональности), и уже после него начинаем внедрять Laplace Transform.

Но, в принципе, можно и другую нефункциональную характеристику крутить — ну там, производительность к примеру.

Вы-то чего хотите добиться при помощи рефакторинга?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.11.19 14:02
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Вы-то чего хотите добиться при помощи рефакторинга?

Кстати, код в репозитории мало того, что неоптимальный, так он ещё и нерабочий.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Рефакторинг Сложных алгоритмов
От: vvv848165@ya.ru  
Дата: 06.11.19 10:59
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, vvv848165@ya.ru, Вы писали:

VYR>>посоветуйте на примере "Transform" https://github.com/VVVaSoft/Fast-Fourier-transform/blob/master/FFTCooleyTukey.cs что можно сделать?
S>А чего вы хотите?
S>Рефакторинг, by definition — это преобразование кода с сохранением его функциональности, но изменением нефункциональных характеристик.
S>Обычно этой характеристикой выступает готовность к внесению каких-то изменений.
S>Ну там — хочется, скажем, иметь возможность применять не только Fourier Transform, но и Laplace Transform. Тогда выделяем общую базу, FFT становится наследником, и всё такое.
S>После рефакторинга — коммит (проверенный тестами на предмет сохранения функциональности), и уже после него начинаем внедрять Laplace Transform.

S>Но, в принципе, можно и другую нефункциональную характеристику крутить — ну там, производительность к примеру.


S>Вы-то чего хотите добиться при помощи рефакторинга?

Только повысить читабельность кода — метод большой — антипаттерн даже такой есть...
Re[3]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 07.11.19 03:39
Оценка:
Здравствуйте, vvv848165@ya.ru, Вы писали:
S>>Вы-то чего хотите добиться при помощи рефакторинга?
VYR>Только повысить читабельность кода — метод большой — антипаттерн даже такой есть...
Ну, во-первых, метод там небольшой.
Во-вторых, рефакторинг его в целях улучшения читаемости проводить можно смело — он написан весьма неэффективно, испортить его сложно.
В-третьих, там нужен не столько рефакторинг, сколько выбор подходящих наименований для переменных и функций.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Рефакторинг Сложных алгоритмов
От: Буравчик Россия  
Дата: 11.11.19 15:39
Оценка:
Здравствуйте, vvv848165@ya.ru, Вы писали:

VYR>Только повысить читабельность кода — метод большой — антипаттерн даже такой есть...


Метод не очень-то и большой, не обязательно уменьшать. Хотя, можно выделить в отдельную функцию тело цикла (обработку одного блока).

При реализации алгоритмов желательно давать ссылку на текстовое описание алгоритма, объяснение. В коде придерживаться названий переменных из этого описания.

В Init создается куча "глобальных" переменных. Я бы постарался, по-возможности, избавиться от них, перенести их инициализацию в Transform().
Best regards, Буравчик
Re[3]: Рефакторинг Сложных алгоритмов
От: vvv848165@ya.ru  
Дата: 12.11.19 05:42
Оценка:
Здравствуйте, Sinclair, Вы писали:
S>Кстати, код в репозитории мало того, что неоптимальный, так он ещё и нерабочий.
А что с ним не так ???
с https://www.alglib.net/ сравнивал всё сходилось ... (правда коэффициенты пришлось убирать — чтобы всё как в alglib было)
не оптимальный в Чём???
Re[4]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 12.11.19 06:02
Оценка:
Здравствуйте, vvv848165@ya.ru, Вы писали:
VYR>А что с ним не так ???
Начнём с того, что class FFTCooleyTukey унаследован от FFT, который нигде не определён.
VYR> с https://www.alglib.net/ сравнивал всё сходилось ... (правда коэффициенты пришлось убирать — чтобы всё как в alglib было)
VYR> не оптимальный в Чём???
Обращения к массивам сделаны так, что JIT не может устранить проверки границ.
О векторизации остаётся только мечтать. В общем, его можно ещё очень и очень разогнать.

Кстати, Кули-Тьюки применим для более-менее любой размерности данных, а не только 2^N.
Для "хороших" размерностей типа 1000 эффективность будет почти такая же, как и для близких к ним степеней двойки.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Рефакторинг Сложных алгоритмов
От: Sharov Россия  
Дата: 12.11.19 09:38
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Обращения к массивам сделаны так, что JIT не может устранить проверки границ.


А это в подобных алгоритмах вообще возможно избежать? Кажется претензия не по существу.
Кодом людям нужно помогать!
Re[6]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 12.11.19 10:05
Оценка: 6 (1)
Здравствуйте, Sharov, Вы писали:
S>А это в подобных алгоритмах вообще возможно избежать? Кажется претензия не по существу.
Конечно можно. Span<T> — ваш лучший друг. Сразу за ним идёт unsafe, который ровно для этого и придуман.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Рефакторинг Сложных алгоритмов
От: Шахтер Интернет  
Дата: 16.11.19 06:24
Оценка:
Здравствуйте, vvv848165@ya.ru, Вы писали:

VYR>А такое вобще возможно без особого вреда для производительности?


VYR>Сколько не смотрел всяких реализаций алгоритмов — рефакторинг там проводится крайне редко (только в спец отраслях — типа распознования изображений)


VYR>посоветуйте на примере "Transform" https://github.com/VVVaSoft/Fast-Fourier-transform/blob/master/FFTCooleyTukey.cs что можно сделать?


Данный код не требует какого-то особенного рефакторинга. Единственное, я бы заменил сдвиги на Pow2(). Ну и поработал бы над эстетикой, типа имен переменных.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[5]: Рефакторинг Сложных алгоритмов
От: Шахтер Интернет  
Дата: 17.11.19 07:11
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, vvv848165@ya.ru, Вы писали:

VYR>>А что с ним не так ???
S>Начнём с того, что class FFTCooleyTukey унаследован от FFT, который нигде не определён.
VYR>> с https://www.alglib.net/ сравнивал всё сходилось ... (правда коэффициенты пришлось убирать — чтобы всё как в alglib было)
VYR>> не оптимальный в Чём???

S>Обращения к массивам сделаны так, что JIT не может устранить проверки границ.

S>О векторизации остаётся только мечтать. В общем, его можно ещё очень и очень разогнать.

Я бы начал с того, что сделал бы его in-place. Доп. память здесь не нужна.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[6]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 17.11.19 12:43
Оценка:
Здравствуйте, Шахтер, Вы писали:


Ш>Я бы начал с того, что сделал бы его in-place. Доп. память здесь не нужна.

Он вроде бы и так inplace, только как-то очень странно.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[7]: Рефакторинг Сложных алгоритмов
От: Шахтер Интернет  
Дата: 17.11.19 16:44
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Шахтер, Вы писали:



Ш>>Я бы начал с того, что сделал бы его in-place. Доп. память здесь не нужна.

S>Он вроде бы и так inplace, только как-то очень странно.

Ну какой же он inplace,


 tmp1 = new Complex[NN];
 tmp2 = new Complex[NN];

 Complex[] data = tmp1;
 Complex[] dest = tmp2;

 {
  Complex d1 = data[offset_block + j];
  Complex d2 = data[offset_block_half + j];

  dest[offset_block + j] = d1 + d2;
  dest[offset_block_half + j] = (d1 - d2) * w;
 }

 tmp = data;
 data = dest;
 dest = tmp;


Два временных буфера, они постоянно переключаются. Зачем всё это сделано -- непонятно.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[8]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 18.11.19 03:34
Оценка:
Здравствуйте, Шахтер, Вы писали:
Ш>Ну какой же он inplace,
Ш>Два временных буфера, они постоянно переключаются. Зачем всё это сделано -- непонятно.
Вот-вот. При этом сигнатура — inplace, то есть мы безвозвратно портим исходный массив.
Я бы как раз понял, если бы Transform имел сигнатуру Complex[] Transform(Complex[] data)
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Рефакторинг Сложных алгоритмов
От: vvv848165@ya.ru  
Дата: 09.12.19 11:03
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Кстати, Кули-Тьюки применим для более-менее любой размерности данных, а не только 2^N.

S>Для "хороших" размерностей типа 1000 эффективность будет почти такая же, как и для близких к ним степеней двойки.

а не подскажите как или где-нибудь написано про это ? (чтобы не степень двойки размерность была)
Re[6]: Рефакторинг Сложных алгоритмов
От: Sinclair Россия https://github.com/evilguest/
Дата: 09.12.19 17:07
Оценка:
Здравствуйте, vvv848165@ya.ru, Вы писали:

VYR>Здравствуйте, Sinclair, Вы писали:


S>>Кстати, Кули-Тьюки применим для более-менее любой размерности данных, а не только 2^N.

S>>Для "хороших" размерностей типа 1000 эффективность будет почти такая же, как и для близких к ним степеней двойки.

VYR>а не подскажите как или где-нибудь написано про это ? (чтобы не степень двойки размерность была)

Да практически везде. Вот, скажем, википедия:
https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.