- Сортировка подсчетом

Сообщения без ответов | Активные темы

Список форумов » Разное » Другие вопросы по программированию

Часовой пояс: UTC + 3 часа

Сортировка подсчетом

Страница 1 из 1

[ Сообщений: 16 ]

Версия для печати

Пред. тема | След. тема

Автор

Сообщение

Евгений Темиргалеев

Заголовок сообщения: Сортировка подсчетом

Добавлено: Понедельник, 14 Май, 2007 14:11

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Разбираю различные алгоритмы сортировки. Один из простейших - сортировка подсчетом. Есть различные вариации. Я смотрел в http://ru.wikipedia.org/wiki/, на русской странице (на других языках могут попасться другие вариации).

Временная сложность алгоритма O(n+k). n - число элементов в массиве. k - длина отрезка, который вмещает элементы массива. k = maxEl - minEl + 1.

Опробуется алгоритм на массивах 4 видов:
1) Упоряд-й по возр-ю, k > n
2) Упоряд-й по убыв-ю, k > n
3) Случайные числа из "широкого" диапазона ("шире" диапазона индексов), k > n
4) Часто повторяющиеся случайные числа, k < n

Ниже привожу время работы:
- поиск min/max
- создание массива счетчиков
- подсчет
- формирование результ-го массива (запись эл-в по порядку)
- итоговое

В пункте подсчет массивы 1) и 2) обрабатываются быстрее, нежели 3) и 4)

Последний раз редактировалось Евгений Темиргалеев Вторник, 15 Май, 2007 00:03, всего редактировалось 1 раз.

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 14:13

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Код:

   PROCEDURE Sort (VAR array: ARRAY OF INTEGER; VAR time: REAL);
      VAR
         min, max, len: INTEGER;
         i, j, k, x: INTEGER;
         b: POINTER TO ARRAY OF INTEGER;
         t: REAL;
   BEGIN
      StdLog.String("n = "); StdLog.Int(LEN(array)); StdLog.Ln;
      U.StartTimer(time);
      U.StartTimer(t);
      min := array[0]; max := array[0];
      FOR i := 0 TO LEN(array) - 1 DO
         x := array[i];
         IF x < min THEN min := x ELSIF x > max THEN max := x END
      END;
      len := max - min + 1;
      U.StopTimer(t); U.PrintTime(t); StdLog.Ln;
      StdLog.String("k = "); StdLog.Int(len); StdLog.Ln;
      U.StartTimer(t); 
      NEW(b, len);
      U.StopTimer(t); U.PrintTime(t); StdLog.Ln;
      U.StartTimer(t);
      FOR i := 0 TO LEN(array) - 1 DO
         INC(b[array[i] - min])
      END;
      U.StopTimer(t); U.PrintTime(t); StdLog.Ln;
      U.StartTimer(t);
      j := 0;
      FOR i := min TO max DO
         k := b[i - min];
         WHILE k > 0 DO
            array[j] := i; INC(j); DEC(k)
         END
      END;
      U.StopTimer(t); U.PrintTime(t); StdLog.Ln;
      U.StopTimer(time)
   END Sort;

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 14:14

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Время на BB (под wine)

Код:

********** A1a **********
=== Тип 1 ===
n =  1000000
Время: 12.0 мс
k =  2000736
Время: 19.0 мс
Время: 19.0 мс
Время: 37.0 мс
Время: 87.0 мс

=== Тип 2 ===
n =  1000000
Время: 11.0 мс
k =  1999224
Время: 18.0 мс
Время: 21.0 мс
Время: 36.0 мс
Время: 86.0 мс

=== Тип 3 ===
n =  1000000
Время: 8.0 мс
k =  7999988
Время: 79.0 мс
Время: 251.0 мс
Время: 83.0 мс
Время: 421.0 мс

=== Тип 4 ===
n =  1000000
Время: 7.0 мс
k =  200001
Время: 4.0 мс
Время: 203.0 мс
Время: 12.0 мс
Время: 227.0 мс

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 14:16

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

На gcc c++

Код:

