Альтернатива строкового класса .net

Question

Поскольку я планирую приложение, которое будет хранить МНОГИЕ своих данных в памяти, я хотел бы иметь какой-то «компактный» класс строк, по крайней мере, один, который будет содержать строку в формате, не превышающем нулевую завершенную версию ASCIIстрока.

Знаете ли вы о какой-либо реализации такого строкового класса - он должен иметь некоторые служебные функции, такие как исходный класс строки.

РЕДАКТИРОВАТЬ:

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

В идеале, это будет источник, совместимый с System.String, поэтому базовые действия поиска и замены оптимизируют использование памяти приложения.

NUMBERS:

Я мог бы иметь запись по 100 тыс. Для каждой записи, содержащей до 10 строк длиной от 30 до 60 символов.Итак:

100000x10x60 = 60000000 = 57 мега символов.Почему бы не использовать 60 мегабаранов для оперативной памяти вместо 120 мегабайтов для оперативной памяти?Операции будут быстрее, все будет труднее.

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

Answer 1

РЕДАКТИРОВАТЬ: у меня теперь есть сообщение в блоге на эту тему , в котором более подробно.

---

По вашим номерам:

У меня может быть запись по 100 тыс. Для каждой записи, содержащей до 10 строк длиной от 30 до 60 символов.

Давайте начнем с добавления служебных данных объекта - строка занимает около 20 байт (IIRC - возможно, больше на 64-битном CLR) плюс фактических данных из-за неизбежных накладных расходов объекта и длина. Давайте снова посчитаем:

Использование строки: 1 миллион объектов при 20 + 120 байтах = 140 МБ

Использование нового класса: 1 миллион объектов размером 20 + 60 байт = 80 МБ

Разница, конечно, в 60 МБ, но пропорционально меньше, чем вы ожидали. Вы экономите только 42% пространства вместо 50%.

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

Ради 60МБ я бы не стал беспокоиться. Это небольшая разница в наши дни - подумайте, сколько еще клиентов вы получите, сделав эту небольшую экономию, чтобы компенсировать значительную дополнительную стоимость работы с двумя различными типами строк.

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

РЕДАКТИРОВАТЬ: Я только что подумал о другой проблеме. Числа, которые мы получили выше, на самом деле не верны ... потому что класс строки особенный. Он встраивает свои данные непосредственно в объект - в отличие от любого другого типа данных, кроме массивов, размер экземпляра string не является фиксированным; он варьируется в зависимости от данных в нем.

Написав свой собственный класс AsciiString, вы не сможете этого сделать - вам нужно будет встроить ссылку на массив внутри класса:

public class AsciiString
{
    private readonly byte[] data;
}

Это означает, что вам понадобятся дополнительные 4 или 8 байтов для ссылки (32 или 64-битный CLR) и дополнительные издержки объекта массива (16 байтов, IIRC) на строку.

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

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

Другой возможностью было бы создать такую ​​структуру:

struct AsciiString
{
    private readonly byte[] data;
    ...
}

Это фактически даст вам сильный набор текста снова, но вам нужно подумать о таких вещах, как:

AsciiString x = new AsciiString();

, который в итоге будет иметь нулевую ссылку data. Вы можете эффективно обработать это, как если бы x было нулевым значением, но это было бы довольно не-идиоматично.

Answer 2

У меня на самом деле была похожая проблема, но с другими параметрами проблемы.Мое приложение имеет дело с двумя типами строк - относительно короткими, длина которых составляет 60-100 символов, и более длинными, длиной 100-1000 байт (в среднем около 300).

Мой вариант использования также должен поддерживать текст в Unicode, но относительноНебольшой процент строк на самом деле имеет неанглийские символы.

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

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

Базовая реализация выглядит примерно так:

byte[] _myProperty;

public String MyProperty
{

   get 
   { 
        if (_myProperty== null)
            return null;

        return Encoding.UTF8.GetString(value);
   }

   set
   { 
        _myProperty = Encoding.UTF8.GetBytes(value);

   }

}

Производительность снизилась для этих конверсий, даже если поиск и сортировка были относительно небольшими (было около 10-15%).

Некоторое время это было нормально, но я хотел еще больше сократить накладные расходы.Следующим шагом было создание объединенного массива для всех строк в данном объекте (объект будет содержать либо 1 короткую и 1 длинную строку, либо 4 коротких и 1 длинную строку).таким образом, для каждого объекта будет один байт [], и для каждой из строк потребуется только 1 байт (сохраните их длины, которые всегда <256).даже если ваши строки могут быть длиннее 256, а int все еще дешевле, чем 12-16-байтовые служебные данные для байта []. </p>

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

эта реализация выглядит примерно так:

byte _property1;
byte _property2;
byte _proeprty3;

private byte[] _data; 

byte[] data;
//i actually used an Enum to indicate which property, but i am sure you get the idea
private int GetStartIndex(int propertyIndex)
{  

   int result = 0;
   switch(propertyIndex)
   {
       //the fallthrough is on purpose 
       case 2:
          result+=property2;
       case 1:
          result+=property1;

   }

   return result;
}

