OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 25 Сентябрь, 2020 05:50

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




Начать новую тему Ответить на тему  [ Сообщений: 16 ] 
Автор Сообщение
 Заголовок сообщения: Сортировка подсчетом
СообщениеДобавлено: Понедельник, 14 Май, 2007 14:11 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4593
Откуда: Россия, Орёл
Разбираю различные алгоритмы сортировки. Один из простейших - сортировка подсчетом. Есть различные вариации. Я смотрел в 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
Сообщения: 4593
Откуда: Россия, Орёл
Код:
   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
Сообщения: 4593
Откуда: Россия, Орёл
Время на 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
Сообщения: 4593
Откуда: Россия, Орёл
На 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
Сообщения: 4593
Откуда: Россия, Орёл
На 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
Сообщения: 4593
Откуда: Россия, Орёл
Практика с теорией расходятся... Что играет роль?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка подсчетом
СообщениеДобавлено: Понедельник, 14 Май, 2007 17:11 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1298
Евгений Темиргалеев писал(а):
n - число элементов в массиве. k - число различных элементов в массиве.
...
1) Упоряд-й по возр-ю, k > n

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Понедельник, 14 Май, 2007 21:42 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4593
Откуда: Россия, Орёл
Trurl, не изложите свою мысль поподробнее?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Понедельник, 14 Май, 2007 22:28 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2352
Откуда: Россия, Томск
Евгений Темиргалеев писал(а):
n - число элементов в массиве. k - число различных элементов в массиве.
...
1) Упоряд-й по возр-ю, k > n

Евгений Темиргалеев писал(а):
Trurl, не изложите свою мысль поподробнее?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 15 Май, 2007 00:04 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4593
Откуда: Россия, Орёл
Гм, да, это я неправильно сформулировал. Исправил: k - длина отрезка, который вмещает элементы массива. k = maxEl - minEl + 1.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 15 Май, 2007 08:44 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1298
Для k>>n это плохой алгоритм. Время на выделение памяти будет больше всего остального. Да и на своп попасть легко. Лучше сделать поразрядную сортировку.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 15 Май, 2007 10:37 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4593
Откуда: Россия, Орёл
Да, так. Просто я сейчас прорешиваю лабораторные из курса "Сортировка и Поиск". Студенты на практике должны увидеть подтверждение теории. А тут, вступил в игру неучтенный фактор - кэш МП (как мне кажется). Вот именно этот вопрос я и хотел обсудить.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 15 Май, 2007 13:10 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1298
Кэш, конечно, сказывается на упорядоченных массивах, но где расхождение с теорией?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 15 Май, 2007 13:34 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4593
Откуда: Россия, Орёл
Временная сложность алгоритма O(n+k)

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 15 Май, 2007 15:57 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Среда, 16 Май, 2007 09:06 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4593
Откуда: Россия, Орёл
Спасибо за разъяснение. В теории по оценке времени мне еще разбираться и разбираться. В мозгах никак не утрясется. Но как говорил герой одного японского мультика: "Учиться! Учиться!Учиться!" :)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ] 

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


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

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


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

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2020, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB