Как компрессировать упорядоченный массив уникальных натуральных чисел огр. диапазона? Веб приложение сравнивает попарно наборы целых положительных чисел
Каждый набор не содержит внутри себя повторов, любое из чисел не больше 210 млн. (28 бит).
В наборе их может быть от 1 до 5 млн
Сравнивая наборы A и B надо получить наборы «уникальные для A», «уникальные для B» и «общее ядро». В частности, просто отвечать на вопросы «Есть ли в наборе S число N?
Реализация, увы, на php и пока на shared hosting. Наскоро реализовал, нагрузив хостинговый MySQL: под каждый сет временная таблица с единственной колонкой-индексом. В большинстве случае таблицы превышают размер, который помещается в engine=Memory, и на дисковых таблицах это совсем небыстро, но работает
Как эффективно держать такой набор, чтобы сравнение двух сетов выполнялось быстро, занимя минимальный footprint по памяти
Пришло в голову записать каждый набор битовой маской длиной в 2^28 бит (32Mb). Из 210 млн бит всего 5 млн единиц, остальные 0: их можно записывать числом нулей подряд, например. Очень похоже на велосипед. Подскажите всем, кроме меня, известный алгоритм, эффективный для компрессии бинарных данных в частном случае «много нулей подряд»?
Про Huffman coding читал, похоже, он будет неэффективен для поиска каждого из 5 млн. чисел второго сета внутри первого.
Как компрессировать упорядоченный массив уникальных натуральных чисел огр. диапазона? Веб приложение сравнивает попарно наборы целых положительных чисел
Каждый набор не содержит внутри себя повторов, любое из чисел не больше 210 млн. (28 бит).
В наборе их может быть от 1 до 5 млн
Сравнивая наборы A и B надо получить наборы «уникальные для A», «уникальные для B» и «общее ядро». В частности, просто отвечать на вопросы «Есть ли в наборе S число N?
Реализация, увы, на php и пока на shared hosting. Наскоро реализовал, нагрузив хостинговый MySQL: под каждый сет временная таблица с единственной колонкой-индексом. В большинстве случае таблицы превышают размер, который помещается в engine=Memory, и на дисковых таблицах это совсем небыстро, но работает
Как эффективно держать такой набор, чтобы сравнение двух сетов выполнялось быстро, занимя минимальный footprint по памяти
Пришло в голову записать каждый набор битовой маской длиной в 2^28 бит (32Mb). Из 210 млн бит всего 5 млн единиц, остальные 0: их можно записывать числом нулей подряд, например. Очень похоже на велосипед. Подскажите всем, кроме меня, известный алгоритм, эффективный для компрессии бинарных данных в частном случае «много нулей подряд»?
Про Huffman coding читал, похоже, он будет неэффективен для поиска каждого из 5 млн. чисел второго сета внутри первого.
Каждый набор не содержит внутри себя повторов, любое из чисел не больше 210 млн. (28 бит).
В наборе их может быть от 1 до 5 млн
Сравнивая наборы A и B надо получить наборы «уникальные для A», «уникальные для B» и «общее ядро». В частности, просто отвечать на вопросы «Есть ли в наборе S число N?
Реализация, увы, на php и пока на shared hosting. Наскоро реализовал, нагрузив хостинговый MySQL: под каждый сет временная таблица с единственной колонкой-индексом. В большинстве случае таблицы превышают размер, который помещается в engine=Memory, и на дисковых таблицах это совсем небыстро, но работает
Как эффективно держать такой набор, чтобы сравнение двух сетов выполнялось быстро, занимя минимальный footprint по памяти
Пришло в голову записать каждый набор битовой маской длиной в 2^28 бит (32Mb). Из 210 млн бит всего 5 млн единиц, остальные 0: их можно записывать числом нулей подряд, например. Очень похоже на велосипед. Подскажите всем, кроме меня, известный алгоритм, эффективный для компрессии бинарных данных в частном случае «много нулей подряд»?
Про Huffman coding читал, похоже, он будет неэффективен для поиска каждого из 5 млн. чисел второго сета внутри первого.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Один из способов эффективной компрессии таких наборов может быть использование битовых массивов или битовых множеств.
Вы можете представить каждый набор как битовый массив, где каждый элемент соответствует натуральному числу из диапазона. Например, если у вас есть набор {1, 3, 5}, то битовый массив будет выглядеть как {1, 0, 1, 0, 1, 0, ...}.
При сравнении двух наборов вы можете использовать операции побитового И, ИЛИ и отрицания для быстрого определения уникальных элементов и общего ядра.
Такой подход позволит вам значительно уменьшить объем памяти, занимаемый каждым набором, и ускорить операции сравнения.
Кроме того, вы можете оптимизировать поиск конкретного числа в наборе, используя эффективные алгоритмы работы с битами, такие как бинарный поиск или использование битовых масок.
Надеюсь, это поможет вам улучшить производительность вашего веб-приложения.