Нужно сделать очень большой массив [2 ^ 16 + 1] [2 ^ 16 + 1] - размер массива слишком велик :(

Question

Привет

Мне нужно вычислить энтропию первого порядка (источник Маркова, как в вики здесь http://en.wikipedia.org/wiki/Entropy_(information_theory) сигнала, который состоит из 16-битных слов. Это означает, что я должен вычислить, как частокаждая комбинация a-> b (символ b появляется после a) происходит в потоке данных. Когда я делал это только для 4 менее значимых или 4 более значимых битов, я использовал двумерный массив, где первое измерение было первымсимвол и второе измерение были вторым символом.

Мой алгоритм выглядел следующим образом

1. Считать текущий символ
2. Массив [prev_symbol] [curr_symbol] ++
3. prev_symbol = curr_symbol
4. Движение вперед на 1 символ

Тогда Array [a] [b] будет означать, сколько раз символ b проходил после символа a, встречался в astream.

Теперь я понимаю, что массив в C - это указатель, который увеличивается для получения точного значения, например, для получения элемента [3] [4] из массива [10] [10] мне нужно увеличить указательмассиву [0] [0] на (3 * 10 +4) (размер переменной хранится в массиве).Я понимаю, что проблема заключается в том, что 2 ^ 32 элемента типа unsigned long должны занимать слишком много времени.

Но все же, есть ли способ с этим справиться?

Или, может быть, есть другой способ сделать это?

Answer 1

Двумерный массив целых чисел (4 байта) с 32000 на 32000 элементов занимает около 16 ГБ оперативной памяти. У вашей машины столько памяти?

Так или иначе, из более чем 1 миллиарда элементов массива только очень немногие будут иметь число, отличное от нуля. Так что, вероятно, лучше пойти с каким-то редким хранилищем.

Одним из решений было бы использование словаря, в котором кортеж (a, b) - это ключ, а количество вхождений - это значение.

Answer 2

Провел быстрый тест на Ubuntu 10.10 x64

gt@thinkpad-T61p:~/test$ uname -a
Linux thinkpad-T61p 2.6.35-25-generic #44-Ubuntu SMP Fri Jan 21 17:40:44 UTC 2011 x86_64 GNU/Linux
gt@thinkpad-T61p:~/test$ cat mtest.c
#include <stdio.h>
#include <stdlib.h>

short *big_array;


int main(void)
{
    if((big_array = (short *)malloc(4UL*1024*1024*1024*sizeof (short))) == NULL) {
        perror("malloc");
        return 1;
    }

    big_array[0]++;
    big_array[100]++;
    big_array[1UL*1024*1024*1024]++;
    big_array[2UL*1024*1024*1024]++;
    big_array[3UL*1024*1024*1024]++;

    printf("array[100] = %d\narray[3G] = %d\n", big_array[100], big_array[3UL*1024*1024*1024]);

    return 0;
}
gt@thinkpad-T61p:~/test$ gcc -Wall mtest.c -o mtest
gt@thinkpad-T61p:~/test$ ./mtest 
array[100] = 1
array[3G] = 1
gt@thinkpad-T61p:~/test$ 

Похоже, что система виртуальной памяти в Linux готова к работе, если у вас достаточно памяти и / или подкачки.

Веселись!

Answer 3

Возможно, вы могли бы сделать несколько проходов по данным.Вклад энтропии для пар, начинающихся с символа X, по существу не зависит от пар, начинающихся с любого другого символа (кроме общего числа их, конечно), поэтому вы можете вычислить энтропию для всех таких пар и затем отбросить данные распределения.В конце объедините 2 ^ 16 частичных значений энтропии, чтобы получить общее значение.Вам не обязательно делать 2 ^ 16 проходов над данными, вы можете «интересоваться» таким количеством начальных символов за один проход, сколько у вас есть места.

В качестве альтернативы, если ваши данные меньшечем 2 ^ 32 выборок, то вы точно знаете, что не увидите все возможные пары, поэтому вам не нужно выделять счетчик для каждой из них.Если выборка достаточно мала или энтропия достаточно мала, то какой-то разреженный массив будет использовать меньше памяти, чем ваша полная матрица 16 ГБ.