private int GetLength(int propertyIndex)
{
   switch (propertyIndex)
   {
     case 0:
        return _property1;
     case 1: 
        return _property2;
     case 2:
        return _property3;
   }
    return -1;
}

private String GetString(int propertyIndex)
{
   int startIndex = GetStartIndex(propertyIndex);
   int length = GetLength(propertyIndex);
   byte[] result = new byte[length];
   Array.Copy(data,startIndex,result,0,length);

   return Encoding.UTF8.GetString(result);

}

, поэтому метод получения выглядит следующим образом:

public String Property1
{
   get{ return GetString(0);}
}

Сеттер в том же духе - скопируйте исходные данные в два массива (между 0 start до startIndex и между startIndex + length to length) и создайте новый массив с 3 массивами (dataAtStart+ NewData + EndData) и установите длину массива для соответствующей локальной переменной.

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

Степень сжатия для моего варианта использования (по сравнению с более эффективным подходом byte [] store)50% (!).Я использовал размер страницы около 10 строк на страницу и сгруппировал похожие свойства (которые, как правило, имеют схожие данные).Это добавило дополнительные издержки в 10-20% (поверх прохода кодирования / декодирования, который все еще требуется).Механизм подкачки кэширует страницы, к которым недавно обращались, до настраиваемого размера.Даже без сжатия эта реализация позволяет вам установить фиксированный коэффициент накладных расходов для каждой страницы.Основным недостатком моей текущей реализации кеша страниц является то, что при сжатии он не является поточно-ориентированным (без него такой проблемы нет).

Если вы заинтересованы в механизме сжатого подкачки, сообщите мне(Я искал оправдание, чтобы открыть его).

Answer 3

Альтернативные структуры данных

Я хотел бы предложить, чтобы, учитывая ваше желание также осуществлять поиск по сохраненным «строковым» значениям, вы должны рассмотреть вопрос о том, является ли структура Trie, такая как Patricia Trie, или, для еще лучшей амортизации памяти,Направленный ациклический словесный граф (именуемый аффилированностью как DAWG) будет работать лучше.

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

Их можно рассматривать как обобщения (встроенного) де-дупликации, предоставленного в .net (и java и многих других управляемых языках) интернирования строк.

Если вы специально хотите сохранить порядок строк каким-либо лексикографическим образом (поэтому вам нужно учитывать только один символ или кодовую точку за раз), то, скорее всего, Patricia Trie будет предпочтительным вариантом, реализуяупорядочить поверх DAWG было бы проблематично.

Альтернативные, более эзотерические решения могут работать, если у вас есть определенный домен строк, включая:

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

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

Строки фиксированной длины.

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

Answer 4

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

Но если у вас есть массив каждого слова или общая фраза, вы сохраняете индекс как массив.за каждое слово

Затем вы платите 4 байта за каждое слово, но если каждое слово в среднем составляет 3,6 символа, то вы в среднем экономите 3,2 байта для каждого слова, поскольку вы платите 2-байтовый / буквенный штраф один раз /word.

Но, чтобы выполнить поиск или сортировку, вы сильно пострадаете от необходимости перестроить строку хотя бы на короткое время.

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

Answer 5

Сколько дубликатов вы ожидаете?Если в вашем массиве много дубликатов, вы можете рассмотреть возможность реализации строкового кэша (обертка вокруг Dictionary<string, string>), который кэширует экземпляры определенных строк и возвращает ссылку на этот экземпляр для каждой дублирующейся строки, которую вы кэшируете в нем.1002 *

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

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

Answer 6

Ну, есть кодировка UTF8 класс

//Example from MSDN
using System;
using System.Text;

public class Example
{
   public static void Main()
   {
      Encoding enc = new UTF8Encoding(true, true);
      string value = "\u00C4 \uD802\u0033 \u00AE"; 

      try
      {
         byte[] bytes= enc.GetBytes(value);
         foreach (var byt in bytes)
            Console.Write("{0:X2} ", byt);
         Console.WriteLine();

         string value2 = enc.GetString(bytes);
         Console.WriteLine(value2);
      }
      catch (EncoderFallbackException e)
      {
         //Encoding error
      }                     
   }
}

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

Или, если вы действительно нуждаетесь в низкоуровневых байтовых массивах без интернационализируемых строк с нулевым символом в конце, вам лучше написать это на C ++.

Answer 7

Вы можете сохранить накладные расходы для каждого объекта, имея большой байт [], в котором хранятся символы, а затем int-offset в этот массив в качестве вашей «строки».

Answer 8

Я думаю, что ключом к этому является то, что каждая запись имеет много строковых полей …

Сохраняя все строковые поля для каждой записи в одном массиве символов, а затем используя поле int со смещением, вы можете значительно уменьшить количество объектов. (Каждый объект имеет накладные расходы около 2 слов, даже до того, как вы поместите в него какие-либо данные.)

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

(Теперь, если многие строковые поля никогда не меняют свои значения, все становится намного проще)

Answer 9

Отличны ли все эти строки?

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

Answer 10

Может быть, старый добрый массив символов моды подойдет вам.