.net string class альтернатива

Ответ 1

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

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

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

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

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

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 байт для байта [].

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

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

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 to startIndex и между startIndex + length to length) и создайте новый массив с 3 массивами (dataAtStart + NewData + EndData) и задайте длину массива соответствующей локальной переменной.

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

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

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

Ответ 2

EDIT: теперь у меня есть запись в блоге по этому вопросу, которая идет в более подробное описание.

Переход по вашим номерам:

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

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

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

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

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

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

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

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

EDIT: Я только подумал о другой проблеме. Числа, которые мы получили выше, на самом деле не правы... потому что класс строки является специальным. Он вводит свои данные непосредственно в объект - в отличие от любого другого типа данных, кроме массивов, размер экземпляра 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();

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

Ответ 3

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

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

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

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

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

Ну, есть класс UTF8Encoding

//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), вам все равно придется преобразовать ее в обычную строку unicode... если вы дал нам больше информации о том, что вы пытаетесь сделать, возможно, мы могли бы помочь вам придумать лучшее решение?

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

Ответ 8

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

Ответ 9

Может быть, хороший массив персонажей старой моды подойдет вашим потребностям.

Ответ 10

Все ли эти строки отличаются?

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