| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
Yello
Зарегистрирован: 09.03.2006
Сообщения: 107
|
 Добавлено: Пн Июл 16 2007 06:51 Заголовок сообщения: ДАЁШЬ АЛГОРИТМ !!!!! |
 |
|
Здравствуйте.
У меня такой вопрос: нужен алгоритм для объединения двух множеств, заданных массивами. Множества (массивы) упорядочены по возрастанию, и результат должен быть - тоже. (Имеется ввиду упорядоченность по целым номерам элемента). Новый элемент "+INFINITY" в конец массива "приделывать" нежелательно.
Какой алгоритм (из известных вам) быстрее всего?
Понимаю, что это вопрос не совсем корректный (типа "какая сортировка самая быстрая"), но уточнить область применения нельзя. Поэтому сам мучаюсь. Вдруг кто-нибудь поумнее что подскажет? |
|
| Вернуться к началу |
|
 |
vir
Зарегистрирован: 17.05.2007
Сообщения: 24
|
| Добавлено: Пт Июл 20 2007 11:58 Заголовок сообщения: |
|
|
| Код: | merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x == y = x : merge xs ys
| x > y = merge (x:xs) ys
| x < y = merge xs (y:ys) |
|
|
| Вернуться к началу |
|
|
Yello
Зарегистрирован: 09.03.2006
Сообщения: 107
|
| Добавлено: Ср Авг 08 2007 12:04 Заголовок сообщения: |
|
|
| Цитата: | merge [] ys = ys
merge xs [] = xs
merge (x s) (y:ys)
| x == y = x : merge xs ys
| x > y = merge (xs) ys
| x < y = merge xs (y:ys) |
А на С++ ?
То есть, я сам виноват, надо было сразу уточнить:
1. все массивы - только в динамической памяти.
2. Длина, т.е. к-во элементов, может быть разная.
3. При реализации этой программы, на уровень языков выше, чем C, подниматься нельзя (вообще, представьте, что надо написать максимально быстрый код, решающий задачу, на asm86)!
Вот теперь, когда задача уточнена - милости прошу!
В КНУТЕ - НЕТ !!! (вообще - и сам могу, несколько разных вариантов, но по поводу их оптимальности - большой вопрос. Ну ведь честно, какие сортировки например может сам придумать любой нормальный человек, и какие при этом есть...  вот именно. Поэтому и спрашиваю.) |
|
| Вернуться к началу |
|
|
vir
Зарегистрирован: 17.05.2007
Сообщения: 24
|
| Добавлено: Чт Авг 30 2007 11:22 Заголовок сообщения: |
|
|
C, массивы:
| Код: |
// слияние 2х отсортированных массивов в 3й
// xs, ys --- исходные массивы
// nxs, nys --- соответствующие размеры (кол-во элементов)
// rs --- массив, куда записывается результат
// nrs --- максимально допустимый размер результата
// возвращаемое значение --- кол-во элементов в результате.
int merge (int nxs, int *xs, int nys, int *ys, int nrs, int*rs)
{
int nrs1 = nrs;
while (nrs > 0 && nxs > 0 && nys > 0) {
if (*xs == *ys) {
*rs++ = *xs++;
nrs--;
nxs--;
ys++;
nys--;
}
if (*xs < *ys) {
*rs++ = *xs++;
nrs--;
nxs--;
}
if (*xs > *ys) {
*rs++ = *ys++;
nrs--;
nys--;
}
}
while (nxs > 0 && nrs > 0) {
*rs++ = *xs++;
nxs--;
nrs--;
}
while (nys > 0 && nrs > 0) {
*rs++ = *xy++;
nys--;
nrs--;
}
return nrs1 - nrs; // сколько элементов добавили в массив
}
|
|
|
| Вернуться к началу |
|
|
Yello
Зарегистрирован: 09.03.2006
Сообщения: 107
|
| Добавлено: Ср Сен 26 2007 12:42 Заголовок сообщения: |
|
|
Да, спасибо.
У меня было всё также, за исключением 2-х моментов:
1. обработка "хвостов" была в главном цикле.
2. хождение по массиву - с операцией [] вместо инкрементации самого указателя.
Т.е., Ваша прога сильнее оптимизирована по скорости (и ведь это были очевидные вещи, жаль что сам не догадался).
Хотя, не знаю, как это для современных компиляторов (MS, gnu) - может, вообще без разницы, они и сами оптимизируют... |
|
| Вернуться к началу |
|
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
