Сохранить память при хранении повторяющихся строк в векторе?

Question

Я использую C ++, и это STL. У меня большой (более 100 МБ) текстовый файл. В этом файле просто много слов (строк, разделенных пробелами), таких как:

sdfi sidf ifids sidf assd fdfd fdfd ddd ddd

Мне нужно поместить каждое из этих «слов» в вектор:

vector<string> allWordsInFile;

Итак, для каждого слова, которое я читаю из файла, я делаю:

allWordsInFile.push_back(word);

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

Может кто-нибудь предложить другой способ подойти к этому?

Answer 1

boost :: flyweight выглядит здесь полезным.

На самом деле учебный пример показывает, boost::flyweight<std::string> используется для сжатия дубликатов имен в базе данных.

Answer 2

Amm, то, что вы на самом деле хотите сделать, называется сжатием.

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

Природа кодирования по Хаффману позволяет вам получить доступ к символу в любом месте, где вы хотите (ни один символ не является префиксом другого символа), проблема в том, что время доступа будет O (n) Есть некоторая оптимизация, которая может сократить время доступа, но только на постоянный коэффициент, ничто не может помешать ему быть O (n) и все же сохранить небольшое использование памяти. Если вы хотите услышать об оптимизации, которую можно сделать, оставьте мне комментарий.

Недостатки:

1. после того, как вы создали закодированные слова, доступ в O (n), вы должны линейно сканировать символы, пока не доберетесь до соответствующей позиции.
2. Реализация этой идеи совсем не тривиальна и отнимает у вас много времени.

Редактировать : Одна вещь, о которой я не задумывался при написании поста, вы должны держать таблицу поиска. Так что это может работать только если у вас есть лот из повторяющихся слов.

Код Хаффмана: http://en.wikipedia.org/wiki/Huffman_coding

Answer 3

Одним из способов может быть сохранение одного вектора, содержащего только уникальные строки. Затем список «слов» - это просто вектор целых чисел, являющийся индексом в массиве уникальных строк. Это сэкономит память за счет того, что чтение файла будет медленнее, поскольку для каждого нового слова вам придется выполнять какое-то линейное сканирование в массиве unique. Затем вы можете использовать карту в качестве индекса в массиве уникальных строк - если новое слово не найдено в наборе, то вы знаете, что добавить слово в конце списка уникальных слов. Эй, если подумать, вам даже не нужен вектор, поскольку карта служит этой цели:

typedef map<string, int> UniqueIndex;
UniqueIndex uniqueIndex;

typedef vector<int> WordsInFile;
WordsInFile wordsInFile;

for (each word in the file)
{
  UniqueIndex::const_iterator it=uniqueIndex.find(word);
  int index; // where in the "uniqueIndex" we can find this word
  if (it==uniqueIndex.end())
  {
    // not found yet
    index=uniqueIndex.size();
    uniqueIndex[word]=index;
  }
  else
    index=it.second;
  wordsInFile.push_back(index);
}

Answer 4

Если у вас мало слов, вы можете сохранить слова во внешнем массиве и сохранить соответствующие индексы в вашем векторе слов. В зависимости от количества уникальных слов у вас может быть только 1 (для макс. 256 слов) или 2 (макс. 65536 слов) байтов на слово.

Если вам нужна скорость, вы можете использовать std :: map для поиска индекса строки за время log (n) (вместо итерации по внешнему массиву)

например. для макс. 65536 уникальных слов

vector<short> words
map<string,short> index
vector<string> uniqueWords
cindex = 0
for all words
    read the word
    if index[word] does not exist
        index[word] = cindex++
        uniqueWords.push_back(word)
    words.push_back(index[word]);

Чтобы получить оригинальные слова, просто найдите их в uniqueWords.

Answer 5

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

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

Answer 6

Поскольку ваши строки обычно имеют размер около 4 байтов, простое создание другого уровня косвенности не поможет, поскольку размер указателя составляет 4 байта (на x86 или хуже, на 8 байтах на x64). И размер индекса, основанного на int, также будет 4 байта.

Загрузка по частям:

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

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

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

Этот метод не пытается исключить хранение дублирующихся строк, но он ограничивает объем ОЗУ, который вам нужно использовать, только размером вашего индекса. Вы можете настроить «каждые 10 слов» выше на «каждые Х слов», чтобы уменьшить потребление памяти. Таким образом, ваш размер, используемый в RAM, будет только (num_words_in_file / X) * sizeof (int), который НАМНОГО меньше размера хранения всего файла в RAM, даже если вы сохранили каждую уникальную строку только один раз.

Доступ к каждому слову без лишних пробелов:

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

Answer 7

После указания на boost::flyweight в другом ответе, Я хотел поближе взглянуть на относительную эффективность контейнеров из струн, маховиков и «ядерного варианта» объединения четырех символов с указателем (класс "sillystring" в коде ниже).

Примечания к коду:

• Работает на 32-битном Debian / squeeze с g ++ 4.3.3 и boost 1.38.0
• Использует std::deque вместо std::vector, потому что вектор Поведение удвоения размера (куски c.f deques) дает (возможно) вводящее в заблуждение впечатление неэффективности, если тестовый случай недавно удвоился.
• "Sillystring" использует младший бит указателя на отличить сценарий использования указателя от локальных символов дело. Это должно работать, если ваш malloc не выделяет на нечетных байтовых границах (в этом случае код будет выброшен) (конечно, не видел это в моей системе; YMMV). Прежде чем кто-либо почувствует необходимость указать на это, да, я делаю рассмотреть этот ужасный опасный хакерский код, а не вариант, который будет выбран легко.

Результаты варьируются в зависимости от распределения длин слов, но для распределения "(2D6 + 1) / 2" (так достигло пика в 4, но с длины от 1 до 6), эффективность (определяется как соотношение между фактическим потреблением памяти и фактическим количеством символы, которые должны быть сохранены):

• 12,4% deque<string>
• 20,9% deque<flyweight<string> >
• 43,7% deque<sillystring>

Если все ваши слова были 4 символа (изменится на const int length=4; в генераторе слов), что является идеальным случаем для глупой строки, то вы получите:

• 14,2% deque<string>
• 77,8% deque<flyweight<string> >
• 97,0% deque<sillystring>

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

Вот код:

// Compile with "g++ -O3 -o fly fly.cpp -lpthread"
// run "./fly 0 && ./fly 1 && ./fly 2" 

#include <boost/flyweight.hpp>
#include <boost/format.hpp>
#include <boost/random.hpp>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

#include <sys/types.h>
#include <unistd.h>

#define THROW(X,MSG) throw X(boost::str(boost::format("%1%: %2%") % __PRETTY_FUNCTION__ % MSG))

struct random_word_generator
{
  random_word_generator(uint seed)
    :_rng(seed),
     _length_dist(1,6),
     _letter_dist('a','z'),
     _random_length(_rng,_length_dist),
     _random_letter(_rng,_letter_dist)
  {}
  std::string operator()()
  {
    std::string r;
    const int length=(_random_length()+_random_length()+1)/2;
    for (int i=0;i<length;i++) r+=static_cast<char>(_random_letter());
    return r;
  }
private:
  boost::mt19937 _rng;
  boost::uniform_int<> _length_dist;
  boost::uniform_int<> _letter_dist;
  boost::variate_generator<boost::mt19937&,boost::uniform_int<> > 
    _random_length;
  boost::variate_generator<boost::mt19937&,boost::uniform_int<> > 
    _random_letter;
};

struct collector
{
  collector(){}
  virtual ~collector(){}

  virtual void insert(const std::string&)
    =0;
  virtual void dump(const std::string&) const
    =0;
};

struct string_collector
  : public std::deque<std::string>, 
    public collector
{
  void insert(const std::string& s)
  {
    push_back(s);
  }
  void dump(const std::string& f) const
  {
    std::ofstream out(f.c_str(),std::ios::out);
    for (std::deque<std::string>::const_iterator it=begin();it!=end();it++)
      out << *it << std::endl;
  }
};

struct flyweight_collector 
  : public std::deque<boost::flyweight<std::string> >, 
    public collector
{
  void insert(const std::string& s)
  {
    push_back(boost::flyweight<std::string>(s));
  }
  void dump(const std::string& f) const
  {
    std::ofstream out(f.c_str(),std::ios::out);
    for (std::deque<boost::flyweight<std::string> >::const_iterator it=begin();
         it!=end();
         it++
         )
      out << *it << std::endl;
  }
};

