На первый взгляд приходят в голову битовые карты (ведь множество значений элементов небольшое), однако они, как мне кажется, не проходят по условию «быстрое итерирование и очистка».

И почему же?

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

Он просил О(N), а тут прям O(1) =D

А если серьезно, какую долю заполнения ожидаешь?

И да, для эстетов есть байтовая карта.

Ожидаю, что большую часть времени в Set будет меньше сотни элементов. Часто даже 20-30. Иногда оно вообще будет пустое.

Это всё равно быстрее, чем другие решения. Рассуждения про O(ololo) на 4096 элементов можешь сразу выкинуть.

Тебе нужен lookup table а не set. Делаешь буфер из 4096 элементов, ну или из 4096/32 если память экономишь, 0 - элемент не добавлен, единичка - добавлен. Быстрее для этой задачи кажется, что ничего не придумать.

Скорее всего, тот кто делал спеку которую ты сейчас реализуешь, именно так себе это и представлял :)

Если бы было 10, я бы тебе предложил мэйнтейнить массив и битовую карту одновременно. Вставка за O(1), проверка за O(1), чистка за O(1), итерация за O(N).

А если 100, то я бы ожидал, что огород того не стоит.

про O(ololo) на 4096 элементов можешь сразу выкинуть

лорчую анона

И самое первое O, которое нужно допнуть - «O(1) на вставку». На менее чем сотне элементов может быть обычный массив из добавленных чисел(линейный поиск дубля перед вставкой) будет лучше всего.

Но ТС явно не из тех, кто идёт лёгкими путями. Давно бы уже забэнчил, но нет.

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

Массив из 4096 char. Или массив из 64 uint64_t и дальше биты там дергать. Для выковыривания битов можно использовать сдвиги, битовые маски, в GCC есть еще такая встроенная функция __builtin_ctzll

0 до 4095

O(N), O(1).

Ты ведь, правда шутишь? Все эти O и в старые добрые времена были интересны начиная с пары тройки десятков тыщЪ, а сейчас, наверно, начиная с пары тройки сотен тыщЪ элементов. Великое горе от ума. Вот ведь сишникам реально делать нечего.

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

Например, если задача сложить числа, то пакуя в 8 битные числа можно будет получать все числа с помощью сдвига на индекс * константу для каждого из 8 чисел в пачке, и цикл для суммы будет на 128 итераций а не на 4096, если применять решение в лоб. Возможно, можно подобрать подходящую SIMD операцию для такой задачи.

А положение числа в списке тебе важно или нет? Или тебя устраивает ситуация, когда число 100 всегда будет 101ым в списке?

ну это ж лаба, или тестовое задание какое-то

Массив чем не устраивает, прибавляешь 1 к числу и используешь в качестве индекса, забивание нулями очистка, 0 - элемента нет, >0 элемент есть, в процессоре 86 есть инструкции сканировать до нулевого элемента, наверняка это используется в библиотеках си, так что поиск выльется в десяток инструкций.

зы. «Команда SCAS производит сравнение содержимого регистра (AL или AX) с байтом памяти, абсолютный адрес которого определяется парой ES:DI, после чего регистр DI устанавливается на соседний элемент памяти (байт или слово) в соответствии с флагом DF. Команда SCAS используется обычно для поиска в строке (ES:DI) элемента заданного в регистре AL или AX.»

Два массива на 4096, один как маска, во второй кладешь списком добавленное.

Да ладно, а то в этом треде никто не догадался. Особенно ТС.

Просто делаешь обычный битсет, во время итерации скипаешь куски с нулями и ведущие нули внутри каждого куска через ctz/clz. Правда, неочевидно, что последняя оптимизация сделает лучше, так что проверь сам.

Наконец-то появился повод поделиться этой статьей:

Using Uninitialized Memory for Fun and Profit

Накорябал портянку:

#define Set(N) \
struct \
{ \
	u16 dense[N]; \
	u16 sparse[N]; \
	u16 n; \
}

static inline bool setGet(const u16 *dense, const u16 *sparse, u16 n, u16 x)
{
	const u16 s = sparse[x];
	return s < n && dense[s] == x;
}

static inline void setAdd(u16 *restrict dense, u16 *restrict sparse, u16 *restrict pN, u16 cap, u16 x)
{
	const u16 n = *pN;
	assert(x < cap && n < cap);

	if (setGet(dense, sparse, n, x))
		return;

	dense[n] = x;
	sparse[x] = n;
	*pN = n + 1;
}

#define setClear(s) \
	((s)->n = 0)
#define setGet(s, x) \
	setGet((s)->dense, (s)->sparse, (s)->n, (x))
#define setAdd(s, x) \
	setAdd((s)->dense, (s)->sparse, &(s)->n, ARRAY_SIZE((s)->dense), (x))
#define set_for_each(s, x) \
	for (u16 *_p = (s)->dense, *const _end = _p + (s)->n, x; _p < _end && (x = *_p++, 1);)

Удовлетворяет требованию «быстрое итерирование и очистка». Очистка быстрее некуда, итерирование не требует ffs. Но всё же проверь на своих данных. Даже если не подойдет, то все равно интересное упражнение и алгоритм.

