О строковом стажировании и альтернативах

О строковом стажировании и альтернативах ⇐ C#

Ответить

1 сообщение • Страница 1 из 1

Anonymous

О строковом стажировании и альтернативах

Цитата

Сообщение Anonymous » 07 ноя 2024, 03:01

У меня есть большой файл, который по сути содержит такие данные:

Код: Выделить всё

Netherlands,Noord-holland,Amsterdam,FooStreet,1,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,2,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,3,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,4,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,5,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,1,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,2,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,3,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,4,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,1,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,2,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,3,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,1,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,2,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,3,...,...
...

Это файл размером в несколько гигабайт. У меня есть класс, который читает этот файл и предоставляет эти строки (записи) как IEnumerable. Этот MyObject имеет несколько свойств (

Код: Выделить всё

Country,Province,City, ...) etc.

As you can see there is a LOT of duplication of data. I want to keep exposing the underlying data as an IEnumerable. Однако какой-то другой класс может (и, вероятно, будет) создавать иерархическое представление/структуру этих данных, например:

Netherlands
Noord-holland
Amsterdam
FooStreet [1, 2, 3, 4, 5]
BarRoad [1, 2, 3, 4]
...
Amstelveen
BazDrive [1, 2, 3]
...
...
Zuid-holland
Rotterdam
LoremAve [1, 2, 3]
...
...
...
...

При чтении этого файла я делаю, по сути, следующее:

Код: Выделить всё

foreach (line in myfile) {
fields = line.split(",");
yield return new MyObject {
Country = fields[0],
Province = fields[1],
City = fields[2],
Street = fields[3],
//...other fields
};
}

Теперь, собственно, вопрос: я мог бы использовать string.Intern() для интернирования страны, провинции, Строки City и Street (это основные «злодеи», MyObject имеет несколько других свойств, не имеющих отношения к вопросу).

Код: Выделить всё

foreach (line in myfile) {
fields = line.split(",");
yield return new MyObject {
Country = string.Intern(fields[0]),
Province = string.Intern(fields[1]),
City = string.Intern(fields[2]),
Street = string.Intern(fields[3]),
//...other fields
};
}

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

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

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

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

Требования:

Мой класс «FileReader» должен продолжать предоставлять IEnumerable
Мой «FileReader» класс может делать что-то (например, string.Intern()) для оптимизации использования памяти
Класс MyObject не может измениться; Я не буду создавать класс City, класс Country и т. д. и предоставлять MyObject как свойства вместо простых строковых свойств
< li>Цель состоит в том, чтобы (более) эффективно использовать память за счет дедупликации большинства повторяющихся строк в Страна, Область, Город и т. д.; как это достигается (например, интернирование строк, внутренний хэш-набор/коллекция/структура чего-либо) не важно. Однако:
Я знаю, что могу поместить данные в базу данных или использовать другие решения в этом направлении; Меня не интересуют подобные решения.
Скорость имеет второстепенное значение; чем быстрее, тем лучше, конечно, но (незначительная) потеря производительности при чтении/переборе объектов не является проблемой.
Поскольку это длительный процесс (например: служба Windows работает 24/24/ 7/365), который иногда обрабатывает большую часть этих данных. Я хочу, чтобы данные были отправлены в сборщик мусора, когда я закончу с ними; Интернирование строк работает отлично, но в конечном итоге приведет к образованию огромного пула строк с большим количеством неиспользуемых данных.
Мне бы хотелось, чтобы любые решения были «простыми»; добавление 15 классов с помощью P/Invokes и встроенной сборки (преувеличено) не стоит затраченных усилий. Сопровождаемость кода занимает одно из первых мест в моем списке.

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

Например: я мог бы сделать что-то вроде этого:

Код: Выделить всё

public class StringInterningObject
{
private HashSet _items;

public StringInterningObject()
{
_items = new HashSet();
}

public string Add(string value)
{
if (_items.Add(value))
return value;  //New item added; return value since it wasn't in the HashSet
//MEH... this will quickly go O(n)
return _items.First(i => i.Equals(value)); //Find (and return) actual item from the HashSet and return it
}
}

Но с большим набором строк (которые нужно дедуплицировать) это быстро застопорится. Я мог бы взглянуть на справочный источник для HashSet или Dictionary или... и создать аналогичный класс, который возвращает не логическое значение для метода Add(), а фактическую строку, найденную во внутренних компонентах/ведре.< /p>

Лучшее, что мне удалось придумать на данный момент, это что-то вроде:

Код: Выделить всё

public class StringInterningObject
{
private ConcurrentDictionary _items;

public StringInterningObject()
{
_items = new ConcurrentDictionary();
}

public string Add(string value)
{
return _items.AddOrUpdate(value, value, (v, i) => i);
}
}

Что имеет «наказание» в виде ключа и значения, где меня на самом деле интересует только ключ. Однако всего несколько байт — небольшая цена. По совпадению, это также дает на 42% меньше использования памяти; тот же результат, что и при использовании string.Intern().

tolanj придумал System.Xml.NameTable:

Код: Выделить всё

public class StringInterningObject
{
private System.Xml.NameTable nt = new System.Xml.NameTable();

public string Add(string value)
{
return nt.Add(value);
}
}

(Я удалил блокировку и проверку string.Empty (последняя, поскольку NameTable уже делает это))

xanatos придумал CachingEqualityComparer:

Код: Выделить всё

public class StringInterningObject
{
private class CachingEqualityComparer : IEqualityComparer where T : class
{
public System.WeakReference X { get; private set; }
public System.WeakReference Y { get; private set; }

private readonly IEqualityComparer Comparer;

public CachingEqualityComparer()
{
Comparer = EqualityComparer.Default;
}

public CachingEqualityComparer(IEqualityComparer comparer)
{
Comparer = comparer;
}

public bool Equals(T x, T y)
{
bool result = Comparer.Equals(x, y);

if (result)
{
X = new System.WeakReference(x);
Y = new System.WeakReference(y);
}

return result;
}

public int GetHashCode(T obj)
{
return Comparer.GetHashCode(obj);
}

public T Other(T one)
{
if (object.ReferenceEquals(one, null))
{
return null;
}

object x = X.Target;
object y = Y.Target;

if (x != null && y != null)
{
if (object.ReferenceEquals(one, x))
{
return (T)y;
}
else if (object.ReferenceEquals(one, y))
{
return (T)x;
}
}

return one;
}
}

private CachingEqualityComparer _cmp;
private HashSet _hs;

public StringInterningObject()
{
_cmp = new CachingEqualityComparer();
_hs = new HashSet(_cmp);
}

public string Add(string item)
{
if (!_hs.Add(item))
item = _cmp.Other(item);
return item;
}
}

(Немного изменено, чтобы «подогнать» мой интерфейс «Add()»)

По запросу Хенка Холтермана :

Код: Выделить всё

public class StringInterningObject
{
private Dictionary _items;

public StringInterningObject()
{
_items = new Dictionary();
}

public string Add(string value)
{
string result;
if (!_items.TryGetValue(value, out result))
{
_items.Add(value, value);
return value;
}
return result;
}
}

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не столь уж реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не столь уж реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не столь уж реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не очень реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не очень реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не очень реальную) проблему. s> Думаю, теперь у меня достаточно вариантов

Вот несколько цифр, которые я получил в ходе простых, коротких предварительных тестов:

Не оптимизировано[/b]Память: ~ 4,5Гб
Время загрузки: ~52с

StringInterningObject (см. выше вариант ConcurrentDictionary)Память: ~2,6Гб
Время загрузки: ~49 сек.

string.Intern()Память: ~2,3Гб
Время загрузки: ~45с

System.Xml .NameTableПамять: ~2,3Гб
Время загрузки: ~41с

CachingEqualityComparerПамять: ~2,3Гб
Время загрузки: ~58 сек.

StringInterningObject (см. выше вариант (непараллельного) словаря) согласно запросу Хенка Холтермана:
Память: ~2, 3 ГБ
Время загрузки: ~39 с

Хотя цифры не очень точные, похоже, что многие выделения памяти для неоптимизированной версии на самом деле замедляются. вниз больше, чем при использовании string.Intern() или вышеуказанного StringInterningObject, что приводит к (немного) увеличению времени загрузки. Кроме того, string.Intern(), похоже, «выигрывает» у StringInterningObject, но не с большим отрывом;

Подробнее здесь: https://stackoverflow.com/questions/299 ... ternatives

1730937719

Anonymous

У меня есть большой файл, который по сути содержит такие данные:[b]
[code]Netherlands,Noord-holland,Amsterdam,FooStreet,1,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,2,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,3,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,4,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,5,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,1,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,2,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,3,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,4,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,1,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,2,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,3,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,1,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,2,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,3,...,...
...
[/code]