struct sillystring
{
  sillystring()
  {
    _rep.bits=0;
  }
  sillystring(const std::string& s)
  {
    _rep.bits=0;
    assign(s);
  }
  sillystring(const sillystring& s)
  {
    _rep.bits=0;
    assign(s.str());
  }
  ~sillystring()
  {
    if (is_ptr()) delete [] ptr();
  }
  sillystring& operator=(const sillystring& s)
  {
    assign(s.str());
  }
  void assign(const std::string& s)
  {
    if (is_ptr()) delete [] ptr();
    if (s.size()>4)
      {
        char*const p=new char[s.size()+1];
        if (reinterpret_cast<unsigned int>(p)&0x00000001)
          THROW(std::logic_error,"unexpected odd-byte address returned from new");
        _rep.ptr.value=(reinterpret_cast<unsigned int>(p)>>1);
        _rep.ptr.is_ptr=1;
        strcpy(ptr(),s.c_str());
      }
    else
      {
        _rep.txt.is_ptr=0;
        _rep.txt.c0=(s.size()>0 ? validate(s[0]) : 0);
        _rep.txt.c1=(s.size()>1 ? validate(s[1]) : 0);
        _rep.txt.c2=(s.size()>2 ? validate(s[2]) : 0);
        _rep.txt.c3=(s.size()>3 ? validate(s[3]) : 0);
      }
  }
  std::string str() const
  {
    if (is_ptr())
      {
        return std::string(ptr());
      }
    else
      {
        std::string r;
        if (_rep.txt.c0) r+=_rep.txt.c0;
        if (_rep.txt.c1) r+=_rep.txt.c1;
        if (_rep.txt.c2) r+=_rep.txt.c2;
        if (_rep.txt.c3) r+=_rep.txt.c3;
        return r;
      }
  }
private:
  bool is_ptr() const
  {
    return _rep.ptr.is_ptr;
  }
  char* ptr()
  {
    if (!is_ptr())
      THROW(std::logic_error,"unexpected attempt to use pointer");
    return reinterpret_cast<char*>(_rep.ptr.value<<1);
  }
  const char* ptr() const
  {
    if (!is_ptr()) 
      THROW(std::logic_error,"unexpected attempt to use pointer");
    return reinterpret_cast<const char*>(_rep.ptr.value<<1);
  }
  static char validate(char c)
  {
    if (c&0x80)
      THROW(std::range_error,"can only deal with 7-bit characters");
    return c;
  }
  union
  {
    struct
    {
      unsigned int is_ptr:1;
      unsigned int value:31;
    } ptr;
    struct
    {
      unsigned int is_ptr:1;
      unsigned int c0:7;
      unsigned int :1;
      unsigned int c1:7;
      unsigned int :1;
      unsigned int c2:7;      
      unsigned int :1;
      unsigned int c3:7;      
    } txt;
    unsigned int bits;
  } _rep;
};

struct sillystring_collector 
  : public std::deque<sillystring>, 
    public collector
{
  void insert(const std::string& s)
  {
    push_back(sillystring(s));
  }
  void dump(const std::string& f) const
  {
    std::ofstream out(f.c_str(),std::ios::out);
    for (std::deque<sillystring>::const_iterator it=begin();
         it!=end();
         it++
         )
      out << it->str() << std::endl;
  }
};

// getrusage is useless for this; Debian doesn't fill out memory related fields
// /proc/<PID>/statm is obscure/undocumented
size_t memsize()
{
  const pid_t pid=getpid();
  std::ostringstream cmd;
  cmd << "awk '($1==\"VmData:\"){print $2,$3;}' /proc/" << pid << "/status";
  FILE*const f=popen(cmd.str().c_str(),"r");
  if (!f)
    THROW(std::runtime_error,"popen failed");
  int amount;
  char units[4];
  if (fscanf(f,"%d %3s",&amount,&units[0])!=2)
    THROW(std::runtime_error,"fscanf failed");
  if (pclose(f)!=0)
    THROW(std::runtime_error,"pclose failed");
  if (units[0]!='k' || units[1]!='B')
    THROW(std::runtime_error,"unexpected input");
  return static_cast<size_t>(amount)*static_cast<size_t>(1<<10);
}

