花弁

Доброкодер 22 July 2009 (Wed) 03:16 No.513

File: 124110119898.png
Png, 136.87 KB, 660×450 - Click the image to expand

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

Например для массива [1, 2, 3, 4, 6, 10, 12, 13, 14, 15] и интервала 2-12 конечный результат должен быть [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].

Все это хочется реализовать максимально просто и эффективно, то есть с минимальным использованием памяти, так что код с использованием функциональных языков и списков не интересует. Основная идея в том, чтобы находить "дыру", увеличивать количество памяти на размер дыры, отодвигать все элементы справа от нее на размер дыры, заполнять и двигаться дальше. Но есть два граничных условия: когда дыра до начала массива и когда дыра после конца массива. Хотелось бы как-то избавиться от этих проверок, которые портят няшный сишный код. Какие есть идеи? Пока что придумал только добавить ноль и бесконечность в начало и конец массива, но это все не очень красиво. Может можно придумать что-то с указателями?

Доброкодер 22 July 2009 (Wed) 17:48 No.516

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

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

Доброкодер 22 July 2009 (Wed) 21:34 No.517

>>516
Бинарная куча преобразуется в сортированный массив за время O(n log n) без дополнительной памяти (только обменами элементов). Сама куча тоже никакой памяти, кроме самого массива, не требует. На ее создание тоже уйдет время O(n log n). А твои сдвиги элементов по массиву наверняка в квадратичное время выльются.

Доброкодер 22 July 2009 (Wed) 21:56 No.518

>>517

> Бинарная куча преобразуется в сортированный массив за время O(n log n)

Вот этого не знал, нужно погуглить. Алсо, Кнут описывает кучу как сортировку ("сортировка с минимальным числом сравнений"), а не как структуру данных. Мне это кажется неправильным, сортировка кучей на разных кучах работает с тем же числом сравнений, а не только на бинарных.

А что делать с повторами? От них в куче можно как-то просто избавиться?

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

Доброкодер 23 July 2009 (Thu) 06:56 No.520

>>517
Насколько я понял, твое предложение с бинарной кучей равносильно тому, чтобы затолкать все числа в один массив, сделать heapsort и удалить повторяющиеся элементы. Если это так, то может лучше использовать быструю сортировку?

Доброкодер 23 July 2009 (Thu) 10:47 No.522

>>521
Сейчас у меня уже реализовано в виде заталкивания в массив, быстрой сортировки и удаления повторов. Думал сделать что-то покруче с сохранением порядка при заполнении массива. Видимо, это будет медленнее.

Доброкодер 23 July 2009 (Thu) 19:14 No.524

a - массив, [l, r] - интервал.
'i := 0;
while (i < length(a)) and (a[i] < l) do
i := i + 1;
j := i;
while (j < length(a)) and (a[j] <= r) do
j := j + 1;
old_len := length(a);
setlength(a, i + (r - l + 1) + (length(a) - j));
for k := length(a) - 1 downto i + (r - l + 1) do
a[k] := a[k - (length(a) - old_len)];
for k := i to i + r - l do
a[k] := l + k - i; '
Говнокод, эффективный по памяти и времени.

Доброкодер 24 July 2009 (Fri) 01:35 No.527

File: 1248277220555.jpg
Jpg, 28.58 KB, 600×310 - Click the image to expand

>>524
Классный код, идея с подсчетом нового размера как разницы между элементом, меньшим, чем начало интервала и большим, чем конец интервала мне что-то в голову не пришла. Показалось, что придется для этого проходить по массиву. Ты этот код сейчас написал?