Супер длинные массивы в C ++

Question

У меня есть два набора A и B. Набор A содержит уникальные элементы. Набор B содержит все элементы. Каждый элемент в B представляет собой матрицу 10 на 10, где все записи равны 1 или 0. Мне нужно сканировать набор B, и каждый раз, когда я сталкиваюсь с новой матрицей, я добавляю ее в набор A. Поэтому набор A является подмножеством B содержащие только уникальные матрицы.

Answer 1

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

Обновление:

Если набор B является лишь некоторымматриц, а не набор всех возможных двоичных матриц 10x10, тогда вы просто хотите разреженный массив.Каждый раз, когда вы находите новую матрицу, вы вычисляете ее ключ (который может быть просто матрицей, преобразованной в двоичное значение из 100 цифр или даже строку из 100 символов!), Ищите этот индекс.Если такого ключа не существует, введите значение 1 для этого ключа.Если ключ существует, увеличьте и повторно сохраните новое значение для этого ключа.

Answer 2

Вот код, возможно, не очень эффективный:

# include <vector>
# include <bitset>
# include <algorithm>

// I assume your 10x10 boolean matrix is implemented as a bitset of 100 bits.

// Comparison of bitsets
template<size_t N>
class bitset_comparator
{
    public :
      bool operator () (const std::bitset<N> & a, const std::bitset<N> & b) const
      {
          for(size_t i = 0 ; i < N ; ++i)
          {
              if( !a[i] && b[i] )       return true ;
              else if( !b[i] && a[i] )  return false ;
          }
          return false ;
      }
} ;

int main(int, char * [])
{
    std::set< std::bitset<100>, bitset_comparator<100> > A ;
    std::vector< std::bitset<100> >                      B ; 


    // Fill B in some manner ...

    // Keeping unique elements in A
    std::copy(B.begin(), B.end(), std::inserter(A, A.begin())) ;
}

Вы можете использовать std::list вместо std::vector.Относительный порядок элементов в B не сохраняется в A (элементы в A сортируются).

РЕДАКТИРОВАТЬ: я инвертировал A и B в моем первом посте.Теперь это правильно.Приносим извинения за неудобства.Я также исправил функтор сравнения.

Answer 3

Каждый элемент в матрице B представляет собой матрицу 10 на 10, где все записи равны 1 или 0.

Хорошо, это означает, что он может быть представлен 100-битным числом.Давайте округлим это до 128 бит (шестнадцати байтов).

Один из подходов состоит в том, чтобы использовать связанные списки - создать структуру наподобие (в C):

typedef struct sNode {
    unsigned char bits[16];
    struct sNode *next;
};

и поддерживать весь список B как отсортированный связанный список.

Производительность будет несколько ниже ^(a) , чем использование 100-битного числа в качестве индекса массива для действительно огромного (до невозможного).учитывая размер известного юниверса) массива.

Когда придет время вставить новый элемент в B, вставьте его в желаемое положение (перед тем, которое равно или больше).Если он был совершенно новым (вы узнаете это, если тот, который вы вставляете раньше, отличается), также добавьте его в A.

---

^(a) Хотя, вероятно, это не так уж и сложно - есть варианты, которые можно использовать для повышения скорости.

Одна из возможностей - использовать пропускаемые списки для более быстрого обхода во время поиска.Это еще один указатель, который ссылается не на следующий элемент, а на один 10 (или 100 или 1000) элементов.Таким образом, вы можете достаточно быстро приблизиться к нужному элементу и просто выполнить одношаговый поиск после этой точки.

В качестве альтернативы, поскольку вы говорите о битах, вы можете разделить B на (например,) 1024 под- B списков.Используйте первые 10 битов 100-битного значения, чтобы выяснить, какой суб B вам нужно использовать, и сохраните только следующие 90 бит.Одно это увеличило бы скорость поиска в среднем на 1000 (используйте больше начальных битов и больше суб B с, если вам нужно улучшить это).

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

Answer 4

Вам не нужно N сегментов, где N - количество всех возможных входов.A двоичное дерево просто подойдет.Это реализовано с помощью класса set в C ++.

vector<vector<vector<int> > > A; // vector of 10x10 matrices
// fill the matrices in A here

set<vector<vector<int> > > B(A.begin(), A.end()); // voila!
// now B contains all elements in A, but only once for duplicates

Answer 5

Конвертировать каждую матрицу в строку из 100 двоичных цифр.Теперь запустите его через утилиты Linux:

sort | uniq

Если вам действительно нужно сделать это в C ++, можно реализовать собственную сортировку слиянием, тогда часть uniq станет тривиальной.