map::insert

Тема в разделе "LANGS.C", создана пользователем cupuyc, 5 авг 2011.

  1. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Они и в случае size_t -> size_t будут быстрее, если хэш-функция подобрана правильно. Если данные случайные и распределены равномерно, то это вообще просто - обычный остаток от деления подойдет, и значения функции будут распределены равномерно. Если данные неслучайные, то нужно подбирать функцию по тестовым наборам. Если данные целиком зависят от пользователя, то хэш-таблицу применять в этом случае нельзя, так как это потенциальный DoS. Кстати, насколько я знаю, hash_map использует для разрешения коллизий не списки, а те же красно-черные деревья, так что даже в худшем случае она не будет медленнее.
     
  2. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Atlantic
    На неизвестных данных это не так просто сделать. Пойдут коллизии, тогда запоёте по другому.
     
  3. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Booster
    Ну так я написал про неизвестные данные. И про потенциальный DoS тоже, когда все данные попадают в одну ячейку таблицы.

    Поиск: O(1+x) для хэш-таблиц, O(log(N)) для деревьев.
    Вставка: O(1) для хэш-таблиц, O(log(N)) для деревьев.
    Удаление: O(1+x) для хэш-таблиц, O(log(N)) для деревьев.
    x - коэффициент заполнения, обычно держится в интервале [0.5,1]. Где тут деревья быстрее? Не вижу.

    P.S. В худшем случае поиск и удаление - O(N) для хэш-таблиц со списками, и не говорите, что я этого не знал.
     
  4. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Пора тему перетаскивать в WASM.A&O :)
     
  5. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    Блин, Вы считать умеете?

    Если таблица размером ~64кб (K = 16384 элементов), то средняя длина списка получается (0x80000000 / 16384) * N / 16384 = 8 * N. если в мапе ~ 1000 элементов, то сложность будет ~8000 операций. + какой оверхед по памяти? для дерева какая будет сложность?
     
  6. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Не понял? Откуда такая формула? Средняя длина списка равна N / K. Если N ~ K, то средняя длина будет равна 1.

    N - это число элементов, а не размер диапазона size_t.

    По-моему, тут как раз не я не разбираюсь в алгоритмах, Лол :)
     
  7. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    +1. В данном случае коллизии неизбежны.
     
  8. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    Atlantic
    Это в случае когда нет коллизий. Вы забыли, учесть высокую вероятность коллизий.
     
  9. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    У вас такое представление, будто коллизии - абсолютное зло. Это не так. Для хэш-таблиц коллизии - абсолютно нормальное дело, и если не доходит до вырожденных случаев, то они никак не влияют на скорость.

    Кто сказал, что она обязательно высокая? Ничего, что она зависит от хэш-функции, размера таблицы и самих входных данных и обычно является наоборот низкой?

    Средняя длина списка в любом случае всегда в точности равна N / K. Почему - советую вспомнить определение слова "средняя" и подумать самому.
     
  10. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    Atlantic, Вы, наверное, не понимаете. Мы обсуждаем конкретную практическую задачу (где ключ изменяется от 0x00000000 до 0x7FFFFFFF) о целесообразности применения хеш таблиц.

    В данной задаче она высокая. Вы это понимаете?
     
  11. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    В какой задаче? Какой набор из чисел size_t вставляется в таблицу? Случайный и равномерно распределенный или специально подобранный под хэш-функцию, чтобы убить скорость в ноль? Так какая у нас задача?

    Ну раз "в данной задаче она высокая", тот тут по умолчанию данные специально подбираются под хэш-функцию, чтобы все тормозило. Тогда и говорить не о чем.
     
  12. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    Я не понимаю, почему так туго доходит. Ключ - случайное число в диапазоне от 0x00000000 до 0x7FFFFFFF.
     
  13. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Распределение равномерное? В таком случае со всей ответственностью заявляю - вероятность коллизий является максимально возможно низкой, даже если хэш-функция - простейшая F(X) = X % K. Потому что значения хэш-функции также будут случайны и распределены равномерно. Надеюсь, это не надо доказывать. Должно быть и так понятно.

    P.S. Но могу и доказать :)
     
  14. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Hash table в целом более эффективна по скорости, но у таблицы есть дополнительный расход на эту самую таблицу, плюс конечно не всегда она более эффективна. Опять таки возьмём случай с 7FFFFFFF ключей и таблицу к примеру размером 0xFFFF и если ключей у нас будет по максимуму, значит делим 7FFFFFFF на 0xffff, получаем что 0x8000 элементов будут в одном индексе таблицы, это явно уступает гарантированным log(0xFFFFFFFF).
     
  15. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Пусть F(X) = X % K, где K > 1. Нужно посчитать вероятность того, что для двух случайных равномерно распределенных X1 и X2 из диапазона 0...2^31-1 будет выполняться равенство F(X1)=F(X2).

    1) Пусть F(X1) = Y.
    2) Вероятность того, что F(X2) = Y будет по определению равна числу всех X, таких, что F(X) = Y, деленному на размер диапазона (2^31).
    3) F(X) = Y при всех X = Y + K * M, 0 <= M < (2^31 - Y) / K.
    4) То есть таких X будет не больше ceil((2^31 - Y) / K).
    5) Отсюда вероятность того, что F(X2) = Y равна ceil((2^31 - Y) / K) / 2^31
    6) По цепочке неравенств можно получить оценку этой вероятности сверху: ceil((2^31 - Y) / K) / 2^31 <= ceil(2^31 / K) / 2^31 <= (2^31 / K + 1) / 2^31 = 1 / K + 2^-31

    Итак, вероятность коллизии двух значений функции будет не больше чем (1 / K + 2^-31). Что лишь чуть-чуть больше, чем идеально низкая для такой функции вероятность (1 / K). Посчитать среднее число коллизий в таблице размера K, содержащей N элементов можно по известным формулам из теории вероятностей.

    P.S. Холиварить на эту больше не собираюсь, переубеждать кого-то в чем-то нет смысла. Если не умеете видеть те случаи, когда хэш-таблицы применимы, а когда - нет, это только ваши проблемы.

    P.P.S. Конкретно для этой задачи (отображение size_t -> size_t) я бы использовал std::map. Если бы скорость не устраивала - использовал бы хэш-таблицу. Если же нужна упорядоченность или данные неслучайные, а std::map слишком медленный - написал бы реализацию структуры данных trie: _http://habrahabr.ru/blogs/algorithm/111874/
     
  16. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Во-первых, для 7FFFFFFF ключей и таблица будет не FFFF размером, а больше, во-вторых, где взять столько памяти, в третьих, для деревьев потребуется еще больше памяти, потому что два указателя на узел.
     
  17. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Atlantic
    А если неизвестно сколько будет ключей? Положим у кого-то их будет мало, у кого-то много. Сколько вы зарезервируете для этого случая?
    Я клоню к тому, что просто нет универсальных структур и алгоритмов. Нельзя тупо выбросить одно и использовать другое.
     
  18. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Стандартный прием - рост хэш-таблицы, если коэффициент заполнения достигнет установленного предела. Только асимптотика будет уже рассчитываться как амортизированная стоимость всех операций. Но лучше конечно использовать таблицы там, где заранее известен максимальный объем данных.
     
  19. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Atlantic
    Стандартная ситуация, оптимизируем по скорости, проигрываем по размеру и наоборот.
     
  20. srm

    srm New Member

    Публикаций:
    0
    Регистрация:
    14 июн 2011
    Сообщения:
    189
    По другому нужно считать. Нужно считать вероятность встречи коллизии после вставки n+1-го элемента мапу. Из этого рассчитывать среднюю длину списка (исключая пустые списки).