МНОГОПОТОЧНАЯ СОРТИРОВКА ЭЛЕМЕНТОВ ДАННЫХ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ

1. Способ, содержащий:
разделение элементов данных в электронной таблице на множество блоков;
использование множества потоков для сортировки элементов данных в блоках;
после сортировки элементов данных в блоках использование посредством вычислительной системы множества потоков объединения для генерирования блока конечного результата, причем блок конечного результата содержит каждый из элементов данных в электронной таблице, каждый из потоков объединения является потоком, который объединяет два исходных блока для генерирования блока результата, каждый из исходных блоков является или одним из сортированных блоков, или одним из блоков результата, сгенерированных другим потоком объединения; и
отображение сортированной версии электронной таблицы, причем элементы данных в сортированной версии электронной таблицы упорядочены в соответствии с порядком элементов данных в блоке конечного результата.
2. Способ по п.1, дополнительно содержащий: определение подходящего количества блоков на основании минимального размера задания и количества блоков обработки в системе обработки,
в котором количество блоков во множестве блоков равно упомянутому подходящему количеству блоков, и
в котором количество элементов данных в каждом из блоков приблизительно равно.
3. Способ по п.1, дополнительно содержащий:
определение посредством вычислительной системы, превышает ли количество элементов данных в электронной таблице нижний предел; и
использование единственного потока для генерирования блока конечного результата, когда количество элементов данных в электронной таблице не превышает нижний предел.
4. Способ по п.1,
в котором один из потоков объединения является неполным внутренним потоком, когда количество блоков во множестве блоков является нечетным;
в котором способ дополнительно содержит: назначение одного из блоков на неполный внутренний поток; и
в котором блок результата, сгенерированный неполным внутренним потоком, содержит каждый из элементов данных в блоке результата, сгенерированном дочерним потоком неполного внутреннего потока, и блоке, назначенном на неполный внутренний поток, причем элементы данных в блоке результата, сгенерированном неполным внутренним потоком, упорядочены заданным образом.
5. Способ по п.4, в котором неполный внутренний поток выполняет по меньшей мере следующие действия:
определение, имеются ли какие-нибудь оставшиеся элементы данных в первом блоке, причем первый блок является блоком результата, сгенерированным дочерним потоком неполного внутреннего потока;
выполнение следующих действий, когда имеется один или более оставшихся элементов данных в первом блоке:
определение, имеются ли какие-нибудь оставшиеся элементы данных во втором блоке, причем второй блок назначается на неполный внутренний поток;
выполнение следующих действий, когда имеется один или более оставшихся элементов данных во втором блоке:
идентификация минимального элемента данных, причем минимальный элемент данных является наименьшим из оставшихся элементов данных в первом блоке и втором блоке; вставка минимального элемента данных в блок результата после наибольшего элемента данных в блоке результата, сгенерированном неполным внутренним потоком; и вставка, когда нет оставшихся элементов данных во втором блоке, любых оставшихся элементов данных в первом блоке, в блок результата, сгенерированный неполным внутренним потоком после наибольшего элемента данных в блоке результата, сгенерированном неполным внутренним потоком;
определение, когда нет оставшихся элементов данных во втором блоке, выполняется ли дочерний поток;
ожидание, когда дочерний поток не выполнен, пока дочерний поток не добавит другой элемент данных во второй блок; и
вставка, когда дочерний поток выполнен, любых оставшихся элементов данных во втором блоке в блок результата, сгенерированный неполным внутренним потоком, после наибольшего элемента данных в блоке результата, сгенерированном неполным внутренним потоком.
6. Способ по п.1, в котором потоки объединения включают в себя родительский поток, который начинает генерировать блок результата до того, как дочерние потоки родительского потока завершат генерирование своих блоков результата, причем дочерние потоки родительского потока являются другими потоками объединения.
7. Способ по п.1, в котором потоки объединения включают в себя листовой поток, который выполняет следующие действия:
определение, имеются ли какие-нибудь оставшиеся элементы данных в первом блоке, назначенном на листовой поток, причем первый блок является одним из сортированных блоков;
выполнение следующих действий, когда имеется один или более элементов данных в первом блоке:
определение, имеются ли какие-нибудь оставшиеся элементы данных во втором блоке, назначенном на листовой поток, причем второй блок является другим, одним из сортированных блоков;
выполнение следующих действий, когда имеется один или более элементов данных во втором блоке:
идентификация минимального элемента данных, причем минимальный элемент данных является наименьшим из оставшихся элементов данных в первом блоке и втором блоке; и вставка минимального элемента данных в блок результата, сгенерированный листовым потоком после наибольшего элемента данных в блоке результата;
вставка, когда нет оставшихся элементов данных во втором блоке, любых оставшихся элементов данных в первом блоке в блок результата, сгенерированный листовым потоком, после наибольшего элемента данных в блоке результата, сгенерированном листовым потоком; и
вставка, когда нет оставшихся элементов данных в первом блоке, любых оставшихся элементов данных во втором блоке в блок результата после наибольшего элемента данных в блоке результата, сгенерированном листовым потоком.
8. Способ по п.7, в котором листовой поток выполняет следующие действия в ответ на пробуждение:
определение, является ли наибольший элемент данных в первом блоке меньшим, чем наименьший элемент данных во втором блоке;
выполнение, когда наибольший элемент данных в первом блоке является меньшим, чем наименьший элемент данных во втором блоке, по меньшей мере следующих действий без сравнения дополнительных элементов данных в первом блоке и втором блоке:
вставка элементов данных в первом блоке в блок результата, сгенерированный листовым потоком; и вставка элементов данных во втором блоке в блок результата после того, как наибольший элемент данных в блоке результата сгенерирован листовым потоком;
определение, является ли наибольший элемент данных во втором блоке меньшим, чем наименьший элемент данных в первом блоке; и выполнение, когда наибольший элемент данных во втором блоке является меньшим, чем наименьший элемент данных в первом блоке, по меньшей мере следующих действий без сравнения дополнительных элементов данных в первом блоке и втором блоке:
вставка элементов данных во втором блоке в блок результата, сгенерированный листовым потоком; и
вставка элементов данных в первом блоке в блок результата после наибольшего элемента данных в блоке результата, сгенерированном листовым потоком.
9. Способ по п.1, в котором электронной таблицей является сводная таблица.
10. Вычислительная система, содержащая:
систему обработки, содержащую множество блоков обработки; и
систему хранения данных, содержащую считываемые компьютером команды, которые при выполнении одного или более блоков обработки вынуждают вычислительную систему:
разделять элементы данных в электронной таблице на множество блоков;
использовать множество потоков сортировки блоков для сортировки элементов данных в блоках, в которых количество потоков сортировки блок равно количеству блоков;
после того, как элементы данных в блоках сортированы, использовать множественные потоки объединения для генерирования блока конечного результата, причем блок конечного результата содержит каждый из элементов данных в электронной таблице, каждый из потоков объединения является потоком, который объединяет два исходных блока для генерирования блока результата, каждый из исходных блоков является или одним из сортированных блоков, или одним из блоков результата, сгенерированным другим потоком объединения; и
отображать сортированную версию электронной таблицы, причем элементы данных в сортированной версии электронной таблицы упорядочены в соответствии с порядком элементов данных в блоке конечного результата.
11. Вычислительная система по п.10, в которой считываемые компьютером команды при выполнении одним или более блоками обработки вынуждают вычислительную систему определять подходящее количество блоков на основании минимального размера задания и количества блоков обработки в системе обработки;
в которой количество блоков во множестве блоков равно упомянутому подходящему количеству блоков,
в которой количество элементов данных в каждом из блоков приблизительно равно.
12. Вычислительная система по п.10, в которой считываемые компьютером команды при выполнении одним или более блоками обработки вынуждают вычислительную систему:
определять, превышает ли количество элементов данных в электронной таблице нижний предел; и
использовать единственный поток для генерирования блока конечного результата, когда количество элементов данных в электронной таблице не превышает нижний предел.
13. Вычислительная система по п.10,
в которой потоки объединения включают в себя неполный внутренний поток, когда количество блоков во множестве блоков является нечетным;
в которой считываемые компьютером команды при выполнении одним или более блоками обработки дополнительно вынуждают вычислительную систему назначать один из блоков на неполный внутренний поток; и
в которой неполный внутренний поток генерирует блок результата, который содержит каждый из элементов данных в блоке результата, сгенерированном дочерним потоком неполного внутреннего потока, и блоке, назначенном на неполный внутренний поток, причем элементы данных в блоке результата, сгенерированном неполным внутренним потоком, упорядочены заданным образом, при этом дочерний поток является другим, одним из потоков объединения.
14. Вычислительная система по п.10, в которой потоки объединения включают в себя родительский поток, который начинает генерировать блок результата до того, как дочерние потоки этого родительского потока будут завершены посредством генерирования их блоков результата, причем дочерние потоки родительского потока являются другими потоками из потоков объединения.
15. Считываемый компьютером носитель данных, имеющий считываемые компьютером команды, хранящиеся на нем, причем считываемые компьютером команды при выполнении одним или более блоками обработки в системе обработки вычислительной системы вынуждают вычислительную систему:
определять, превышает ли количество строк в сводной таблице нижний предел;
использовать единственный поток для генерирования блока конечного результата, когда количество строк в сводной таблице не превышает нижний предел, причем блок конечного результата содержит каждую из строк в сводной таблице, строки упорядочены заданным образом в блоке конечного результата;
выполнять следующие действия, когда количество строк в сводной таблице превышает нижний предел:
определять подходящее количество блоков на основании количества строк в сводной таблице и количества блоков обработки в системе обработки,
разделять строки в сводной таблице на множество блоков, при этом количество блоков в упомянутом множестве блоков равно этому подходящему количеству блоков, причем количество строк в каждом из блоков приблизительно равно; использовать множество потоков сортировки блока для сортировки блоков таким образом, чтобы строки в блоках были упорядочены заданным образом;
генерировать дерево потоков, причем дерево потоков содержит множество потоков объединения;
назначать два из блоков на каждый листовой поток в дереве потоков; и пробуждать каждый поток объединения в наборе потоков объединения,
при этом каждый листовой поток в дереве потоков генерирует блок результата, который содержит каждую из строк в блоках, назначенных на листовой поток, причем строки в блоке результата, сгенерированном листовым потоком, упорядочены заданным образом, при этом каждый полный внутренний поток в дереве потоков генерирует блок результата, который содержит каждую из строк в блоках результата, сгенерированных дочерними потоками полного внутреннего потока, строки в блоке результата, сгенерированного полным внутренним потоком, упорядочены заданным образом;
причем блоком конечного результата является блок результата, сгенерированный корневым потоком в дереве потоков, при этом корневой поток является потоком, не имеющим родительских потоков в дереве потоков; и
отображать сортированную версию электронной таблицы, причем элементы данных в сортированной версии электронной таблицы упорядочены в соответствии с порядком элементов данных в блоке конечного результата.