Реализация чрезвычайно разреженных массивов

Question

У меня очень разреженный статический массив с 4 измерениями по 8192 каждое, из которых я хочу выполнить поиск из (C #). Только 68796 из этих 4,5 * 10 ^ 15 значений являются ненулевыми. Какой самый быстрый способ сделать это, при этом скорость и низкое использование памяти имеют жизненно важное значение?

Спасибо

Answer 1

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

Как насчет использования "> словаря , где вы используете 4- кортеж как индекс?

var lookup = new Dictionary<Tuple<int,int,int,int>, int>();

Я никогда не делал этого сам, но он должен работать нормально.Если у вас нет готового Tuple, потому что вы работаете с версией .NET Framework, предшествующей .NET 4, вы можете указать свой собственный тип индекса:

struct LookupKey
{
    public readonly int First;
    public readonly int Second;
    public readonly int Third;
    public readonly int Fourth;
    …
}

var lookup = new Dictionary<LookupKey, int>();

Answer 2

Вы можете использовать обычную Dictionary или создать аналогичную карту, подходящую для ваших нужд (это будет массив, в который вы помещаете элементы в соответствии с хеш-значением, которое вы рассчитываете для своих 4 значений), но вам нужно позаботиться о столкновения.

Также двоичное дерево поиска может помочь, если вы примете логарифмическую сложность для поиска.

Answer 3

Я думаю, что лучше всего использовать хеш-таблицу (Dictionary<T, int>), индексированную с помощью пользовательского struct, содержащего 4 индекса.Не забудьте переопределить object.Equals() и object.GetHashCode() на этом struct.

Answer 4

Для этого я бы использовал хеш-списки вместо «обычных» массивов, затем (псевдокод):

// first, check bounds:
if(x < 0 || y < 0 || z < 0 || w < 0
|| x > xsize || y > ysize || z > zsize || w > wsize)
    throw new Whatever(...);

// now return value if != 0
if(x in arr && y in arr[x] && z in arr[x][y] && w in arr[x][y][z])
    return arr[x][y][z][w];
else
    return 0;

Answer 5

Использовать хеш-таблицу (общий словарь уже реализован как Hashtable). В качестве ключа используется вектор 4-х мерного индекса. Как хранилище значений, что вы хотите.