Просто неохота писать свой велосипед.

Данные могут так сложиться, что элементы лягут строго по нечётным числам 1, 3, 5, 7, 9, и т.д. Умное перечисление тут не поможет.

Да и не понтяно что такое «значения» в количестве 100 млн. Это целые числа 32 бита, 64 бита? Если нет, то имеется ли отображение множества «значений» на целые числа, меньшие некоторого заранее известного числа N?

задача 1 курса по программированию,

Пока что это целые числа int32.

Данные могут так сложиться, что элементы лягут строго по нечётным числам 1, 3, 5, 7, 9,

Очень маловероятно. Причем наихудший вариант будет только при половине проверенных данных. Далее объем перечисления должен снижаться. Для перечисления 1,3,5,7 при добавлении 4 и 6 оно должно преобразоваться в 1, 3-7.

А какая разница, 32 или 64 бита?

Общая концепция простая, никто и не спорит. Только вот как лучше хранить перечисление? Линейный список, вектор, деревья? Как оптимизировать перестройку перечисления, если, например, добавляемый элемент объединяет два диапазона в один? (т.е., если в [0.100 и 102..200] добавить 101, то оно преобразуется в [0..200])?

>>Для перечисления 1,3,5,7 при добавлении 4 и 6 оно должно преобразоваться в 1, 3-7.

Чудень, курни-ка теорию информации, это же совсем азы, которые должны быть прошиты аппаратно.

По-твоему, 1011111 длиннее, чем задать три трехбитных числа: 001011111?? И это без учета особого кода для дефиса.

www.linux.org.ru/jump-message.jsp?msgid=6441331&cid=6441467

К тому же, я ж небуду хранить перечисления как строку и парсить её, зачем мне дефис? Эта структура вполне послужит диапазоном.

struct Foo {
    quint32 min;
    quint32 max;
}

Для любителей кликабельных ссылок

http://www.linux.org.ru/jump-message.jsp?msgid=6441331&cid=6441467

http://www.linux.org.ru/jump-message.jsp?msgid=6441331&cid=6441498

Если не важна скорость, то можно разделить диапазон на куски по 1-10000,10001-20000 и т.д. и сжимать каждый кусок RARом :) При поступлении числа, например, 12345 разжать кусок 100001-20000 и проверить, записать значение. После чего сжать обратно

Если не важна скорость, то можно разделить диапазон на куски по 1-10000,10001-20000 и т.д. и записывать их в файл на диске. При поступлении числа, например, 12345 прочитать файл 100001-20000 и проверить, записать значение. После чего записать обратно

Если не важна скорость, то можно разделить диапазон на куски по 1-10000,10001-20000 и т.д. и записывать их в файл RAR на диске. При поступлении числа, например, 12345 прочитать файл 100001-20000, разжать RAR и проверить, записать значение. После чего записать обратно на диск и сжать RARом :)

I LOL'D

глянь xsc.de ; там есть библиотека С диапазонных вычислений для научных нужд и специфичный Паскаль построенный на ней. Может чего пригодится по теме хранения и обработки чисел в заданных диапазонах.

Если ложноположительные срабатывания не проблема, то можешь посмотреть в сторону фильтра Блума (Bloom filter или Bloom map)

Если упростить условие задачи, то тебе нужно сжать 12 мегабайт случайных данных?

Если известны вероятности прохождения проверки для каждого элемента и если большинство элементов проверку обычно проходят (или наоборот не проходят), то назначения номеров-чисел этим элементам можно делать по сортировке этих вероятностей. Тогда вполне может подойти предложенный способ сжатия информации, так как будут образовываться большие группы чисел с одинаковыми результатом проверки и будет исключена ситуация проходения проверки для элементов с номерами типа 1,3,5,7,9,...

Короче нужны данные о характере проверок для элементов. Если они абсолютно случайны, то и сжимать нечего.

Если Вас волнует скорость проверки, то работайте с массивом. Все умные перечисления будут проигрывать, поскольку код значительно сложнее, много условий и т.д. 10^8 значений это всего лишь 12Мб как уже выше писали, это может влезть в кэш и тогда все хорошо.

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

Умные перечисления с диапазонами плохи тем, что в общем случае Вам придется перебрать очень много вариантов прежде чем найдете нужный диапазон. Это было бы оправданно если бы значений было 10^9 и больше, ну или у Вас был бы очень старый или очень специфический процессор;-)

Если скорость критична, то всякие архиваторы сильно испортят всю картину. Сравните на досуге сколько скажем пишется на диск картинка в формате bmp и png - там разница больше чем в десять раз...

Умные перечисления с диапазонами плохи тем, что в общем случае Вам придется перебрать очень много вариантов

Дерево диапазонов, упорядоченное по началу диапазона? Правда, очень большие накладные расходы.

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

