Длинная проблема с производительностью массива

Question

У меня есть массив char указателей длиной 175 000.Каждый указатель указывает на массив к-строк длиной 100, каждый символ либо 1, либо 0.Мне нужно сравнить разницу между строками.

char* arr[175000];

Пока у меня есть два цикла for, где я сравниваю каждую строку с любой другой строкой.Функции сравнения в основном берут две c-строки и возвращают целое число, которое представляет собой число разностей массивов.

На моей 4-ядерной машине это занимает очень много времени.В прошлый раз я оставил его на 45 минут, и он так и не закончился.Посоветуйте, пожалуйста, более быстрое решение или некоторые оптимизации.

---

Пример:

000010
000001

имеет разность 2, поскольку последние два бита не совпадают.

После вычисления разницы я сохраняю значение в другом массиве

                int holder;

                for(int x = 0;x < UsedTableSpace; x++){
                    int min = 10000000;

                    for(int y = 0; y < UsedTableSpace; y++){

                        if(x != y){
                            //compr calculates difference between two c-string arrays
                            int tempDiff =compr(similarity[x]->matrix, similarity[y]->matrix);

                            if(tempDiff < min){
                                min = tempDiff;
                                holder = y;
                            }
                        }       
                    }
                    similarity[holder]->inbound++;

                }

Answer 1

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

1. Поскольку вы используете каждый символ для представления 1или 0, вы используете в несколько раз больше памяти, чем нужно, что создает большое влияние на производительность, когда дело доходит до кэширования и тому подобного.Вместо этого представьте свои данные, используя числовые значения, которые вы можете представить в виде последовательности битов.
2. После того, как вы реализовали # 1, вы можете получить целое или длинное целое за раз и сделать побитовоеОперация XOR для получения числа, которое имеет 1 в каждом месте, где два числа не имеют одинаковых значений.Затем вы можете использовать некоторые из упомянутых здесь приемов для быстрого подсчета этих битов.

3. Поработайте над "развертыванием" ваших циклов, чтобы избежать необходимого количества прыжков.Например, следующий код:

   total = total + array[i];
   total = total + array[i + 1];
   total = total + array[i + 2];
   

   ... будет работать быстрее, чем просто повторение total = total + array[i] три раза.Скачки дороги и мешают конвейерной обработке процессора. Обновление: я должен упомянуть, что ваш компилятор, возможно, уже делает кое-что для вас - вы можете проверить скомпилированный код, чтобы увидеть.

4. Разбейте весь ваш набор данных на кускиэто позволит вам в полной мере использовать кеширование.Думайте о своей проблеме как о «квадрате» с индексом i на одной оси и осью j на другой.Если вы начнете с одного i и выполните итерацию по всем значениям 175000 j, первые посещенные вами значения j будут удалены из кэша к тому времени, как вы доберетесь до конца строки.С другой стороны, если вы возьмете верхний левый угол и перейдете от j = 0 до 256, большинство значений на оси j все равно будет находиться в низкоуровневом кеше, так как вы будете циклично сравнивать их с i =0, 1, 2 и т. Д.

Наконец, хотя это само собой разумеется, я думаю, стоит упомянуть: убедитесь, что ваш компилятор настроен на оптимизацию!

Answer 2

Одной простой оптимизацией является сравнение строк только один раз.Если разница между A и B равна 12, разница между B и A также равна 12. Ваше время бега уменьшится почти вдвое.

В коде:

int compr(const char* a, const char* b) {
  int d = 0, i;
  for (i=0; i < 100; ++i)
    if (a[i] != b[i]) ++d;
  return d;
}

void main_function(...) {

    for(int x = 0;x < UsedTableSpace; x++){
        int min = 10000000;

        for(int y = x + 1; y < UsedTableSpace; y++){

            //compr calculates difference between two c-string arrays
            int tempDiff = compr(similarity[x]->matrix, similarity[y]->matrix);

            if(tempDiff < min){
                min = tempDiff;
                holder = y;
            }
        }
        similarity[holder]->inbound++;
    }
}

Обратите внимание на второй цикл for, я изменил стартовый индекс.

Некоторые другие оптимизации - это запуск метода run в отдельных потоках, чтобы использовать ваши 4 ядра..

Answer 3

Какова ваша цель, т.е. что вы хотите сделать с расстояниями Хэмминга (каковы они есть) после того, как вы их получили? Например, если вы ищете ближайшую или самую дальнюю пару, вы, вероятно, можете получить алгоритм O (n ln n) вместо методов O (n ^ 2), предложенных до сих пор. (При n = 175000 n ^ 2 в 15000 раз больше, чем n ln n.)

Например, вы можете охарактеризовать каждое 100-битное число m с помощью 8 4-битных чисел, представляющих собой число битов, установленных в 8 сегментах m, и отсортировать полученные 32-битные сигнатуры в порядке возрастания. Сигнатуры ближайшей пары, вероятно, будут рядом в отсортированном списке. Можно легко ограничить расстояние между двумя числами, если их сигнатуры различаются, что дает эффективный процесс ветвления и ограничения при обнаружении менее удаленных чисел.