Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

ABC-сортировка

Anna | 24.06.2014 | нет комментариев

Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Однако, алгорифм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик предпочел наименование в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.

Сам по себе Бичик знаменателен тем, что он не только программист, а ещё и целый магистр богословия. Опеки по упорядочиванию неотсортированных данных волнуют его только в рамках мирской профессии. Куда больше уважаемого теолога беспокоит наведение порядка в хаосе современного социума, намедни Вознесения для правдиво верующих и Ужасного Суда для всех остальных.Что касается алгорифма, то это единственно знаменитая мне сортировка, за применение которой её изобретатель требует деньги.

Бичик

Баптист-консерватор, ярый противник претеризма. Протестантская ересь разгромлена Алленом ещё 30 лет назад в его неугасаемом бестселлере «Вознесение в преддверии Великой Скорби» («The Pre-Tribulation Rapture», 1980 г., переиздание в 1999 г.). Выводом многолетних религиозных исследований нашего героя является книга «Отгадка Вознесения – соберём паззл совместно» («The Rapture Solution, Putting the Puzzle Together»).

Превосходства

Автору дюже нравится хвалить свой алгорифм и он с нескрываемым удовольствием на сайте сортировкиперечисляет её бесчисленные превосходства:

  • В среднем в 2-3 раза стремительней чем стремительная сортировка, в зависимости от списка.
  • Стабильность.
  • Нет вырожденных случаев.
  • Не использует сопоставлений.
  • Не использует обменов.
  • Не использует опорные элементы.
  • Работает идентично отлично с короткими и с длинными списками.
  • Экономична по памяти.
  • Первые отсортированные элементы теснее доступны для применения в других процессах, пока сортируется оставшаяся часть списка (другими словами – сортировка устойчива).

В всеобщем-то, всё вышеперечисленное соответствует реальности. Правда, взамен сопоставлений, обменов и опорных элементов дозволено было сказать проще – это сортировка разделением. Ну и насчёт «экономичности по памяти» тоже дозволено подискутировать (но об этом позднее).

Чем ещё классна сортировка – в различие от классической MSD-radix sort сортирует не по каждому разрядам. Процесс прекращается сразу как только список будет отсортирован, а не до тех пор пока не обработаются все разряды. Так же дозволено указать число первых разрядов по которым произведётся упорядочивание, если старшинство по младшим разрядам не имеет специального значения.

Алгорифм

Для сортировки требуется два вспомогательных массива.

Один из них назовём трекер слов (WT – word tracker), с поддержкой него мы будем группировать слова, имеющих идентичные буквы в i-м разряде. Для самого первого обнаруженного такого слова в списке заносится значение 0. Для всякого дальнейшего обнаруженного слова с той же буквой в i-м разряде в трекере слов отмечается индекс предыдущего слова, соответствующего этому же знаку.

В приведённой таблице показан 1-й этап сортировки, когда слова группируются по первой букве. В процессе сортировки, когда происходит переход от разряда к разряду значения в этом массиве меняются, отражая цепочки слов, начинающихся с одной буквы и имеющие идентичные литеры в том либо другом месте.

Ещё один массив – трекер символов (LT – letter tracker). В нём отмечаются индексы самого первого (либо последнего) слова в списке, в котором в соответствующем разряде находится определённый символ. Отталкиваясь от этого слова, с поддержкой трекера слов восстанавливается цепочка всех остальных лексем, имеющих в i-м разряде соответствующую букву.

Теперь в таблице приведены индексы последних слов из списка, которые начинаются с той либо другой буквы.

В данных момент с поддержкой этих 2-х таблиц дозволено вытянуть все слова, к примеру, начинающиеся на букву «B». Для этого необходимо взять значение ячейки LT[1, b] = 9 – это индекс последнего слова из списка начинающегося на «b» — Beckie. У данного слова в трекере слов трек-значение теперь: WT[9] = 8. Это индекс предыдущего слова на «b» — Belinda. В ячейке WT[8] хранится значение 6 – под этим индексом обнаруживается Barbara, которая в свою очередь указывает на индекс Beatrix: WT[6] = 3. Трек-значение для Beatrix равно нулю, то есть касательно неё в списке нет предыдущих слов начинающихся на B.

