Анализ / оптимизация тяжелых вычислений

Question

Прежде всего, у меня нет операций умножения, деления, чтобы я мог использовать сдвиг / сложение, умножение переполнения, предварительные вычисления и т. Д. Я просто сравниваю одно n-битное двоичное число с другим, но согласно алгоритмуколичество таких операций кажется огромным.Вот оно:

1. Дана последовательность из 0 и 1, разделенная на блоки.Пусть длина последовательности равна S, длина блока равна N, что является некоторой степенью двойки (4,8,16,32 и т. Д.).Количество блоков равно n = S / N, здесь нет науки о ракетах.
2. В соответствии с выбранным N я строю набор всех возможных N-битных двоичных чисел, который представляет собой набор из 2 ^ N-1.objects.
3. После этого мне нужно сравнить каждое двоичное число с каждым блоком из исходной последовательности и вычислить, сколько раз было совпадение для каждого двоичного числа , например:S: 000000001111111100000000111111110000000011111111 ... (0000000011111111 повторяется 6 раз, 16 бит x 6 = 96 бит в целом)N: 8блоки: {00000000, 11111111, 00000000, 1111111, ...}расчеты:

.

// _n = S/N;
// _N2 = Math.Pow(2,N)-1
// S=96, N=8, n=12, 2^N-1=255 for this specific case
// sourceEpsilons = list of blocks from input, List<string>[_n]
var X = new int[_n]; // result array of frequencies
for (var i = 0; i < X.Length; i++) X[i] = 0; // setting up
for (ulong l = 0; l <= _N2; l++) // loop from 0 to max N-bit binary number
var currentl = l.ToBinaryNumberString(_N/8); // converting counter to string, getting "current binary number as string"
var sum = 0; // quantity of currentl numbers in blocks array
for (long i = 0; i < sourceEpsilons.LongLength; i++)
{
   if (currentl == sourceEpsilons[i]) sum++; // evaluations of strings, evaluation of numbers (longs) takes the same time
}
// sum is different each time, != blocks quantity                    
for (var j = 0; j < X.Length; j++) 
if (sum - 1 == j) X[j]++; // further processing
// result : 00000000 was matched 6 times, 11111111 6 times, X[6]=2. Don't ask me why do i need this >_<

При даже малых S я, кажется, имею (2 ^ N-1) (S / N) итераций, при N = 64 число растетдо 2 ^ 64 = (максимальное значение типа long), так что это не красиво.Я уверен, что есть необходимость оптимизировать циклы и, возможно, кардинально изменить подход (реализация c # для N = 32 требует 2h @ двухъядерный ПК с Parallel.For).Любые идеи, как сделать вышеупомянутую схему меньше времени и ресурсов ?Кажется, что мне нужно предварительно вычислить двоичные числа и избавиться от первого цикла, прочитав «i» из файла и оценив его с блоками «на лету», но размер файла будет (2 ^ N) * N байт ((2 ^ N-1) +1) * N), что тоже как-то неприемлемо.

Answer 1

Похоже, что вы хотите, чтобы подсчитать, сколько раз каждый конкретный блок произошел в вашей последовательности; в этом случае сравнение каждого блока с всеми возможными блоками и затем подсчет - это ужасный способ сделать это. Вам гораздо лучше создать словарь, который отображает блоки в счетчики; как то так:

var dict = Dictionary<int, int>();
for (int j=0; j<blocks_count; j++)
{
    int count;
    if (dict.TryGetValue(block[j], out count)) // block seen before, so increment
    {
        dict[block[j]] = count + 1;
    }
    else // first time seeing this block, so set count to 1
    {
        dict[block[j]] = 1; 
    }
}

После этого счет q для любого конкретного блока будет в dict[the_block], а если этот ключ не существует, то счет будет 0.

Answer 2

Вместо словаря вы также можете использовать плоский файл размером 2 ^ N записей, каждый размером, например, целое число.

Это будет ваша счетная площадка. Вместо того, чтобы перебирать все возможные числа в коллекции и сравнивать с вашим текущим просмотренным номером, вы перебираете S вперед только так:

procedure INITIALIZEFLATFILE is
    allocate 2^N * sizeof(integer) bytes to FLATFILE
end procedure

procedure COUNT is
    while STREAM is not at END
        from FLATFILE at address STREAM.CURRENTVALUE read integer into COUNT
        with FLATFILE at address STREAM.CURRENTVALUE write integer COUNT+1
        increment STREAM
    end while
end procedure

Словарь вначале консервативен по пространству и требует поиска нужного индекса позже. Если в конечном итоге вы ожидаете все возможные целые числа, вы можете сохранить «карту результата» фиксированного размера от getgo.

Answer 3

Вы пытаетесь получить количество уникальных сообщений в S? Например, в данном примере для N = 2 вы получите 2 сообщения (00 и 11), для N = 4 вы получите 2 сообщения (0000 и 1111) и для N = 8 Вы получаете 1 сообщение (00001111). Если это так, то словарный подход, предложенный tzaman , является одним из способов. Другой - сначала отсортировать список, затем просмотреть его и найти каждое сообщение. Третий, наивный подход заключается в том, чтобы использовать сторожевое сообщение, например, все 0, и выполнять поиск сообщений, не являющихся сторожевым. Когда вы найдете один, уничтожьте все его копии, установив их на страже. Например:

int CountMessages(char[] S, int SLen, int N) {
    int rslt = 0;
    int i, j;
    char *sentinel;

    sentinel = calloc((N+1)*sizeof(char));

    for (i = 0; i < N; i ++)
        sentinel[i] = '0';

    //first, is there a sentinel message?
    for (i = 0; ((i < SLen) && (rslt == 0)); i += N) {
        if (strncmp(S[i], sentinel, N) == 0)
            rslt++;
    }

    //now destroy the list and get only the unique messages
    for (i = 0; i < SLen; i += N) {
        if (strncmp(S[i], sentinel, N) != 0) { //first instance of given message
            rslt++;                
            for (j = i+N; j < SLen; j += N) { //look for all remaining instances of this message and destroy them
                if (strncmp(S[i], S[j], N) == 0)
                    strncpy(S[j], sentinel, N); //destroy message
            }
        }
    }

    return rslt;
}

Первый означает использование заранее написанного словаря или написание собственного. Второй и третий уничтожают список, то есть вы должны использовать копию для каждого «N», которое вы хотите проверить, но это довольно просто. Что касается распараллеливания, то словарь является самым простым, поскольку вы можете разбить строку на столько разделов, сколько у вас есть потоков, создать словарь для каждого, а затем объединить сами словари, чтобы получить окончательные значения. Во-вторых, я полагаю, что сама сортировка может быть легко сделана параллельной, тогда есть последний проход для подсчета. Третий требует, чтобы вы выполняли дозорную строку для каждой подстроки, а затем переделывали ее для последней рекомбинированной строки.

Обратите внимание на важную идею: вместо того, чтобы перебирать все возможные ответы, вы только перебираете все данные!

Answer 4

Я просто сравниваю одно n-битное двоичное число с другим

Разве не для этого memcmp?

Вы просматриваетекаждое возможное целое значение, и это занимает 2 часа, и вы удивлены этим?Вы ничего не можете сделать, чтобы упорядочить вещи, если вам нужно многократно повторять.