Быстрый способ реализовать 2D свертку в C
Похоже, вы не проверяете songs[probe].getYear() == year во время цикла while в findYear.
Может быть:
public static int findYear(MusicV3[] songs, int year) {
int high = songs.length;
int low = -1;
int probe = -1;
while (high - low > 1) {
probe = (high + low) / 2;
int probeSongYear = songs[probe].getYear();
if (probeSongYear == year) {
break;
} else if (probeSongYear > year)
high = probe;
else
low = probe;
}
if (probe >= 0 && songs[probe].getYear() == year) {
while (songs[--probe].getYear() == year) {
}
return probe + 1;
}
return -1;
}
Не забудьте добавить «find =», как показано ниже:
System.out.println("Searching for the year: 2014");
find = /* <--- ADD THIS */ findYear(songs, 2014);
Чтобы напечатать все песни (как требуется в комментарии) для рассматриваемый год:
System.out.println("Searching for the year: 2014");
find = findYear(songs, 2014);
if (find != -1) {
System.out.println("We found songs made in the year 2014 in the song list: ");
while (sortedSongs[find].getYear() == 2014) {
System.out.println(sortedSongs[find++]);
}
}
3 ответа
Вы уверены, что хотите использовать FFT? Это будет целым массивом, преобразовывают, который будет дорогим. Если Вы уже выбрали 9x9 фильтр свертки, Вам не нужен никакой FFT.
Обычно самый дешевый способ сделать свертка в C должна настроить цикл, который перемещает указатель через массив, суммируя скрученные значения в каждой точке и пишущий данные в новый массив. Этот цикл может затем быть параллелизирован с помощью любимого метода (векторизация компилятора, библиотеки MPI, OpenMP, и т.д.).
Относительно границ:
- Если Вы предполагаете, что значения 0 внешней стороны границы, то добавьте 4 границы элементов 0 к Вашему 2-му массиву точек. Это избежит потребности в том, 'если' операторы для обработки границ, которые являются дорогими.
- Если Ваши данные переносятся на границах (т.е. это периодически), то используйте модуль или добавьте 4 границы элементов, которые копируют противоположную сторону сетки (abcdefg-> fgabcdefgab для 2 точек). ** Примечание: это - то, что Вы неявно принимаете с любым видом преобразования Фурье, включая FFT **. Если это не так необходимо было бы объяснить его, прежде чем любой FFT будет сделан.
4 точки - то, потому что максимальное граничное перекрытие 9x9 ядро является 4 точками вне основной сетки. Таким образом, n точки границы, необходимой для 2n+1 x 2n+1 ядро.
Если Вам нужна эта свертка, чтобы быть действительно быстрыми, и/или Ваша сетка является большой, рассмотрите разделение ее в мелкие кусочки, которые могут быть сохранены в кэше процессора и таким образом вычислены намного более быстро. Это также идет для любой разгрузки GPU, которую Вы могли бы хотеть сделать (они идеальны для этого типа вычисления с плавающей точкой).
Вот является ссылка теории http://hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf
И вот ссылка на fftw, который является довольно хорошей библиотекой FFT, которой я пользовался в прошлом (проверьте лицензии, чтобы удостовериться, что это подходит), http://www.fftw.org/
Все, что Вы делаете, является FFT Ваше изображение и ядро (9x9 матрица). Умножьтесь вместе, затем обратно преобразуйте.
Однако с 9x9 матрица можно все еще лучше делать его в реальных координатах (только с двойным циклом по пикселям изображения и матрице). Попробуйте оба пути!
На самом деле вам не нужно использовать размер БПФ, достаточно большой, чтобы вместить все изображение. Вы можете делать много меньших перекрывающихся 2D-изображений. Вы можете выполнить поиск по запросу «быстрая свертка» «сохранение с перекрытием» «добавление с перекрытием».
Однако для ядра 9x9. Вы можете не увидеть большого преимущества в скорости.