********** A1a **********
=== Тип 1 ===
n = 1000000
Время: 13.63 мс
k = 2501829
Время: 45.96 мс
Время: 24.96 мс
Время: 45.61 мс
Время: 132.31 мс
=== Тип 2 ===
n = 1000000
Время: 12.52 мс
k = 2501734
Время: 46.14 мс
Время: 24.62 мс
Время: 45.02 мс
Время: 131.03 мс
=== Тип 3 ===
n = 1000000
Время: 9.76 мс
k = 7999996
Время: 146.82 мс
Время: 249.90 мс
Время: 96.16 мс
Время: 508.61 мс
=== Тип 4 ===
n = 1000000
Время: 9.84 мс
k = 200001
Время: 3.58 мс
Время: 203.33 мс
Время: 15.13 мс
Время: 232.28 мс

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 14:17

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

На gcc c++ с оптимизацией (-O2)

Код:

********** A1a **********
=== Тип 1 ===
n = 1000000
Время: 6.00 мс
k = 2500270
Время: 34.79 мс
Время: 24.09 мс
Время: 23.44 мс
Время: 90.59 мс
=== Тип 2 ===
n = 1000000
Время: 5.59 мс
k = 2502455
Время: 34.63 мс
Время: 24.07 мс
Время: 23.72 мс
Время: 90.23 мс
=== Тип 3 ===
n = 1000000
Время: 3.25 мс
k = 7999998
Время: 112.08 мс
Время: 254.10 мс
Время: 44.02 мс
Время: 419.23 мс
=== Тип 4 ===
n = 1000000
Время: 3.20 мс
k = 200001
Время: 2.69 мс
Время: 211.58 мс
Время: 9.00 мс
Время: 226.87 мс

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 14:20

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Практика с теорией расходятся... Что играет роль?

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

Вернуться к началу

Trurl

Заголовок сообщения: Re: Сортировка подсчетом

Добавлено: Понедельник, 14 Май, 2007 17:11

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428

Евгений Темиргалеев писал(а):

n - число элементов в массиве. k - число различных элементов в массиве.
...
1) Упоряд-й по возр-ю, k > n

число различных элементов>число элементов

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 21:42

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Trurl, не изложите свою мысль поподробнее?

Вернуться к началу

Александр Ильин

Заголовок сообщения:

Добавлено: Понедельник, 14 Май, 2007 22:28

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск

Евгений Темиргалеев писал(а):

n - число элементов в массиве. k - число различных элементов в массиве.
...
1) Упоряд-й по возр-ю, k > n

Евгений Темиргалеев писал(а):

Trurl, не изложите свою мысль поподробнее?

Евгений, в цитате видно, что у вас число различных элементов массива (k) больше, чем число элементов этого самого массива (n). Как такое возможно? Даже если ВСЕ элементы массива различны, их число не может быть больше n.

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Вторник, 15 Май, 2007 00:04

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Гм, да, это я неправильно сформулировал. Исправил: k - длина отрезка, который вмещает элементы массива. k = maxEl - minEl + 1.

Вернуться к началу

Trurl

Заголовок сообщения:

Добавлено: Вторник, 15 Май, 2007 08:44

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428

Для k>>n это плохой алгоритм. Время на выделение памяти будет больше всего остального. Да и на своп попасть легко. Лучше сделать поразрядную сортировку.

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Вторник, 15 Май, 2007 10:37

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

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

Вернуться к началу

Trurl

Заголовок сообщения:

Добавлено: Вторник, 15 Май, 2007 13:10

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428

Кэш, конечно, сказывается на упорядоченных массивах, но где расхождение с теорией?

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Вторник, 15 Май, 2007 13:34

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Временная сложность алгоритма O(n+k)

Тип 1:
n = 1000000, k = 2000736, Время: 87.0 мс

Тип 4:
n = 1000000, k = 200001, Время: 227.0 мс

Вернуться к началу

Trurl

Заголовок сообщения:

Добавлено: Вторник, 15 Май, 2007 15:57

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428

Но ведь O(n+k) это асимптотика.
Формально это означает, что существуют с и M, такие, что T<=c*(n+k) для всех (n + k) > M. Никакого расхождения

Вернуться к началу

Евгений Темиргалеев

Заголовок сообщения:

Добавлено: Среда, 16 Май, 2007 09:06

Модератор

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл

Спасибо за разъяснение. В теории по оценке времени мне еще разбираться и разбираться. В мозгах никак не утрясется. Но как говорил герой одного японского мультика: "Учиться! Учиться!Учиться!"

Вернуться к началу

Страница 1 из 1

[ Сообщений: 16 ]

Список форумов » Разное » Другие вопросы по программированию

Часовой пояс: UTC + 3 часа

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

OberonCore

Сортировка подсчетом

Кто сейчас на конференции