OberonCore https://forum.oberoncore.ru/ |
|
Сортировка подсчетом https://forum.oberoncore.ru/viewtopic.php?f=27&t=464 |
Страница 1 из 1 |
Автор: | Евгений Темиргалеев [ Понедельник, 14 Май, 2007 14:11 ] |
Заголовок сообщения: | Сортировка подсчетом |
Разбираю различные алгоритмы сортировки. Один из простейших - сортировка подсчетом. Есть различные вариации. Я смотрел в 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) |
Автор: | Евгений Темиргалеев [ Понедельник, 14 Май, 2007 14:13 ] |
Заголовок сообщения: | |
Код: 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 ] |
Заголовок сообщения: | |
Время на 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 ] |
Заголовок сообщения: | |
На 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 ] |
Заголовок сообщения: | |
На 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 ] |
Заголовок сообщения: | |
Практика с теорией расходятся... Что играет роль? Я думаю, что при работе с упоряд-ми массивами, поскольку идет обращение по возр-м (уб-м) индексам играет роль кэш МП, которыей и ускоряет процесс. |
Автор: | Trurl [ Понедельник, 14 Май, 2007 17:11 ] |
Заголовок сообщения: | Re: Сортировка подсчетом |
Евгений Темиргалеев писал(а): n - число элементов в массиве. k - число различных элементов в массиве.
... 1) Упоряд-й по возр-ю, k > n число различных элементов>число элементов |
Автор: | Евгений Темиргалеев [ Понедельник, 14 Май, 2007 21:42 ] |
Заголовок сообщения: | |
Trurl, не изложите свою мысль поподробнее? |
Автор: | Александр Ильин [ Понедельник, 14 Май, 2007 22:28 ] |
Заголовок сообщения: | |
Евгений Темиргалеев писал(а): n - число элементов в массиве. k - число различных элементов в массиве. ... 1) Упоряд-й по возр-ю, k > n Евгений Темиргалеев писал(а): Trurl, не изложите свою мысль поподробнее?
Евгений, в цитате видно, что у вас число различных элементов массива (k) больше, чем число элементов этого самого массива (n). Как такое возможно? Даже если ВСЕ элементы массива различны, их число не может быть больше n. |
Автор: | Евгений Темиргалеев [ Вторник, 15 Май, 2007 00:04 ] |
Заголовок сообщения: | |
Гм, да, это я неправильно сформулировал. Исправил: k - длина отрезка, который вмещает элементы массива. k = maxEl - minEl + 1. |
Автор: | Trurl [ Вторник, 15 Май, 2007 08:44 ] |
Заголовок сообщения: | |
Для k>>n это плохой алгоритм. Время на выделение памяти будет больше всего остального. Да и на своп попасть легко. Лучше сделать поразрядную сортировку. |
Автор: | Евгений Темиргалеев [ Вторник, 15 Май, 2007 10:37 ] |
Заголовок сообщения: | |
Да, так. Просто я сейчас прорешиваю лабораторные из курса "Сортировка и Поиск". Студенты на практике должны увидеть подтверждение теории. А тут, вступил в игру неучтенный фактор - кэш МП (как мне кажется). Вот именно этот вопрос я и хотел обсудить. |
Автор: | Trurl [ Вторник, 15 Май, 2007 13:10 ] |
Заголовок сообщения: | |
Кэш, конечно, сказывается на упорядоченных массивах, но где расхождение с теорией? |
Автор: | Евгений Темиргалеев [ Вторник, 15 Май, 2007 13:34 ] |
Заголовок сообщения: | |
Временная сложность алгоритма O(n+k) Тип 1: n = 1000000, k = 2000736, Время: 87.0 мс Тип 4: n = 1000000, k = 200001, Время: 227.0 мс |
Автор: | Trurl [ Вторник, 15 Май, 2007 15:57 ] |
Заголовок сообщения: | |
Но ведь O(n+k) это асимптотика. Формально это означает, что существуют с и M, такие, что T<=c*(n+k) для всех (n + k) > M. Никакого расхождения . |
Автор: | Евгений Темиргалеев [ Среда, 16 Май, 2007 09:06 ] |
Заголовок сообщения: | |
Спасибо за разъяснение. В теории по оценке времени мне еще разбираться и разбираться. В мозгах никак не утрясется. Но как говорил герой одного японского мультика: "Учиться! Учиться!Учиться!" |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |