Интересно, почему в классе HashSet<T> (.NET 3.5) не выставили наружу свойство Capacity, чтобы можно было заранее аллоцировать нужный размер контейнера при работе с большим числом элементов?
Есть подозрение, что есть какая-то серьёзная техническая причина, почему этого не сделали.
Может, кто-нибудь в курсе?

Здравствуйте, andy1618, Вы писали:

A>Интересно, почему в классе HashSet<T> (.NET 3.5) не выставили наружу свойство Capacity, чтобы можно было заранее аллоцировать нужный размер контейнера при работе с большим числом элементов?
A>Есть подозрение, что есть какая-то серьёзная техническая причина, почему этого не сделали.
A>Может, кто-нибудь в курсе?

Use source, Luke

    /// The capacity is always prime; so during resizing, the capacity is chosen as the next prime
    /// greater than double the last capacity. 
    ///
    /// The underlying data structures are lazily initialized. Because of the observation that,
    /// in practice, hashtables tend to contain only a few elements, the initial capacity is
    /// set very small (3 elements) unless the ctor with a collection is used.

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, andy1618, Вы писали:

A>>Интересно, почему в классе HashSet<T> (.NET 3.5) не выставили наружу свойство Capacity, чтобы можно было заранее аллоцировать нужный размер контейнера при работе с большим числом элементов?
A>>Есть подозрение, что есть какая-то серьёзная техническая причина, почему этого не сделали.
A>>Может, кто-нибудь в курсе?

_FR>Use source, Luke
_FR>

_FR>

_FR>    /// The capacity is always prime; so during resizing, the capacity is chosen as the next prime
_FR>    /// greater than double the last capacity. 
_FR>    ///
_FR>    /// The underlying data structures are lazily initialized. Because of the observation that,
_FR>    /// in practice, hashtables tend to contain only a few elements, the initial capacity is
_FR>    /// set very small (3 elements) unless the ctor with a collection is used. 
_FR>

А как это отвечает на поставленый вопрос? Тот же Dictionary ничем принцыпиально от HashSet-а по внутреннему устройству не отличается, но тем не менее, у Dictionary есть Capacity.

Здравствуйте, Lloyd, Вы писали:

L>Здравствуйте, _FRED_, Вы писали:

_FR>>Здравствуйте, andy1618, Вы писали:

A>>>Интересно, почему в классе HashSet<T> (.NET 3.5) не выставили наружу свойство Capacity, чтобы можно было заранее аллоцировать нужный размер контейнера при работе с большим числом элементов?
A>>>Есть подозрение, что есть какая-то серьёзная техническая причина, почему этого не сделали.
A>>>Может, кто-нибудь в курсе?

_FR>>Use source, Luke
_FR>>

_FR>>

_FR>>    /// The capacity is always prime; so during resizing, the capacity is chosen as the next prime
_FR>>    /// greater than double the last capacity. 
_FR>>    ///
_FR>>    /// The underlying data structures are lazily initialized. Because of the observation that,
_FR>>    /// in practice, hashtables tend to contain only a few elements, the initial capacity is
_FR>>    /// set very small (3 elements) unless the ctor with a collection is used. 
_FR>>

L>А как это отвечает на поставленый вопрос?

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

То есть юзер задаст 128, а свойство на слудеющий get вернёт 131 — это нормально выглядит?

Здравствуйте, Пельмешко, Вы писали:

П>То есть юзер задаст 128, а свойство на слудеющий get вернёт 131 — это нормально выглядит?
Учитывая скорость перехеширование — нормально. А так никакого рычага не присутствует.(ну за исключением промежуточного хранения в коллекции, что также дает нагрузку на память).

Здравствуйте, Lloyd, Вы писали:

L>А как это отвечает на поставленый вопрос? Тот же Dictionary ничем принцыпиально от HashSet-а по внутреннему устройству не отличается, но тем не менее, у Dictionary есть Capacity.

Я так думаю, что ключевыми являются слова

//The capacity is always prime

Здравствуйте, Пельмешко, Вы писали:

A>>>>Интересно, почему в классе HashSet<T> (.NET 3.5) не выставили наружу свойство Capacity, чтобы можно было заранее аллоцировать нужный размер контейнера при работе с большим числом элементов?
A>>>>Есть подозрение, что есть какая-то серьёзная техническая причина, почему этого не сделали.
A>>>>Может, кто-нибудь в курсе?
_FR>>>Use source, Luke
L>>А как это отвечает на поставленый вопрос?

П>Видимо дело в выделенном.
П>Всё равно требуемую пользователем ёмкость получить не удастся, всегда надо будет простое число больше задаваемой ёмкости искать.
П>То есть юзер задаст 128, а свойство на слудеющий get вернёт 131 — это нормально выглядит?

