Как объединить два отсортированных массива (n1 и n2 элементов) в один отсортированный массив? Такой вопрос мне неоднократно попадался на собеседованиях и даже пару раз сталкивался с ним на практике. Вся сложность этого вопроса не в том как это сделать, а как это сделать максимально быстро.
Быстрее всего это делается за n1+n2 итераций (линейное время). Пусть есть два отсортированных по возрастанию массива A1 и A2. Можно легко определить первый элемент результирующего массива - им будет либо первый элемент первого массива, либо первый элемент второго массива, в зависимости от того, что меньше. Допустим, наименьший - это A1[0]. На следующей итерации при помощи одного сравнения определяется второй элемент результирующего массива - опять сравниваются первые элементы исходных массивов, при условии, что для A1 первый элемент - это A1[1], так как A1[0] - уже выбыл из игры. И так продолжается пока не будет заполнен результирующий массив. На картинке это выглядит так:
Как видно, ничего сложного в этом алгоритме нет. Самое интересное в нем - это возможность использования для сортировки. Любой массив размера n можно представить в виде n массивов, состоящих из одного элемента. Пары соседних элементов, представленных ввиде массивов можно объединять по описанному выше алгоритму. Получится примерно в 2 раза (примерно, потому что n может быть как четным так и нечетным числом) меньше отсортированных массива по 2 элемента, которые в свою очередь тоже можно объединить. И так пока не получится один отсортированный массив.
А все это называется сортировка слиянием.
воскресенье, 16 ноября 2008 г.
Объединение двух отсортированных массивов
суббота, 15 ноября 2008 г.
Concepts в C++0x
Наконец то удалось посмотреть видео о новых расширениях С++ Concepts: Extending C++ Templates For Generic Programming. Решил поделиться своими впечатлениями.
Concepts - это расширение существующих шаблонов С++, позволяющие устанавливать требования к параметрам шаблона. Концепция позволяет ответить на несколько вопросов:
В ролике это называлось Concept definitions, Where clauses и Concept maps соответственно. Насколько я понимаю, то, что было озвучено и то, что будет в стандарте немного отличается, по крайне мере вместо where будет использоваться requires, поэтому пример будет выглядеть не как в видео:// Вычисление суммы элементов последовательности
// Параметр шаблона должен быть Forward Iterator -
// позволяет двигаться только в перед
template< ForwardIterator Iter >
// два значения, на которые указывают итераторы,
// могут быть сложены при помощи оператора +
requires Addable< Iter::value_type >,
// объект, на который указывает итератор,
// должен иметь оператор присваивания
&& Assignable< Iter::value_type >
Iter::value_type sum(Iter first, Iter last,
Iter::value_type result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}
// у типа double* нет оператора сложения, присваивания,
// получения следующего элемента последовательности,
// но реализация алгоритма sum будет корректно работать
// с этим типом, поэтому устанавливается соответствие
// между ForwardIterator и double*
concept_map ForwardIterator
typedef double value_type;
};
Надеюсь, теперь понятно, зачем вводятся concepts, если нет, то подробней можно почитать здесь: ConceptC++ Tutorial.
На видео, дядька приводит другой пример, знакомый всем, кто использовал STL: простой алгоритм поиска, реализованный в соответствие с требованиями STL, отлично работает с вектором, но не хочет работать со списком. Хотя внешне все вписывается в общую структуру библиотеки: контейнеры - итераторы - алгоритмы. Для того, что бы понять, что не так с алгоритмом нужно копаться в его коде либо использовать concepts. Начиная с этого места у меня появилось чувство, что concepts - это костыль, который подсовывают С++. Проблема как была, так и осталась, но теперь можно уверенно хромать в перед. Лечится только следствие проблемы - теперь компилятор будет сам говорить, что хотя все вписывается в рамки, но работать все равно не будет. При этом, возможность писать неработающий код так и остается - для совместимости с предыдущими версиями.
Кроме того, и без того, часто трудночитаемый код с шаблонами, станет во много раз менее читабельным. А разработчику придется больше потеть, определяя жесткие требования к написанным функциям.
Это первое впечатление, основанное на двухчасовом знакомстве с этим нововведением. Надо будет еще обдумать прочитанное и просмотренное, а то прям бесполезная какая-то штука получается :) Поэтому интересно было бы услышать критику моего обзора и мысли по поводу concepts.
четверг, 13 ноября 2008 г.
Задачка про прилив
Нашел в шкафу старую книгу "Математическая смекалка". Замечательная книга! Теперь по вечерам сижу с удовольствием решаю задачки - неплохая гимнастика для мозгов и хорошая альтернатива вечернему созерцанию интернета. Вот одна из задач, которая мне понравилась (кстати, ничем не хуже майкрософтовских :)
Недалеко от берега стоит корабль со спущенной на воду веревочной лестницей вдоль борта. У лестницы 10 ступенек; расстояние между ступеньками 30 см. Самая нижняя ступенька касается поверхности воды. Океан сегодня очень покоен, но начинается прилив, который поднимает воду за каждый час на 15 см. Через сколько времени покроется водой третья ступенька веревочной лесенки?
вторник, 11 ноября 2008 г.
Python 3 Patterns & Idioms
Стала доступна open source книга Python 3 Patterns & Idioms, написанная Bruce Eckel при содействии Python community. Она распространяется под лицензией Creative Commons Attribution-Share Alike 3.0 (первый раз о такой слышу :).
Книга еще сыровата, по крайне мере в содержании все перемешано в кучу и некоторые главы отсутствуют. Большая часть посвящена паттернам, например, есть много про singleton, есть много про Jython, немного про юнит тестирование и TDD, рефакторинг, а так же упражнения к каждой главе. Самое интересное, что здесь кода больше, чем букафф :)
среда, 29 октября 2008 г.
Задача о шляпах от Microsoft
На лестнице стоят 4 человека. Самый верхний стоит на ступеньке, спрятанной за непроницаемой стеной и не видит никого. Все остальные видят только вышестоящих: A видит B и С, B видит C, С видит стену.
На каждом из человечков одета шляпа. На двоих красные шляпы, на других двоих черные. Кто из них первый поймет какого цвета у него шляпа, если никто не может ее снять и посмотреть?
Дополнительные условия: человечки не могут поворачиваться, не могут переговариваться и перемещаться по лестнице, так же они не могут блефовать и ломать стену.
ЗЫ: Выглядит это примерно так:
понедельник, 27 октября 2008 г.
Поиск последовательности в массиве
Задача
Есть массив положительных и отрицательных чисел. Нужно найти последовательность значений, сумма которой будет наибольшая. Например, для массива [-2, 5, -5, 8, -1, 3, 2, 6] наибольшая сумма будет для последовательности [8, -1, 3, 2, 6].
Решение
Пусть нам дан массив:
src_aray = [x1, x2, x3, x4]
Тогда для решения поставленной задачи нужно вычислить и найти наибольшее для следующих последовательностей:
x1+x2+x3
x2+x3
x1
x2+x3+x4
x2+x3
x2
x3+x4
x3
x4
Так как известно, что массив может содержать отрицательные значения, то можно попытаться уменьшить количество вычислений, суммируя только те последовательности, которые начинаются с положительного числа. Только нужно учесть, что массив может полностью состоять из отрицательных чисел.
Тогда алгоритм будет такой:
1. Массив проверяется на наличие положительных чисел.
2. Пошагово проверяем каждый элемент массива xi.
3. Если в массиве нет положительных чисел (худший вариант), вычисляем сумму всех последовательностей, начинающихся с xi.
4. Если в массиве есть положительные числа, вычисляем сумму всех последовательностей, начинающихся с xi, только в случае xi > 0.
5. Среди вычисленных сумм, выбираем наибольшую.
Реализовать этот алгоритм можно так:
// допускаем, что данные всегда передаются валидные
// src_array - исходный массив
// len - его длина
// sindex, eindex - результат поиска - начальный и
// конечный индексы последовательности
void sub_array(int *src_array, int len,
int &sindex, int &eindex)
{
int sum = src_array[0];
sindex = 0;
eindex = 0;
// проверяем наличие положительных значений
bool has_positive = false;
for(int i=0;i < len;i++)
if(src_array[i]>0)
{
has_positive = true;
break;
}
for(int i=0;i < len;i++)
{
int ssum = src_array[i];
if(has_positive && ssum < 0) continue;
for(int j=i;j < len;j++)
{
ssum += j>i?src_array[j]:0;
if(ssum>=sum)
{
sum = ssum;
sindex = i;
eindex = j;
}
}
}
}
воскресенье, 26 октября 2008 г.
Поиск дубликатов в массиве
Задача
Есть массив целых от 1 до N. Нужно определить, есть ли в этом массиве повторяющиеся значения.
Решение
Задачу можно решить несколькими способами. Первое, что приходит в голову - отсортировать исходный массив и сравнивать соседние элементы. Затраты по времени и по расходуемой памяти будут зависеть от алгоритма сортировки, например, при быстрой сортировке временная сложность будет O(nlogn +n-1) и емкостная сложность (память) будет O(logn).
Другое решение - пошагово обходить массив и в каждой итерации проверять значение элемента, сравнивая с информацией о предыдущих итерациях, сохраняемой в дополнительном контейнере. Таким контейнером может быть массив размера N и полностью заполненный нулями. Индекс элемента в массиве - значение от 1 до N (точнее от 0 до N-1), значение элемента - количество "индекса" в исходном массиве. Это проще выглядит на примере:
// исходный массив, со значениями от 1 до 9
src_array = [1,3,8,4,2,9,3,9]
// дополнительный массив на 9 элементов (что бы уместились от 1 до 9)
add_array = [0,0,0,0,0,0,0,0,0]
// после обработки исходного массива результирующий будет выглядеть так:
// одна единица, одна двойка, две тройки, одна четверка, одна восьмерка и две девятки
add_array = [1,1,2,1,0,0,0,1,2]
Сложность такого алгоритма будет O(n), затраты памяти будут зависеть от диапазона данных - O(maxN-minN). Кроме этого, требуется, что бы было известно максимальное значение элементов из исходного массива, в противном случае либо будет затрачиваться дополнительное время на его поиск, либо понадобиться значительно больше памяти (например, что бы поместить все целые числа).
Вывод
Из двух предложенных решений первое требует дополнительно реализации сортировки, но является более универсальным и имеет преимущества при больших размерах исходного массива и большом диапазоне значений. Второй метод проще реализуем (если предположить, что в первом случае нет готовой функции сортировки), но требует дополнительной информации о диапазоне значений и при большом диапазоне - большие затраты памяти.
