Блог

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

Кто-нибудь, пожалуйста, подскажите, какую структуру данных мне использовать? Или что-нибудь еще, что может улучшить использование памяти с помощью моей хэш-таблицы?

Программа написана на C .

Вот как выглядит мой код: инициализация хэш-таблицы:

 class Link
{ 
  public:
         double iData; 
         Link* pNext; 
         Link(double it) : iData(it) 
         { }
         void displayLink()
         { cout << iData << " "; }
}; 

class List
 {
  private:
          Link* pFirst; 
  public:
         List() 
         { pFirst = NULL; }
         void insert(double key) 
         {

           if(pFirst==NULL)
           pFirst = new Link(key);
       else
          {
        Link* pLink = new Link(key);
        pLink->pNext = pFirst;
        pFirst = pLink;
       }

         }     

 }; 
class HashTable
{      
  public:
         int arraySize;
         vector<List*> hashArray; 

         HashTable(int size) 
         {

            hashArray.resize(size); 
            for(int j=0; j<size; j  ) 
            hashArray[j] = new List; 
         }
};
  

основной фрагмент:

 int t_sample = 1000;
 for(int i=0; i < k; i  )                                // initialize random position
{
        x[i] = (cal_rand() * dom_sizex);   //dom_sizex = 20e-10  cal_rand() generates rand no between 0 and 1
        y[i] = (cal_rand() * dom_sizey);    //dom_sizey = 10e-10
}

for(int t=0; t < t_sample; t  )
{
 int size;
 size = cell_nox * cell_noy; //size of hash table cell_nox = 212, cell_noy = 424

 HashTable theHashTable(size); //make table
 int hashValue = 0;

 for(int n=0; n<k; n  )   // k = 10*212*424
 {
  int m = x[n] /cell_width;     //cell_width = 4.7e-8
  int l = y[n] / cell_width;

   hashValue = (kx*l) m;
   theHashTable.hashArray[hashValue]->insert(n); 

  }

   -------
   -------
 }
  

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

• либо std::unordered_multimap<int, double>
• или std::unordered_map<int, std::vector<double>>

(Примечание: если у вас нет C 11, они доступны в Boost)

Ваш основной цикл становится (используя второй вариант):

 typedef std::unordered_map<int, std::vector<double>> HashTable;

for(int t = 0; t < t_sample;   t)
{
    size_t const size = cell_nox * cell_noy;
       // size of hash table cell_nox = 212, cell_noy = 424

    HashTable theHashTable;
    theHashTable.reserve(size);

    for (int n = 0; n < k;   n)   // k = 10*212*424
    {
        int m = x[n] / cell_width;     //cell_width = 4.7e-8
        int l = y[n] / cell_width;

        int const cellId = (kx*l) m;

        theHashTable[cellId].push_back(n);
    }
}
  

Это не приведет к утечке памяти (надежно), хотя, конечно, у вас могут быть другие утечки, и, таким образом, даст вам надежную базовую линию. Это также, вероятно, быстрее, чем ваш подход, с более удобным интерфейсом и т.д…

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

ОС должна решать те же проблемы со страницами памяти, может быть, стоит посмотреть, как это делается? Прежде всего, давайте предположим, что все страницы находятся на диске. Страница — это фрагмент памяти фиксированного размера. Для вашего варианта использования, допустим, это массив ваших записей. Поскольку объем оперативной памяти ограничен, ОС поддерживает сопоставление между номером страницы и ее местоположением в оперативной памяти.

Итак, допустим, на ваших страницах 1000 записей, и вы хотите получить доступ к записи 2024, вы должны запросить у ОС страницу 2 и прочитать запись 24 с этой страницы. Таким образом, ваша карта имеет размер всего 1/1000.

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

Это очень упрощенное описание того, что происходит, и я не удивлюсь, если кто-то набросится на меня за такое описание.

Дело в том,:

Что это значит для вас?

Во-первых, ваши данные превышают объем оперативной памяти — вы не обойдетесь без записи на диск, если не хотите сначала попробовать сжатие. Во-вторых, ваши цепочки могут работать как страницы, если хотите, но мне интересно, будет ли лучше работать просто подкачка вашего хэш-кода. Я имею в виду, что используйте верхние биты в качестве номера страницы, а младшие биты — в качестве смещения на странице. По-прежнему важно избегать столкновений, так как вы хотите загрузить как можно меньше страниц. Вы все равно можете объединить свои страницы в цепочку и в итоге получить карту гораздо меньшего размера. Вторая важная часть — решить, какие страницы поменять местами, чтобы освободить место для новых страниц. LRU должен работать нормально. Если вы можете лучше предсказать, какие страницы вам (не) понадобятся, тем лучше для вас. В-третьих, вам нужны заполнители для ваших страниц, чтобы указать, находятся ли они в памяти или на диске.

Надеюсь, это поможет.