Нормально, учитывая что в Dictionary нет свойства, возвращающего Capacity

Здравствуйте, Пельмешко, Вы писали:

L>>А как это отвечает на поставленый вопрос?

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

The capacity of a Dictionary<TKey, TValue> is the number of elements that can be added to the Dictionary<TKey, TValue> before resizing is necessary.

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

П>То есть юзер задаст 128, а свойство на слудеющий get вернёт 131 — это нормально выглядит?

Кто вернет? Нет такого свойства.

Здравствуйте, Lloyd, Вы писали:

П>>То есть юзер задаст 128, а свойство на слудеющий get вернёт 131 — это нормально выглядит?

L>Кто вернет? Нет такого свойства.

Попутал, my bad

Здравствуйте, Пельмешко, Вы писали:

L>>Кто вернет? Нет такого свойства.

П>Попутал, my bad

Кстати, я тоже был уверен, что такое свойство есть.

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Lloyd, Вы писали:

L>>А как это отвечает на поставленый вопрос? Тот же Dictionary ничем принцыпиально от HashSet-а по внутреннему устройству не отличается, но тем не менее, у Dictionary есть Capacity.

_FR>Я так думаю, что ключевыми являются слова
_FR>

_FR>

_FR>//The capacity is always prime
_FR>

Тем не менее, остаётся непонятным, что мешало сделать метод Reserve и read-only свойство Capacity, по аналогии, с C++-ными контейнерами. Тем более, что это лучше согласуется с FDG.

Здравствуйте, Аноним, Вы писали:

L>>>А как это отвечает на поставленый вопрос? Тот же Dictionary ничем принцыпиально от HashSet-а по внутреннему устройству не отличается, но тем не менее, у Dictionary есть Capacity.
_FR>>Я так думаю, что ключевыми являются слова

_FR>>//The capacity is always prime

А>Тем не менее, остаётся непонятным, что мешало сделать метод Reserve

Во-первых, операция Reverse для неупорядоченного множества имеет не много смысла. Я для упорядоченного сета такая операция как раз есть.

А>и read-only свойство Capacity,

А какой в нём прок?

А>по аналогии, с C++-ными контейнерами.

ИМХО, аналогии тут уж совсем не уместны.

А>Тем более, что это лучше согласуется с FDG.

Что "это": Reverse, Capacity или "аналогии, с C++-ными контейнерами"?

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Аноним, Вы писали:

L>>>>А как это отвечает на поставленый вопрос? Тот же Dictionary ничем принцыпиально от HashSet-а по внутреннему устройству не отличается, но тем не менее, у Dictionary есть Capacity.
_FR>>>Я так думаю, что ключевыми являются слова
_FR>

_FR>

_FR>>>//The capacity is always prime
_FR>

А>>Тем не менее, остаётся непонятным, что мешало сделать метод Reserve

_FR>Во-первых, операция Reverse для неупорядоченного множества имеет не много смысла. Я для упорядоченного сета такая операция как раз есть.

А вот операция Reserve, вполне имеет смысл, прочти слово внимательней.

А>>и read-only свойство Capacity,

_FR>А какой в нём прок?

такой-же, что и сейчас.

А>>по аналогии, с C++-ными контейнерами.

_FR>ИМХО, аналогии тут уж совсем не уместны.

Почему нет?

А>>Тем более, что это лучше согласуется с FDG.

_FR>Что "это": Reverse, Capacity или "аналогии, с C++-ными контейнерами"?

Использование метода вместо сеттера для потенциально долгой операции по перемещению данных коллекции в кусок памяти большего размера.

Здравствуйте, Аноним, Вы писали:

А>>>Тем не менее, остаётся непонятным, что мешало сделать метод Reserve
_FR>>Во-первых, операция Reverse для неупорядоченного множества имеет не много смысла. Я для упорядоченного сета такая операция как раз есть.
А>А вот операция Reserve, вполне имеет смысл, прочти слово внимательней.

О, пардон

А>>>и read-only свойство Capacity,
_FR>>А какой в нём прок?
А>такой-же, что и сейчас.

И где такое свойство сейчас есть? Только в List<>, в котором нет никакой логики — это просто удобная обёртка над массивом и который, если верить FDG не следует выносить "наружу", в открытый интерфейс классов\методов.

В более менее коллекциях со "смыслом" такого свойства нет. И я могу уверенно предположить почему: потому что с коллекциями в подавляющем большенстве случаев удобно работать через интерфейс, а не через конкретный класс. Добавление же Capacity в интерфейс кажется очень перегруженным — различные реализации (в List<> и HashSet<>) могут по-разному на него реагировать.