Да дерево (или поиск половинным делением, что тоже самое в итоге), сложность N log(N)... А сколько тактов на узел? Это может быть оправданно если данных ОЧЕНЬ много и значения идут вразнобой. В любом случае, сначала нужно проверить на что уходит основное время работы, и вот ТОЛЬКО когда оно начнет уходить на проверку, вот ТОЛЬКО тогда нужно сажать всякие деревья.

http://crd.lbl.gov/~kewu/fastbit/

Согласен. Сложные алгоритмы надо использовать там где они уместны - то есть если например количество возможных значений например 100 миллиардов, а количество реальных значений порядка 10-20 тысяч, или если делаются проверки по множеству наборов диапазонов, в каждом из которых сравнительно немного значений.

Если же «алфавит» небольшой и их (множеств используемых значений) не слишком много - типа использованых локальных номеров портов - тогда да, проще битовые маски.

Тупое использование битовой карты (кушает 12 Мб памяти, при этом Firefox, в котором я сейчас это пишу, кушает 180 Мб).

#include <stdio.h>

#define BITCOUNT 100000000

char set[(BITCOUNT + 7) / 8];

int getbit(char *set, int number)
{
        set += number / 8;
        return (*set & (1 << (number % 8))) != 0;       /* 0 or 1       */
}

int setbit(char *set, int number, int value)
{
        set += number / 8;
        if (value)
                *set |= 1 << (number % 8);              /* set bit      */
        else    *set &= ~(1 << (number % 8));           /* clear bit    */
}

int main() {
	int i, j;
	for (i = 0; i < BITCOUNT / 1000; i++) {
		for (j = 0; j < 1000; j++) {
			setbit(set, i*1000+j, 1);
		}
	}
	printf("Done!\n");
	return 0;
}

$ time ./a.out 
Done!

real	0m1.009s
user	0m0.952s
sys	0m0.012s

ЧЯДНТ?

под set память все таки лучше выделять в куче, оно кошернее;-)

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

> под set память все таки лучше выделять в куче, оно кошернее;-)

кстати да, так ещё лучше, скорость работы возрастает в 4 раза :)

А скока у Вашего проца ГГц и какие опции компиляции?

И какой сакральный смысл в двойном цикле в main?

аффтару гуглить union-find и перед тем как задавать вопросы попросить у учительницы информатики методичку по основным классическим алгоритмам.

остальным: спасибо, поржал

Мне кажется, ты не вкурил, в чём соль. Ваш эти disjoint-set data structure вместе с union-find разве реализуют хранение диапазонов?

разве реализуют хранение диапазонов?

Эй, ТС, ты определись - тебе нужно ХРАНЕНИЕ ДИАПАЗОНОВ, или ХРАНЕНИЕ РЕЗУЬТАТА ВЫПОЛНЕНИЯ (выполнено-невыполнено).

Это на самом деле существенно - битовые маски хорошо позволяют реализовать задачу «Скажи, а было ли выполнено задание номер XXXXX?», но они сбоят на задачах вида «Скажи, какое задание не выполнено чтобы мы могли начать его выполнять?», поскольку по битовым маскам надо будет ходить перебором, что есть нехорошо, либо придется организовывать индексы, разбивать биты по «кластерам» для эффективного престроения индексов и т.п.

Использовать какую-то хитрую структуру судя по условию смысла нет. Если вдруг внезапно во входных данных только нечетные числа, 50 000 000 их разных, то никаких перечислений нет и нужно будет хранить 50 000 000 разных значений. При этом будет даже больше памяти использовано, ибо структура скорее всего что-то дополнительно хранит.

Так что с точки зрения структуры данных ваш выбор — велосипедный битовый массив или даже (свят-свят!) vector<bool>, который им и является вроде.

P.S. комментарии не читал. :)

Тему не читал.

Перешел сюда с маклауд-плача.

Бессмысленно - храни храни битовые флаги/булев массив или как ты это называешь. Любая попытка юзать «умные» перечисления, в лучшем случае приведет к тормозам.

Отпишусь тут по многочисленным просьбам трудящихся

По идее разумным выбором для этой задачи будет обычный битовый массив, типа уже приведённых в этом треде, до тех пор, пока этот массив укладывается в требования по памяти.

Теперь что делать, если этот массив в память весь не помещается. Тут ключевым вопросом будет «А сколько там лишней информации». И если у нас выбор каждого следующего проверенного элемента полностью случаен, то как бы мы не вертели эту задачу, в какой-то момент времени у нас по объёму будет тот же самый битовый массив + накладные расходы на его сжатие. Но вот если у нас выбор следующего элемента не равновероятен, то возможны более удачные варианты. Можно использовать какой-то алгоритм сжатия, от модифицированного RLE и до стандартных для архиваторов алгоритмов (LZMA :). Из неприятного получается то, что нам весь этот массив надо перед каждым шагом распаковывать, после каждого шага перепаковывать обратно. Чтобы не делать этого для всего массива можно попробовать разбить его на страницы, и уже к ним применять сжатие. Плюс в предельном случае мы можем дать странице два флага «полностью заполненная» и «полностью пустая» и не обращаться для таких к данным массива вообще, сильно экономя память и время на начальной и финальной стадии заполнения.