Создавая и прослеживая сходственные цепочки слов, рекурсивно продвигаясь от больше старших разрядов к больше младшим, в выводе крайне стремительно формируются новые последовательности, упорядоченные в алфавитном порядке. Отсортировав слова на «A», после этого сортируется «B», после этого «C» и дальше по алфавиту.

Демо-код на C (автор – Линн Д. Ярбро)

/*            
 ** ABCsort на C
 ** Представленный в данной программе алгорифм сортировки является собственностью
 ** Аллена Бичика (Allen Beechick) и находится под охраной права США, 
 ** Патент №5218700.
 ** Применение данного алгорифма без разрешения обладателя запрещено законом.
 ** Автором этой программы является:
 ** Линн Д. Ярбро (Lynn D. Yarbrough)
 ** Палм Десерт (Palm Desert), Калифорния  

 **====================================================================== 
*/ 

	#include <malloc.h> 
	#include <stdio.h> 
	#include <stdlib.h> 

	long *RT;  /* Таблица записей */
	long **LT; /* Таблица символов */

	void ABCsort (int keys) { /* число используемых ключевых полей */ 

		void process (int, int); 
		long register i, j, recno; 
		int register c; 
		int nodup = noduplicates; 
		long start, step, stop; 

		/* Выделяем хранилища под внутренние таблицы */ 
		LT = lmatrix(1, keys, alphamin, alphamax); 
		RT = lvector(1, N); 

		/* Инициализация таблицы символов: */ 
		for (j = alphamin; j <= alphamax; j  ) { 
			for (i = 1; i <= keys; i  ) 
				LT[i][j] = 0; 
		} 

		/* Обеспечиваем устойчивость сортировки */ 
		if ((keys & 1) ^ nodup) {
			start = N; stop = 0; step = -1;
		} else {
			start = 1; 
			stop = N   1; 
			step = 1;
		}

		/* Этап 1 */
		/* Группируем слова по первой букве */
		for (recno = start; recno != stop; recno  = step) { 
			c = GetNextField(recno, 1); 
			RT[recno] = LT[1][c]; 
			LT[1][c] = recno; 
		}		

		/* Запускаем процесс уточнения расположения записей в списке. */		
		process(1, keys); 	

		free_lmatrix(LT, 1, keys, alphamin, alphamax); 
		free_lvector(RT, 1, N); 

	} 

	/* ======================================================== */ 

	/* Функция обработки данных позже 1-го этапа: */ 
	/* Перегруппировываем слова, переходя от одной буквы к дальнейшей */
	void process (int level, int keys) { 

		long i, newlevel, nextrec, recno; 
		int nodup = noduplicates; 
		unsigned char c; 

		/* Цикл по алфавиту */
		for (i = alphamin; i <= alphamax; i  ) {

			/* Ищем применение i-й буквы */ 
			recno = LT[level][i]; 
			LT[level][i] = 0; 

			/* Сканируем ветвь для этой буквы */ 
			while (recno != 0) {
				/* i-й символ применяется только некогда, значит  
				отсортированная часть массива пополнилась новым элементом */ 
				if (RT[recno] == 0) {				
					PutCurrRecord(recno); 
					recno = 0; 
					continue; 
				} else {
					/* В случае многократного применения i-го символа: */ 
					if (level == keys) {
						/* Итог всех данных на этом ярусе: */ 
						while (recno != 0) {
							/* Добавляем нынешнюю запись в таблицу индексов */ 
							PutCurrRecord(recno); 
							recno = RT[recno]; 
							if (nodup) recno = 0; 
						} 
					} else { 
						/* Продолжать уточнять порядок слов:*/ 
						/* опускаемся на ярус вниз */ 						
						newlevel = level   1; 
						while (recno != 0) { 
							nextrec = RT[recno]; 
							c = GetNextField(recno, newlevel); 
							RT[recno] = LT[newlevel][c]; 
							LT[newlevel][c] = recno; 
							recno = nextrec; 
						}  
						/* Продолжаем процесс уточнения */ 
						process(newlevel, keys); 
					} 
				} 
			} 
		} 
	} 