Это файл размером в несколько гигабайт. У меня есть класс, который читает этот файл и предоставляет эти строки (записи) как IEnumerable. Этот MyObject имеет несколько свойств ([code]Country,Province,City, ...) etc.

As you can see there is a LOT of duplication of data. I want to keep exposing the underlying data as an IEnumerable. Однако какой-то другой класс может (и, вероятно, будет) создавать иерархическое представление/структуру этих данных, например:

Netherlands
Noord-holland
Amsterdam
FooStreet [1, 2, 3, 4, 5]
BarRoad [1, 2, 3, 4]
...
Amstelveen
BazDrive [1, 2, 3]
...
...
Zuid-holland
Rotterdam
LoremAve [1, 2, 3]
...
...
...
...
[/code]

При чтении этого файла я делаю, по сути, следующее:

[code]foreach (line in myfile) {
fields = line.split(",");
yield return new MyObject {
Country = fields[0],
Province = fields[1],
City = fields[2],
Street = fields[3],
//...other fields
};
}
[/code]

Теперь, собственно, вопрос: я [b]мог бы[/b] использовать string.Intern() для интернирования страны, провинции, Строки City и Street (это основные «злодеи», MyObject имеет несколько других свойств, не имеющих отношения к вопросу).

[code]foreach (line in myfile) {
fields = line.split(",");
yield return new MyObject {
Country = string.Intern(fields[0]),
Province = string.Intern(fields[1]),
City = string.Intern(fields[2]),
Street = string.Intern(fields[3]),
//...other fields
};
}
[/code]

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

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

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

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

Требования:
[list]
[*]Мой класс «FileReader» должен продолжать предоставлять IEnumerable
[*]Мой «FileReader» класс может делать что-то (например, string.Intern()) для оптимизации использования памяти
[*]Класс MyObject не может измениться; Я не буду создавать класс City, класс Country и т. д. и предоставлять MyObject как свойства вместо простых строковых свойств
< li>Цель состоит в том, чтобы (более) эффективно использовать память за счет дедупликации большинства повторяющихся строк в Страна, Область, Город и т. д.; как это достигается (например, интернирование строк, внутренний хэш-набор/коллекция/структура чего-либо) не важно. Однако:
[*]Я знаю, что могу поместить данные в базу данных или использовать другие решения в этом направлении; Меня не интересуют подобные решения.
[*]Скорость имеет второстепенное значение; чем быстрее, тем лучше, конечно, но (незначительная) потеря производительности при чтении/переборе объектов не является проблемой.
[*]Поскольку это длительный процесс (например: служба Windows работает 24/24/ 7/365), который иногда обрабатывает большую часть этих данных. Я хочу, чтобы данные были отправлены в сборщик мусора, когда я закончу с ними; Интернирование строк работает отлично, но в конечном итоге приведет к образованию огромного пула строк с большим количеством неиспользуемых данных.
[*]Мне бы хотелось, чтобы любые решения были «простыми»; добавление 15 классов с помощью P/Invokes и встроенной сборки (преувеличено) не стоит затраченных усилий. Сопровождаемость кода занимает одно из первых мест в моем списке.
[/list]

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


Например: я мог бы сделать что-то вроде этого:

[code]public class StringInterningObject
{
private HashSet _items;

public StringInterningObject()
{
_items = new HashSet();
}

public string Add(string value)
{
if (_items.Add(value))
return value;  //New item added; return value since it wasn't in the HashSet
//MEH... this will quickly go O(n)
return _items.First(i => i.Equals(value)); //Find (and return) actual item from the HashSet and return it
}
}
[/code]

Но с большим набором строк (которые нужно дедуплицировать) это быстро застопорится. Я мог бы взглянуть на справочный источник для HashSet или Dictionary или... и создать аналогичный класс, который возвращает не логическое значение для метода Add(), а фактическую строку, найденную во внутренних компонентах/ведре.< /p>

Лучшее, что мне удалось придумать на данный момент, это что-то вроде:

[code]public class StringInterningObject
{
private ConcurrentDictionary _items;

public StringInterningObject()
{
_items = new ConcurrentDictionary();
}

public string Add(string value)
{
return _items.AddOrUpdate(value, value, (v, i) => i);
}
}
[/code]

