Задать вопрос
  • Не работает INSERT INTO, почему?

    mayton2019
    @mayton2019
    Возможно в консоли у тебя все строками и работает а в коде есть типизация и где-то целочисленное не кастуется например. Но я не люблю такие гадания.

    Нам нужно точно знать какая ошибка. Посмотри как тут
    https://www.w3schools.com/php/func_mysqli_error.asp
    PHP ловит ошибку и выдай ее на экран.
  • Как разогнать процессор AMD?

    mayton2019
    @mayton2019
    У него вполне себе норм процессор. И кино смотреть можно. У меня такой эффект
    часто бывал лет 15 назад когда я ставил еще тогда хреновые драйвера NVidia
    на всякие SuseLinux, Slack e.t.c. И OpenGL не включался и рендеринг плоской
    графики в VLC плеере шел с чудовищными лагами. Не лечилось это никак.
    Тогда только сумашедший красноглазик мог играть в игрухи на Linux. Все понимали
    что реально Windows была игровой платформой а Linux драйера для Radeon/NV
    делали только энтузиасты. И как делали чорт его знает. Может реверс-инжинерингом?

    И на windows такой эффект можно словить когда какая-нть Windows-2000 не осилила
    найти подходящий драйвер.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Еще одна оптимизация. Если есть предположение что будем отбивать 90% негативных реквестов на contains - то можно соединить хеш таблицу с фильтром Блума.

    Расчет размеров будет такой. Для 5 млн ключей https://hur.st/bloomfilter/?n=5000000&p=0.01&m=&k=

    размер биткарты будет 5 мегабайт и нужно 7 хеш-функций (на самом деле можно одну
    только к аргументу единичку прибавлять) и фактор ложно-позитивного срабатывания
    0.01. Вот такой фильтр будет дешевой проверкой чтоб отбивать реквесты от хешмапы.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Ну... популярность ключей это-ж краеугольный камень всего перформанс тюнинга. Это и для баз данных актуально. Для файловых систем. И для веб-приложений с Rest.

    И один великий сказал дескыть всего 2 проблемы у нас. Как обозвать переменную и как инвалидировать
    кеш. А все остальное - решаемо.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на contains

    Если ты дойдешь до практики реализации кешей. То там окажется что оперативная память неодинаково
    работает. Если делать тюнинг структур данных под L1/L2/L3 то может оказаться что такое зональное
    деление ключей на популярные и непопулярные очень полезно для кеша.

    Вот. Поэтому лучше остановись и сделай бенчмарк в сравнении с хешами STL, Google e.t.c.

    O(1) - это чистая теория. А практика может показать что твой теоретический хороший O(1) может быть хуже например логарифма но адаптированного к железу. Бегаешь по красно-черному дереву но ближе к CPU. А пробирования хещ-таблиц будут всегда промахами для железа.

    Вот мой десктоп дома (Ryzen-5) имеет на борту 8М кеша L3. И если я его прогрею полностью
    (положу туда одну зону из хеш-таблицы) то я почти гарантирую очень короткий отклик
    без вовлечения оперативной памяти.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Ну я вообще тестирую set. В нем только и будет contains. А get не имеет смысла.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Действительно, можно отсортировать данные по частоте заросов на них, скажем на 10% объектов приходится 90% запросов contains/get, тогда можно с обычным линейным пробированием эти 10% запихать первыми (так, чтобы distance от места вставки до реального места был не больше 1.05 скажем), а остальные 90% запихать потом. Тогда мат. ожидание кеш мисса будет близко к 1.

    Да и если использовать этот пирамидальный вариант таблиц то можно пускать в population ключи
    в порядке их частоты. Сначала - самые популярные. Они займут толстый слой пирамиды. А потом
    уже те кто пореже будут заселены на 2 и 3 и выше уровня. Но нам - пофиг. Они - редкие посетители.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.

    2023-07-28 20:06:28,511 : [INFO] - Start demo
    2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
    2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
    2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
    2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
    2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
    2023-07-28 20:06:29,419 : [INFO] - Finish


    Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
    их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
    таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
    1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
    я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
    даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Мне как базовику очень не нравится что кукушка постоянно что-то тасует в памяти. Было-бы более ясно если есть фаза генерации или популяции таблицы. И после этого мы ее фиксируем и больше ключи не вращаются.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Мда... От коллизий вообще не уйти. Может примем за допущение что 1 коллизия для 1 ключа это нормально?

    Но глубина пробирования будет в 1 шаг. После первой коллизии мы применяем ту-же хеш-функцию типа CRC или mur-mur но с другим seed.

    Если после 2 шага коллизия - то растягиваем таблицу.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    floppa322, функция mur-mur-hash. Линейное. Пока я фикшу баги.

    Но ты булки не расслабляй. Кодь дальше.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Короче я нашел свой старый исходник и сюда приложу а ты посмотри. Если какой-то API по Java ты не знаешь - то я могу подсказать.

    UPD: Нет. Херовенько он работает. Надо подфиксить.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    10-16n

    Тоесть ты хочешь сказать что вместо 5 млн слотов тебе надо будет 16 * 5 000 000 = 80_000_000 ?

    Восемдесят лямов?

    Ахахаха.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Нормально.

    Я 5 миллионов ключей записал в 5008333 слотов. Без коллизий за 2 итерации.
  • Как посчитать значение до прибавления к ней процента?

    mayton2019
    @mayton2019
    galliard, я написал достаточно для решения. Ты просто не мог поставить задачу в термиах алгебры.
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Отписал я вариант ответа. Чего тут еще придумывать. Ну ты подумай что двухуровневая таблица - это-ж фу-фу-фу.
    Ни один нормальный разработчик не захочет тащить в проект накладные расходы ни с того ни с сего 2х от нужного размера. И кукуха здесь не поможет и Робин гуд. Если уж ты такой перфекционист.
  • Как разогнать процессор AMD?

    mayton2019
    @mayton2019
    Как давно стоит эта операционка?

    Драйвер на видео как называется? Какая версия? Возможно ли обновить?
  • Seed для CRC32?

    mayton2019
    @mayton2019
    floppa322, почитай еще про метод Робин-Гуда. Возможно тебе пригодится.