Внешние сортировка и перестановка: различия между версиями

Сортировка и операции, подобные ей, составляют значительную долю компьютерных вычислений [9], при этом они находят множество применений в базах данных. Кроме того, сортировка является важной парадигмой при разработке эффективных EM-алгоритмов, как показано в [14], где можно найти несколько приложений. С некоторыми техническими оговорками, многие проблемы, которые могут быть легко решены за линейное время во внутренней памяти, такие как перестановка, ранжирование списка, оценка дерева выражений и поиск связных компонентов в разреженном графе, требуют такого же количества операций ввода-вывода в PDM, как и сортировка.

Несколько интересных задач остаются нерешенными. Одной из сложных теоретических проблем является доказательство нижних границ для перестановки и сортировки без предположения о неделимости. Другой вопрос заключается в том, как определить стоимость ввода-вывода для каждой отдельной перестановки как функцию некоторой простой характеристики перестановки, например, количества инверсий. Постоянной целью является разработка оптимальных EM-алгоритмов и перевод теоретических достижений в заметные улучшения в практическом применении. Любопытные проблемы и возможности в разработке и анализе алгоритмов возникают в связи с появлением новых архитектур, таких как сети рабочих станций, иерархические устройства хранения, дисковые накопители с возможностями обработки и устройства хранения на основе микроэлектромеханических систем (МЭМС). Недавно были предложены активные (или интеллектуальные) диски, в которых дисковые накопители имеют некоторые возможности обработки и могут фильтровать информацию, отправляемую на хост-компьютер, для «расширения» узкого места в виде операций ввода-вывода, особенно в масштабных приложениях баз данных. Энергонезависимая память на основе МЭМС может стать промежуточным уровнем в иерархии памяти между DRAM и дисками. В конечном итоге она может обеспечить лучшие по сравнению с дисками параметры задержки и пропускной способности при меньшей стоимости за бит, чем у DRAM.