Youtube-версия анимации

Трудность по времени

В целом дозволено уверенно говорить о временной трудности O(n).

Компания «ASIC DESIGN & MARKETING», занимающаяся разработкой интегральных микросхем, имплементировала алгорифм при создании ППВМ (Программируемых пользователем вентильных матриц). По заявлению инженеров компании, ABCsort работает от 2,5 до 10 раз стремительней чем QuickSort. Об этом дозволено почитать в этом PDF-отчёте.

Трудность по памяти

Для сортировки понадобится два вспомогательных массива: двухмерный для трекера символов, которым при оценке трудности дозволено пренебречь. А также массив из n элементов для трекера слов. То есть, всеобщая оценка дополнительной памяти: O(n).

Цена

Если Вам приглянулся алгорифм, то не спешите запускать его в продакшен, не уплатив обладателю отступных. Метод запатентован (ссылка на pdf патента) и за его пиратское применение на похитителя обрушится карающий меч заокеанского правосудия.

Цена за сортировку абсолютно божеская, 49 баксов. За эту сумму удовлетворенный заказчик получает:

  • BeechickSort.dll. Здесь содержится функция сортировки которую дозволено вызывать из всякий программы.
  • BeechickSortDemo.exe а также сорцы к ней – BeechickSortDemo.cpp.
  • Примеры начальных данных для сортировки: SchoolAddresses.txt (записи с несколькими полями, сортировать дозволено по-различному) и ShuffledText.txt (комплект случайных слов из словаря).
  • SortDemo.htm – веб-интерфейс для задания параметров сортировки.

Если накинуть сверху 39 условных единиц, то DLL-ку отдадут с прокомментированными исходниками на C .

Также деятельный религиовед-программист божится, что если ABCsort не окажется правда бы вдвое стремительней чем Quick sort, то он без разговоров вернёт деньги.

Тем, у кого остались вопросы по поводу патента, Аллен Бичик даёт исчерпывающие результаты:

Может, стоит продать алгорифм Microsoft?

Я пытался. Это было до того как я получил патент. Ребята из “Microsoft” сказали, что запатентовать не получится, от того что это очередная разновидность поразрядной сортировки; к тому же, она их не впечатлила. Но в патентном ведомстве рассмотрели уникальность алгорифма.

Отчего бы Вам не передать алгорифм в социальное наследие? 

Патентный представитель не работает за легко так. Правительственная служба не выдаёт патенты даром. Так что, недурно воротить правда бы часть потраченных из собственного кармана средств.

Колляции алгорифма

Наименование ABC-сортировка (ABCsort, Allen Beechick Character sort); Сортировка Бичика (Beechick sort)
Автор Аллен Бичик (Allen Beechick)
Год публикации 1993
Класс Сортировка разделением
Подкласс Поразрядная сортировка
Стабильность Устойчивая
Сопоставления Без сопоставлений
Временная трудность O(n)
Трудность по памяти O(n)

Ссылки

Сайт сортировки
Реализация Лина Д. Ярбро
Патент на алгорифм (pdf)
Аппаратная реализация в интегральных миксросхемах (pdf)

Аллен Бичик

На Фейсбуке
На LinkedIn
Сайт книги «Отгадка Вознесения – соберём паззл совместно»
«Who’s who in Bible Prophecy. A list of popular teachers and scholars»

Голосование

Считаете ли Вы возможным патентование компьютерных алгорифмов с дальнейшим требованием роялти?

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Проголосовал 1 человек. Воздержавшихся нет.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB