-
Notifications
You must be signed in to change notification settings - Fork 0
SergioCSC/hadamard_cpp
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
В этом файле содержится описание файлов, а также обоснование решения и доказательство его эффективности. Описание файлов. Все решение содержится в единственном файле hadamard_cpp\src\hadamard_inverser.h. В заголовочном файле потому, что решение использует для оптимизации скорости inline-функции, которые должны быть определены в месте объявления. Кроме того, есть 5 файлов тестов в папке hadamard_cpp\tests: run_tests.cpp (запускает тесты) Tests.h и Tests.cpp -- описание тестов TestTemplate.h и TestTemplate.cpp -- предок класса Tests, содержит неспецифичные конкретным тестам методы. (Еще есть 3 файла, созданные профилировщиком Visual Studio: performance_report_1e7_transforms.diagsession -- 1e7 обратных преобразований оптимизированным кодом; performance_report_1e7_transforms_direct_matrix_multiply.diagsession -- код без быстрого преобразования Уолша, использующий прямое умножение матриц. Программа в 1,5 раза медленнее; performance_report_1e7_transforms_float_division.diagsession -- деление на 16 с использованием чисел с плавающей точкой, программа в 2,2 раза медленнее.) Обоснование решения и доказательство эффективности. Используя тот факт, что A^-1 = 1/4 * A и домножая обе части исходного равенства R - P = A * C * A на A^-1 слева и справа, получаем С = 1/16 * A * (R - P) * A. Это можно вычислить с использованием быстрого преобразования Уолша в 1,5 раза быстрее, чем умножая матрицы (8 операций на строку против 12; из теста производительности это тоже видно). Детали есть в комментариях в коде. Вряд ли это можно вычислить еще быстрее, но доказать это я не могу. В данный момент программа выполняет вычисление 1e7 обратных преобразований за 5,5 сек на домашнем компьютере, или чуть меньше 2-х миллионов преобразований в секунду.
About
job offer problem with Fast Walsh Hadamard Transform
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published