А>>>по аналогии, с C++-ными контейнерами.
_FR>>ИМХО, аналогии тут уж совсем не уместны.
А>Почему нет?

Потому что контейнеры С++ спроектированны с расчётом на С++, в частности на полиморфизм, который не требует явной реализации некоторого интерфейса, ибо С++ позволяет во время компиляции создавать код обобщённых алгоритмов. В шарпе это не пройдёт.

А>>>Тем более, что это лучше согласуется с FDG.
_FR>>Что "это": Reverse, Capacity или "аналогии, с C++-ными контейнерами"?
А>Использование метода вместо сеттера для потенциально долгой операции по перемещению данных коллекции в кусок памяти большего размера.

ИМХО, поскольку "реально долгой" операция будет не часто (посчитайте, сколько копирований произойдёт при создании пустого HashSet<> и заполнении его, допустим, до ста тыщ элементов), то изменяемое свойство кажется более подходящим.

Но вот с точки зрения того, что некоторые структуры данных (Dictionary, HashSet) предъявляют особые требования к capacity (capacity is always prime) то метод мог бы быть более подходящим для изменения capacity.

Здравствуйте, Аноним, Вы писали:

_FR>>Во-первых, операция Reverse для неупорядоченного множества имеет не много смысла. Я для упорядоченного сета такая операция как раз есть.
А>А вот операция Reserve, вполне имеет смысл, прочти слово внимательней.
А>>>и read-only свойство Capacity,
_FR>>А какой в нём прок?
А>такой-же, что и сейчас.

А>>>по аналогии, с C++-ными контейнерами.
_FR>>ИМХО, аналогии тут уж совсем не уместны.
А>Почему нет?

Кстати, reserve в stl есть только у вектора (как и Capacity у List<>). Так какую именно аналогию вы имели в виду?

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Аноним, Вы писали:

_FR>>>Во-первых, операция Reverse для неупорядоченного множества имеет не много смысла. Я для упорядоченного сета такая операция как раз есть.
А>>А вот операция Reserve, вполне имеет смысл, прочти слово внимательней.
А>>>>и read-only свойство Capacity,
_FR>>>А какой в нём прок?
А>>такой-же, что и сейчас.

А>>>>по аналогии, с C++-ными контейнерами.
_FR>>>ИМХО, аналогии тут уж совсем не уместны.
А>>Почему нет?

_FR>Кстати, reserve в stl есть только у вектора (как и Capacity у List<>). Так какую именно аналогию вы имели в виду?

Если говорить про стандартную библиотеку текущего стандарта, то, да, эта операция есть только у вектора и строки, но она может и не иметь смысла для, возможных реализаций list'a или map'а. Добавленные в tr1 hash_map/hash_set этой операции тоже не имеют, но уже, скорее, по недосмотру. В новом стандарте (C++0x) reserve был добавлен и для них.

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Аноним, Вы писали:

А>>>>и read-only свойство Capacity,
_FR>>>А какой в нём прок?
А>>такой-же, что и сейчас.

_FR>И где такое свойство сейчас есть? Только в List<>, в котором нет никакой логики — это просто удобная обёртка над массивом и который, если верить FDG не следует выносить "наружу", в открытый интерфейс классов\методов.

ещё в ArrayList, но, я пока не понимаю при чём тут количество классов с этим свойством и его наличие/отсутствие в интерфейсах. Всё, что я хотел сказать, это, то, что, на мой взгляд, для HashSet'а можно было бы сделать свойство Capacity, с геттером работающим также как для List<>/ArrayList и методом Reserve вместо сеттера. Для единообразия, лучше было бы сделать тоже самое и в List<>/ArrayList.

_FR>В более менее коллекциях со "смыслом" такого свойства нет. И я могу уверенно предположить почему: потому что с коллекциями в подавляющем большенстве случаев удобно работать через интерфейс, а не через конкретный класс. Добавление же Capacity в интерфейс кажется очень перегруженным — различные реализации (в List<> и HashSet<>) могут по-разному на него реагировать.

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

А>>>>по аналогии, с C++-ными контейнерами.
_FR>>>ИМХО, аналогии тут уж совсем не уместны.
А>>Почему нет?

_FR>Потому что контейнеры С++ спроектированны с расчётом на С++, в частности на полиморфизм, который не требует явной реализации некоторого интерфейса, ибо С++ позволяет во время компиляции создавать код обобщённых алгоритмов. В шарпе это не пройдёт.

А при чём тут вобще полиморфизм? Мы обсуждаем операции для конкретных контейнеров.