Теперь специально для отдельных великих учёных, снисходящих в тред нести знание людям:

Если принудить проверять сразу пачками по 5-10 последовательных элементов, то массив индексов можно ужать, из-за его меньшей энтропии. Если же «квант» процедуры проверки - один элемент, то, согласно Шеннону, не существует никакого кода, который бы мог ужать массив индексов без потери информации.

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

> А скока у Вашего проца ГГц и какие опции компиляции?

$ sudo lshw -c cpu | grep product
       product: Intel(R) Celeron(R) CPU          550  @ 2.00GHz

$ gcc -g0 -O2 main.c

> И какой сакральный смысл в двойном цикле в main?

А никакого :D Это я просто экспериментировал и, как обычно, забыл убрать.

То есть по пять тактов на элемент. Если доступ будет не подряд, то будет помедленней, но все равно никаким деревом этот результат не перебить;-)

Несколько интересных вариантов увидел, спасибо.

В данном случае, данные будут проверяться пачками, около ~1000 подряд, т.е., экономия памяти будет очевидна при использовании диапазонов/перечислений. Ситуация со всеми нечётными номерами даже не учитывается, это почти нереально.

> на задачах вида «Скажи, какое задание не выполнено чтобы мы могли начать его выполнять?»

именно такая задача и стоит.

Ради справедливости стоит добавить

Зря потерли комментарии mclaudt'а, его замечания были к месту, поскольку я недостаточно точно сформировал условие.

если бы он повежливее был немного, может быть и не потёрли бы.

Бессмысленно - храни храни битовые флаги/булев массив или как ты это называешь. Любая попытка юзать «умные» перечисления, в лучшем случае приведет к тормозам.

А теперь вопрос на засыпку - как без «умных перечислений» или других извращений с составными структурами реализовать операцию «Найди какое-нибудь невыполнявшееся задание» со сложностью менее чем O(N)? :-)

Будешь бить исходный массив на части, и для каждой части хранить «сколько заданий выполнено и сколько нет»?

скорость и объём памяти взаимоисключающие вещи. Можно всё тупо класть в файл иметь массив хоть из триллионов бит. А можно держать в массиве байт (не бит даже) с самым скоростным доступом.
Автор хочет непонятно чего. Чтобы и быстро было и памяти поменьше.

Автор знает, чего хочет.

скорость и объём памяти взаимоисключающие вещи

Только для тех, кто делает задачи «в лоб». Ты отрицаешь возможность оптимизаций структур и методов работы с ними?

Если у меня есть диапазон, который характеризуется минимальным и максимальным значениями, то это дает

1) Уменьшение памяти - не надо хранить состояние каждого элемента.

2) Чтобы проверить наличие части или всего диапазона [A] в интересующем нас диапазоне [B]- надо сделать лишь пару проверок, а не N штук, где N - количество элементов в [A].

Профиты разве неочевидны?

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

если вероятность прохождения проверки для каждого элемента равна 0.5, то массив этих проверок каждый раз будет последовательностью случайных двоичных числе. Оно не сжимается пруф

dd if=/dev/urandom count=1000000 bs=1 2>/dev/null > test
7z a test.7z test 

У меня вероятность прохождения проверки - более 0.9, в среднем даже больше 0.99

Значит имеем 1 нолик на 99 единичек. В среднем последовательность единиц будет прерываться через 100 бит или 12 байт. Таким образом запись интервала X-Y должна занимать меньше, чем 12 байт. Но X-Y это 2 числа по 4 байта, так как имеем дело с диапазоном в 100 млн. Значит максмальное сжатие составит 12/8=1.5 всего-то.

Я понимаю, что телепатов нет, и полностью картины ты мржешь не увидеть. Дела обстоят даже лучше. Чаще всего могут пройти десятки тысяч успешных проверок подряд. В следующем запуске сразу стараемся проверить те, у которых статус «непроверен». Понятия «неудачная проверка» нет. Таким образом, разные прерывания будут успешно устраняться. Т.е., ужасающих разрывов и энтропии быть не должно, а если такое будет - это уже проблема в сервисе/оборудовании/канале связи и ситуация будет внештатная. Т.е., если больше 10-20% неудачных проверок - работу временно вообще прекращаем.

запись диапазонов X-Y это модификация алгоритма сжатия RLE.