Что имеет «наказание» в виде ключа и значения, где меня на самом деле интересует только ключ. Однако всего несколько байт — небольшая цена.  По совпадению, это также дает на 42% меньше использования памяти; тот же результат, что и при использовании string.Intern().

tolanj придумал System.Xml.NameTable:

[code]public class StringInterningObject
{
private System.Xml.NameTable nt = new System.Xml.NameTable();

public string Add(string value)
{
return nt.Add(value);
}
}
[/code]

(Я удалил блокировку и проверку string.Empty (последняя, поскольку NameTable уже делает это))

xanatos придумал CachingEqualityComparer:

[code]public class StringInterningObject
{
private class CachingEqualityComparer : IEqualityComparer where T : class
{
public System.WeakReference X { get; private set; }
public System.WeakReference Y { get; private set; }

private readonly IEqualityComparer Comparer;

public CachingEqualityComparer()
{
Comparer = EqualityComparer.Default;
}

public CachingEqualityComparer(IEqualityComparer comparer)
{
Comparer = comparer;
}

public bool Equals(T x, T y)
{
bool result = Comparer.Equals(x, y);

if (result)
{
X = new System.WeakReference(x);
Y = new System.WeakReference(y);
}

return result;
}

public int GetHashCode(T obj)
{
return Comparer.GetHashCode(obj);
}

public T Other(T one)
{
if (object.ReferenceEquals(one, null))
{
return null;
}

object x = X.Target;
object y = Y.Target;

if (x != null && y != null)
{
if (object.ReferenceEquals(one, x))
{
return (T)y;
}
else if (object.ReferenceEquals(one, y))
{
return (T)x;
}
}

return one;
}
}

private CachingEqualityComparer _cmp;
private HashSet _hs;

public StringInterningObject()
{
_cmp = new CachingEqualityComparer();
_hs = new HashSet(_cmp);
}

public string Add(string item)
{
if (!_hs.Add(item))
item = _cmp.Other(item);
return item;
}
}
[/code]

(Немного изменено, чтобы «подогнать» мой интерфейс «Add()»)

По запросу Хенка Холтермана :

[code]public class StringInterningObject
{
private Dictionary _items;

public StringInterningObject()
{
_items = new Dictionary();
}

public string Add(string value)
{
string result;
if (!_items.TryGetValue(value, out result))
{
_items.Add(value, value);
return value;
}
return result;
}
}
[/code]

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не столь уж реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не столь уж реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не столь уж реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не очень реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не очень реальную) проблему.

Мне просто интересно, есть ли более аккуратный/лучший/крутой способ «решить» мою (не очень реальную) проблему.  s> Думаю, теперь у меня достаточно вариантов 
[img]https://i.sstatic.net/VxodK.gif[/img]



Вот несколько цифр, которые я получил в ходе простых, коротких предварительных тестов:

[img]https://i.sstatic.net/sHJiD.png[/img]

Не оптимизировано[/b][b]Память: ~ 4,5Гб
Время загрузки: ~52с

[img]https://i.sstatic.net/DVAjG.png [/img]

StringInterningObject[/b] (см. выше вариант ConcurrentDictionary)[b]Память: ~2,6Гб
Время загрузки: ~49 сек.

[img]https://i.sstatic.net/l1fya.png[/img]

string.Intern()[/b][b]Память: ~2,3Гб
Время загрузки: ~45с

[img]https://i.sstatic.net/BBD1d.png[/img]

System.Xml .NameTable[/b][b]Память: ~2,3Гб
Время загрузки: ~41с

[img] https://i.sstatic.net/5YTf2.png[/img]

CachingEqualityComparer[/b][b]Память: ~2,3Гб
Время загрузки: ~58 сек.

[img]https://i.sstatic.net/mZdJ4.png[/img]

StringInterningObject[/b] (см. выше вариант (непараллельного) словаря) согласно запросу Хенка Холтермана:
Память: ~2, 3 ГБ
Время загрузки: ~39 с

Хотя цифры не очень точные, похоже, что многие выделения памяти для неоптимизированной версии на самом деле замедляются. вниз больше, чем при использовании string.Intern() или вышеуказанного StringInterningObject, что приводит к (немного) увеличению времени загрузки. Кроме того, string.Intern(), похоже, «выигрывает» у StringInterningObject, но не с большим отрывом; 

Подробнее здесь: [url]https://stackoverflow.com/questions/29984839/on-string-interning-and-alternatives[/url]