int data[4096];

#define set(n) data[n] = 1     // O(1)
#define isset(n) data[n] == 1  // O(1)
#define clear() data = {0}     // O(1)

for (n = 0; n < 4096; n++) {   // O(N)
    if (isset(n)) {
        do_something_with(n);
    }
}

Вроде все условия выполнил. KISS.

Для 4k значений байто-дрочиво можно опустить.

Из готового:

#include <sys/param.h>

→ https://github.com/openbsd/src/blob/master/sys/sys/param.h

Даст тебе следующий набор:

/* Bit map related macros. */
#define setbit(a,i)     ((a)[(i)>>3] |= 1<<((i)&(NBBY-1)))
#define clrbit(a,i)     ((a)[(i)>>3] &= ~(1<<((i)&(NBBY-1))))
#define isset(a,i)      ((a)[(i)>>3] & (1<<((i)&(NBBY-1))))
#define isclr(a,i)      (((a)[(i)>>3] & (1<<((i)&(NBBY-1)))) == 0)

Да, практически хрестоматийный случай. Удаление тоже реализуется.

+1

.

O(n)

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

Спасибо, прикольный и простой алгоритм. Понравилось как удаление сделано.

Кажется, это то что мне нужно. Очень элегантное решение!

А чего такого особенного в ТС? Можно подумать где-то в конце темы есть результаты такой-то алгоритм работает столько, такой-то столько.

Статья хорошая, а макро-изврат бессмысленный.

#define clear() data = {0}     // O(1)

Адназначна!

Ничего, это тычок в сторону того, что идею битмасок он предвосхитил и даже заранее в меру способностей раскритиковал, еще в шапке.

#define clear() data = {0}     // O(1)

Полыхнуло.

Ну потому что придётся бегать по всей битовой карте,

Т.е. обычно элементов в set-е немного. Сделай несколько битовых карт разных масштабов.

512 байт - битовая карта всех элементов

64 байта - битовая карта, где бит=0 говорит, что соответствующий байт из 512 карты пустой.

8 байт - по аналогии, битовая карта для 64 байт

1 байт - битовая карта для 8 байт.

Добавлением в структуру ещё одного поля deleted_count и «порчей» удаляемого элемента в dense?

Там в комментариях человек написал:

Через sparse смотрим, где жил наш удаляемый элемент. Используя этот индекс, «удаляем» этот элемент из dense путем его обмена с последним элементом dense (стандартный подход удаления из массива когда порядок не важен). Теперь осталось только подправить ячейку sparse, соответствующую последнему элементу dense.

А, ну да, прикольно. Спасибо :)

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

Может просто сонный был? Не надо себя думать :)

буду неоригинальна: ты не в микроконтроллере, выдели массив на 4095 элементов и пиши туда, сколько хочешь. определи «незанятое» значение как 4096 и используй его для «затирания» значений. и радуйся жизни. доступ по индексу, быстрее не бывает. всё тривиально.

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

Было или нет. Массив байт (или минимально адресуемых данных) на 4096 элементов. И один байт на текущее значение, которое является признаком занятости. Очистка - инкремент признака занятости.

набросок

unsigned char data[4096] = {0};
unsigned char flag = 1;

set(k) { data[k] = flag; }
unset(k) { data[k] = flag - 1; }
test(k) { return data[k] == flag; }
clear(k) { flag++; }

Зачем бегать? Число дели на 8, целая часть будет номер байта, а дробная номер бита. Установлен бит - значит число задано.

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

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

Господи, uint64_t[64] и всё, битовая маска называется. Развели тут дискуссии, хотя вопрос выеденного яйца не стоит. Ничего быстрей в природе не существует. Если хочешь ещё быстрей, кури SSE.

битовая маска называется

Как у него с

очистка желательно за O(1).

memset. Забить 512 последовательных байтов нулями это очень быстро. Ничего быстрей ты просто не придумаешь. И на O(1) не надо кивать, в данном случае у нас жёстко ограничено число элементов, поэтому смысл O-нотации теряется, есть смысл рассуждать только о реальной производительности.

Чисто теоретически можно ввести ещё впереди маску из одного uint64_t, который будет означать, инициализирован ли соответствующий 8-байтовый кусок. Тогда очистка сведётся к обнулению этой маски, но все остальные операции должны будут проходить через неё. Если прям очистка постоянно производится, в этом есть смысл.

Это мнение твое выеденного яйца не стоит, а не вопрос, которого ты просто не осознал.

Забить 512 байтов нулями это очень быстро

Насколько быстрее чем изменить 4 байта (точнее 2 или даже 1 байт), которые в регистре, пусть даже если avx512?

А зачем тебя волнует O(N) когда у тебя сверху ограничение в 4096 элементов. Если ты как-то сильно утыкаешься в производительность и тебе надо это оптимизировать, то тебя волнует совсем другая оптимизация алгоритма. Либо который будет быстрее всего в большинстве случаев на выборке твоего размера, либо который будет быстрее всего на выборке твоего размера в худшем случае, т.е. T(N)