int main(int argc,char** argv)
{
  if (sizeof(void*)!=4)
    THROW(std::logic_error,"64-bit not supported");
  if (sizeof(sillystring)!=4) 
    THROW(std::logic_error,"Compiler didn't produce expected result");

  if (argc!=2)
    THROW(std::runtime_error,"Expected single command-line argument");

  random_word_generator w(23);

  std::auto_ptr<collector> c;
  switch (argv[1][0])
    {
    case '0':
      std::cout << "Testing container of strings\n";
      c=std::auto_ptr<collector>(new string_collector);
      break;
    case '1':
      std::cout << "Testing container of flyweights\n";
      c=std::auto_ptr<collector>(new flyweight_collector);
      break;
    case '2':
      std::cout << "Testing container of sillystrings\n";
      c=std::auto_ptr<collector>(new sillystring_collector);
      break;
    default:
      THROW(std::runtime_error,"Unexpected command-line argument");
    }

  const size_t mem0=memsize();

  size_t textsize=0;
  size_t filelength=0;
  while (filelength<(100<<20))
    {
      const std::string s=w();
      textsize+=s.size();
      filelength+=(s.size()+1);
      c->insert(s);
    }

  const size_t mem1=memsize();
  const ptrdiff_t memused=mem1-mem0;

  std::cout 
    << "Memory increased by " << memused/static_cast<float>(1<<20)
    << " megabytes for " << textsize/static_cast<float>(1<<20)
    << " megabytes text; efficiency " << (100.0*textsize)/memused << "%"
    << std::endl;

  // Enable to verify all containers stored the same thing:
  //c->dump(std::string(argv[1])+".txt");

  return 0;
}

Answer 8

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

   int count = 0;
   Map<String, List<Integer>> words = new HashMap<String, List<Integer>>();

Тогда это выглядит примерно так (псевдокод типа Java):

   for (word : yourFile) {
      List<Integer> positions = words.get(word);
      if (values == null) {
         positions = new ArrayList<Integer>();
      }
      positions.add(++count);
      words.put(word, positions);
   }

Answer 9

Прежде всего, мы должны знать, на что похожи строки:

если «большинство строк - 4 буквы», а размер файла составляет 100 МБ, тогда

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

b) Может быть, есть способ сжать с 8-разрядного ascii (при условии, что это действительно ASCII) (8X4 = 32) до, возможно, 20 бит (5x4), используя 5 бит на букву, и с некоторыми причудливыми работающими битами уменьшить размер вектора. Пожалуйста, запустите образец данных и посмотрите, сколько букв действительно есть в файлах, возможно, некоторые группы букв настолько многочисленны, что имеет смысл назначить им особое значение (из 32 опций в 8-битной последовательности). На самом деле, если я прав, если большинство слов можно преобразовать в 20-битное представление, то все, что нужно, это массив с 3 МБ для хранения всех слов и их количества слов - и для обработки> 4 символов отдельно (предполагается, что 3 байта достаточно для подсчета слов, что должно быть, может быть, достаточно 2 байта: может сделать его динамическим для использования в общей сложности 2 МБ)

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

d) если вы действительно хотите минимизировать количество оперативной памяти, возможно, вы хотите использовать свой диск: отсортируйте слова (вы можете использовать диск, если у вас недостаточно оперативной памяти), и создайте временный файл со словами один за другим , что бы сделать для последовательного доступа. Затем вы можете создать одноразовое древовидное представление слов с листьями, содержащими относительный адрес к словам в файле для произвольного доступа, и «сериализовать» его на диск. В конце концов, так как большинство слов имеют длину 4 символа, с 5 прыжками вы получите положение любой буквы в файле без использования оперативной памяти, так сказать. Вы также можете кэшировать в оперативной памяти первые 2 или 3 слоя дерева, которые будут легкими в оперативном режиме, чтобы уменьшить количество переходов до 2 или 3 прыжков для слов из 4 символов. Затем вы можете использовать небольшую оперативную память для кеширования наиболее часто используемых слов и делать все возможное, чтобы ускорить доступ.

уже довольно поздно, надеюсь, у меня есть смысл ...

оплаченный Спасибо за комментарии, ребята

Answer 10

Я думаю, что использование таких вещей спасет память

struct WordInfo
{
    std::string m_word;
    std::vector<unsigned int> m_positions;
};

typedef std::vector<WordInfo> WordVector;

First find whether the word exists in WordVector

If no,
    create WordInfo object and push back into WordVector
else
    get the iterator for the existing WordInfo
    Update the m_positions with the position of the current string