А>>>>Тем более, что это лучше согласуется с FDG.
_FR>>>Что "это": Reverse, Capacity или "аналогии, с C++-ными контейнерами"?
А>>Использование метода вместо сеттера для потенциально долгой операции по перемещению данных коллекции в кусок памяти большего размера.

_FR>ИМХО, поскольку "реально долгой" операция будет не часто (посчитайте, сколько копирований произойдёт при создании пустого HashSet<> и заполнении его, допустим, до ста тыщ элементов), то изменяемое свойство кажется более подходящим.

Ну это примерно как возвращение массива из геттера, это ведь тоже не рекомендуют делать из-за "долгого" копирования. Ну и для HashSet'а (если бы такой функционал был для него реализован) поведение метода Reserve было бы более понятным чем сеттера Capacity.

_FR>Но вот с точки зрения того, что некоторые структуры данных (Dictionary, HashSet) предъявляют особые требования к capacity (capacity is always prime) то метод мог бы быть более подходящим для изменения capacity.

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

Реальная причина как всегда одна:

because it was never specified, designed, implemented, tested and shipped.

Здравствуйте, _FRED_, Вы писали:

_FR>Use source, Luke
_FR>

_FR>

_FR>    /// The capacity is always prime; so during resizing, the capacity is chosen as the next prime
_FR>    /// greater than double the last capacity. 
_FR>    ///
_FR>    /// The underlying data structures are lazily initialized. Because of the observation that,
_FR>    /// in practice, hashtables tend to contain only a few elements, the initial capacity is
_FR>    /// set very small (3 elements) unless the ctor with a collection is used. 
_FR>

Очень интересно! Осталось только понять, почему в Dictionary управление ёмкостью было вынесено в конструктор,
а в более свежем HashSet, при том же самом алгоритме — это убрали.

Посмотрел сейчас код HashHelpers (из конструктора Dictionary он вызывается так: int prime = HashHelpers.GetPrime(capacity):

static HashHelpers()
{
    primes = new int[] { 
        3, 7, 11, 0x11, 0x17, 0x1d, 0x25, 0x2f, 0x3b, 0x47, 0x59, 0x6b, 0x83, 0xa3, 0xc5, 0xef, 
        0x125, 0x161, 0x1af, 0x209, 0x277, 0x2f9, 0x397, 0x44f, 0x52f, 0x63d, 0x78b, 0x91d, 0xaf1, 0xd2b, 0xfd1, 0x12fd, 
        0x16cf, 0x1b65, 0x20e3, 0x2777, 0x2f6f, 0x38ff, 0x446f, 0x521f, 0x628d, 0x7655, 0x8e01, 0xaa6b, 0xcc89, 0xf583, 0x126a7, 0x1619b, 
        0x1a857, 0x1fd3b, 0x26315, 0x2dd67, 0x3701b, 0x42023, 0x4f361, 0x5f0ed, 0x72125, 0x88e31, 0xa443b, 0xc51eb, 0xec8c1, 0x11bdbf, 0x154a3f, 0x198c4f, 
        0x1ea867, 0x24ca19, 0x2c25c1, 0x34fa1b, 0x3f928f, 0x4c4987, 0x5b8b6f, 0x6dda89
     };
}


[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
internal static int GetPrime(int min)
{
    if (min < 0)
    {
        throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
    }
    for (int i = 0; i < primes.Length; i++)
    {
        int num2 = primes[i];
        if (num2 >= min)
        {
            return num2;
        }
    }
    for (int j = min | 1; j < 0x7fffffff; j += 2)    
    {
        if (IsPrime(j))
        {
            return j;
        }
    }
    return min;
}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
internal static bool IsPrime(int candidate)
{
    if ((candidate & 1) == 0)
    {
        return (candidate == 2);
    }
    int num = (int) Math.Sqrt((double) candidate);
    for (int i = 3; i <= num; i += 2)
    {
        if ((candidate % i) == 0)
        {
            return false;
        }
    }
    return true;
}

Видим, что сперва делается попытка подобрать простое число из таблички. Но если это не удаётся (затребованная Capacity превышает 7-8 млн. элементов), то начинается цикл (выделен жирным) перебора по нечётным в поиске следующего простого числа, а с учётом тупого устройства функции IsPrime (хоть бы табличку первых 1000 простых сделали!), можно напороться на очень существенное время!

Так что, по-видимому, Майкрософты решили избавиться от этой проблемы плавающего времени конструктора радикально, убрав Capacity вообще. Мда.

Здравствуйте, _FRED_, Вы писали:

_FR>

/// The capacity is always prime;

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

Здравствуйте, lost_guadelenn, Вы писали:

_FR>>

/// The capacity is always prime;

_>Я извиняюсь, если вопрос кому-то покажется глупым, но зачем это было сделано?

Зачем нужны именно простые числа?