МНОГОПОТОЧНАЯ СОРТИРОВКА ЭЛЕМЕНТОВ ДАННЫХ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ Российский патент 2016 года по МПК G06F9/06 G06F7/22 

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

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

[0002] В больших электронных таблицах процесс сортировки строк в электронной таблице может быть относительно медленным. Такие задержки обработки могут нарушить ход мыслей пользователя или препятствовать пользователю сортировать строки в электронной таблице. Следовательно, желательно сделать процесс сортировки строк в электронной таблице настолько быстрым, насколько это возможно.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0003] Процесс сортировки выполнен в электронной таблице. В процессе сортировки элементы данных в электронной таблице разделены на множество блоков. Множество потоков использованы для сортировки элементов данных в блоках. После того как элементы данных в блоках отсортированы, множество объединенных потоков используются для генерирования блока конечного результата. Блок конечного результата содержит каждый из элементов данных в электронной таблице. Каждый из объединенных потоков является потоком, который объединяет два исходных блока для генерирования блока результата. Каждый из исходных блоков является или одним из отсортированных блоков, или одним из блоков результата, сгенерированных другим одним из объединенных потоков. Отсортированная версия электронной таблицы затем отображается. Элементы данных в отсортированной версии электронной таблицы упорядочиваются в соответствии с порядком элементов данных в блоке конечного результата.

[0004] Эта сущность изобретения предоставляется для ввода выбора понятий. Эти понятия дополнительно описаны ниже в подробном описании. Данная сущность изобретения не предназначена для идентификации ключевых особенностей или существенных признаков заявленного объекта изобретения, и при этом эта сущность изобретения не предназначена в качестве помощи в определении объема заявленного объекта изобретения.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0005] Фиг. 1 является блок-схемой, иллюстрирующей пример вычислительной системы.

[0006] Фиг. 2 является блок-схемой, иллюстрирующей примерный альтернативный вариант осуществления вычислительной системы.

[0007] Фиг. 3 является последовательностью операций, иллюстрирующей примерную работу для сортировки электронной таблицы.

[0008] Фиг. 4 является диаграммой, показывающей примерное дерево потоков.

[0009] Фиг. 5 является последовательностью операций, иллюстрирующей примерную операцию, выполняемую листовым потоком во время фазы объединения процесса сортировки.

[0010] Фиг. 6 является последовательностью операций, иллюстрирующей примерную операцию, выполняемую неполным внутренним потоком.

[0011] Фиг. 7 является последовательностью операций, иллюстрирующей примерную операцию, выполняемую полным внутренним потоком.

[0012] Фиг. 8 является последовательностью операций, иллюстрирующей примерную операцию, выполняемую потоком управления памятью во время фазы объединения процесса сортировки.

[0013] Фиг. 9 является блок-схемой, иллюстрирующей примерное вычислительное устройство.

ПОДРОБНОЕ ОПИСАНИЕ

[0014] Фиг. 1 является блок-схемой, иллюстрирующей примерную вычислительную систему 100. Вычислительная система 100 является системой, содержащей одно или более вычислительных устройств. Как используется в настоящем описании, вычислительное устройство является физическим материальным устройством, которое обрабатывает информацию. В различных вариантах осуществления вычислительная система 100 содержит различные типы вычислительных устройств. Например, вычислительная система 100 может содержать один или более настольных компьютеров, ноутбуков, нетбуков, карманных вычислительных устройств, смартфонов, автономных серверов, сверхкомпактных серверов, универсальных компьютеров, суперкомпьютеров и/или других типов вычислительных устройств. В вариантах осуществления, где вычислительная система 100 содержит более чем одно вычислительное устройство, вычислительные устройства в вычислительной системе 100 могут быть распределены по различным местоположениям и связываться с помощью системы связи, такой как Интернет или локальная сеть.

[0015] Как иллюстрировано в примере на фиг. 1, вычислительная система 100 содержит систему 102 хранения данных, систему 104 обработки и систему 106 отображения. Должно быть оценено, что в других вариантах осуществления вычислительная система 100 включает в себя больше или меньше компонентов, чем иллюстрированы в примере на фиг. 1. Кроме того, должно быть оценено, что фиг. 1 показывает вычислительную систему 100 в упрощенной форме для простоты понимания.

[0016] Система 102 хранения данных является системой, содержащей один или более считываемых компьютером носителей данных. Считываемым компьютером носителем данных является физическое устройство или продукт изготовления, который способен хранить данные энергозависимым или энергонезависимым способом. В некоторых вариантах осуществления система 102 хранения данных содержит один или более считываемых компьютером носителей данных, которые являются непереносными. Примерные типы считываемых компьютером носителей данных включают в себя оперативное запоминающее устройство (RAM), постоянное запоминающее устройство (ROM), запоминающее устройство на оптических дисках (например, CD-ROM, DVD, диски BluRay, диски HDDVD и т.д.), на магнитных дисках (например, жесткие диски, дискеты и т.д.), устройства твердотельной памяти (например, устройства флэш-памяти), памяти EEPROM, программируемые пользователем вентильные матрицы и так далее. В некоторых вариантах осуществления, где система 102 хранения данных содержит более чем один считываемый компьютером носитель данных, считываемые компьютером носители данных распределяются по различным географическим местоположениям.

[0017] Система 102 хранения данных хранит считываемые компьютером команды, представляющие приложение 108 электронной таблицы. В некоторых вариантах осуществления, где система 102 хранения данных содержит более чем один считываемый компьютером носитель данных, считываемые компьютером команды, представляющие приложение 108 электронной таблицы, распределяются по двум или более считываемым компьютером носителям данных. В других вариантах осуществления, где система 102 хранения данных содержит более чем один считываемый компьютером носитель данных, считываемые компьютером команды, представляющие приложение 108 электронной таблицы, сохраняются только на одном из считываемых компьютером носителей данных.

[0018] Система 104 обработки является системой, содержащей множество блоков 110A-110N обработки (все вместе "блоки 110 обработки"). В различных вариантах осуществления система 104 обработки содержит разное количество блоков обработки. Например, система 104 обработки может содержать один, два, четыре, восемь, шестнадцать, тридцать два, шестьдесят четыре или другое количество блоков обработки. Каждый из блоков 110 обработки является физической интегральной схемой. Каждый из блоков 110 обработки выполняет считываемые компьютером команды асинхронно от других блоков 110 обработки. В результате, блоки 110 обработки могут независимо выполнять считываемые компьютером команды параллельно друг другу. В некоторых вариантах осуществления один или более блоков 110 обработки может индивидуально выдавать два или более логических блоков обработки. Считываемые компьютером команды могут независимо работать на логических блоках обработки и могут иначе работать как реальные блоки обработки.

[0019] Система 106 отображения является системой, используемой системой 104 обработки для отображения информации пользователю. В различных вариантах осуществления система 106 отображения отображает информацию пользователю различными способами. Например, в некоторых вариантах осуществления система 106 отображения содержит графический интерфейс и монитор.

[0020] Блоки 110 обработки в системе 104 обработки выполняют считываемые компьютером команды, которые представляют приложение 108 электронной таблицы. Считываемые компьютером команды, которые представляют приложение 108 электронной таблицы, при выполнении блоками 110 обработки вынуждают вычислительную систему 100 предоставлять приложение 108 электронной таблицы. Приложение 108 электронной таблицы позволяет пользователю просматривать и манипулировать одной или более электронными таблицами. Электронные таблицы являются данными, которые организованы в качестве таблицы, имеющей одну или более строк и одну или более колонок. Электронная таблица может содержать различные типы данных. Например, табличные данные могут быть коммерческими данными, данными учета, военными данными, данными выставления счетов, статистическими данными, популяционными данными, демографическими данными, финансовыми данными, медицинскими данными, спортивными данными, научными данными или любым другим типом поддающихся сортировке данных, которые могут быть представлены в таблице.

[0021] Ячейки в электронной таблице могут содержать значения, имеющие различные типы данных. Например, значения в ячейках могут быть целыми числами, действительными числами, числами с плавающей запятой, алфавитно-цифровыми текстовыми строками, датами, денежно-кредитными числами, нулевыми значениями и так далее. В дополнение к значениям в ячейках, каждая из ячеек может иметь множество других свойств. Например, каждая из ячеек может иметь свойство цвета фона, свойство цвета шрифта, одно или более свойств флага, свойство видимости, свойство стиля шрифта, свойство размера шрифта и так далее.

[0022] Приложение 108 электронной таблицы в состоянии использовать множество потоков для выполнения процесса сортировки в электронной таблице. Потоком является часть программы, которая может работать независимо от и одновременно с другими частями программы. Процесс сортировки может быть выполнен по отношению к строкам или колонкам электронной таблицы. Для простоты объяснения этот документ рассматривает выполнение операции сортировки по отношению к строкам электронной таблицы. Однако должно быть оценено, что, если иначе не обозначено, рассмотрение в этом документе относительно строки одинаково применяется к колонкам. Термин "элемент данных" используется в этом документе для ссылки, в общем, на строку или колонку.

[0023] Процесс сортировки сортирует строки в электронной таблице. В различных случаях электронная таблица может быть полной таблицей в электронной таблице, части таблицы или другом типе электронной таблицы. Кроме того, в некоторых вариантах осуществления пользователь приложения 108 электронной таблицы выбирает электронную таблицу.

[0024] Кроме того, в некоторых вариантах осуществления электронная таблица может быть сводной таблицей. Сводная таблица является электронной таблицей, которая суммирует один или более других табличных наборов данных, таких как электронные таблицы, таблицы реляционных баз данных, кубы данных онлайновой аналитической обработки (OLAP), другие типы многомерных наборов данных и другие типы табличных наборов данных. В некоторых вариантах осуществления пользователь в состоянии составить сводную таблицу посредством выбора строки c обозначением колонки и колонки с обозначением колонки в исходной таблице. Значения в ячейках в строке с обозначением колонки становятся обозначениями строки сводной таблицы. Значения в ячейках колонки с обозначением колонки становятся обозначениями колонки сводной таблицы. Значение в каждой ячейке сводной таблицы вычисляется из значений ячеек в колонке с обозначением колонки, которые имеют то же самое значение, что и обозначение строки у строки сводной таблицы, содержащей ячейку сводной таблицы. Сводная таблица может также включать в себя ячейки, которые имеют значения, вычисленные из значений в ячейках сводной таблицы. Например, сводная таблица может включать в себя ячейки, содержащие общие количества или счет значений в колонках или строках сводной таблицы. В некоторых вариантах осуществления пользователи также в состоянии составить сводные таблицы посредством выбора строк исходной таблицы вместо колонок исходной таблицы.

[0025] В некоторых вариантах осуществления пользователь в состоянии выбрать две или более колонок с обозначением строки и колонку с обозначением колонки. В таких вариантах осуществления комбинации значений в ячейках колонок с обозначением строки становятся обозначениями строк у строк в сводной таблице и значения ячеек в колонке с обозначением колонки становятся обозначениями колонки в сводной таблице.

[0026] В некоторых вариантах осуществления электронная таблица может включать в себя скрытые строки. Скрытой строкой является строка, которая находится в электронной таблице, но не видна пользователю приложения 108 электронной таблицы. Пользователь может захотеть скрыть конкретные строки для упрощения представления электронной таблицы. В таких вариантах осуществления процесс сортировки сортирует скрытые, а также видимые строки в электронной таблице.

[0027] Сортировка строк в электронной таблице содержит манипулирование порядком строк в электронной таблице таким образом, чтобы строки в электронной таблице располагались заданным образом. Строки в электронной таблице располагаются заданным образом, когда строки располагаются заданным образом для каждой отсортированной колонки. Колонкой сортировки является колонка в электронной таблице, в которой сортируются строки. В операции сортировки по колонкам колонки в электронной таблице располагаются заданным образом, когда колонки располагаются заданным образом для каждой строки сортировки. Термин "линия сортировки" используется в данном документе для ссылки обычно на колонку сортировки или строку сортировки.

[0028] Каждая колонка сортировки имеет требования к сортировке. Требования к сортировке включают в себя релевантное свойство и отношение порядка. Релевантное свойство может быть множеством различных свойств ячеек в колонке сортировки. Например, релевантное свойство может быть значениями в ячейках, цветом ячеек, флагами в отношении ячеек, цветами шрифтов в ячейках, стилями шрифтов в ячейках, размером шрифтов в ячейках, статус скрытый/видимый ячеек и другими свойствами ячеек.

[0029] Отношение порядка является набором из одного или более правил, которые определяют, как свойства упорядочены. Примерные типы отношений порядка включают в себя алфавитный порядок, обратный алфавитный порядок, числовой порядок, обратный числовой порядок, хронологический порядок, обратный хронологический порядок, категорический порядок, географический порядок и другие типы заданий. В качестве одного конкретного примера категорического порядка, отношение порядка могут определять порядок по Булевым значениям, указывая, что все истинные значения находятся перед любыми ложными значениями. В другом примере отношение порядка могут определять порядок по цветам ячейки, указывая, что синие ячейки находятся перед зелеными ячейками, желтые ячейки находятся перед синими ячейками, красные ячейки находятся перед желтыми ячейками и так далее. В некоторых вариантах осуществления пользователь приложения 108 электронной таблицы имеет возможность выбрать колонки сортировки и требования сортировки для этих колонок сортировки.

[0030] Когда имеются множественные колонки сортировки, эти колонки сортировки ранжируются. Строки в электронной таблице сортируются первыми в соответствии с требованиями сортировки самой высокой по рангу колонки сортировки, затем в соответствии с требованиями сортировки второй, самой высокой по рангу колонки сортировки и так далее. Следовательно, строки располагаются заданным образом для заданной колонки сортировки, когда для любых двух строк, имеющих одинаковые релевантные свойства в ячейках каждой более высокой по рангу колонки сортировки, эти две строки удовлетворяют требованиям сортировки заданной колонки сортировки. Эти две строки удовлетворяют требованиям сортировки заданной колонки сортировки, когда отношение порядка для заданной колонки сортировки сохраняется истинным для релевантного свойства этих двух ячеек.

[0031] Как описано подробно в другом месте этого документа, приложение 108 электронной таблицы делит строки в электронной таблице на множество блоков. Блоком является набор строк. Следовательно, о блоке можно думать как о меньшей электронной таблице. В некоторых вариантах осуществления количество строк в каждом из блоков основано на количестве строк в электронной таблице и количестве блоков 110 обработки. По большей части количество блоков равно количеству блоков обработки 110 в системе 104 обработки.

[0032] После того как строки разделяются на блоки, процесс сортировки входит в фазу сортировки блока. Во время фазы сортировки блока приложение 108 электронной таблицы использует множественные потоки сортировки блоков для сортировки строк в блоках. Количество потоков сортировки блока равно количеству блоков. Каждый из потоков сортировки блоков работает для сортировки строк в каждом из блоков.

[0033] После того как потоки сортировки блока отсортируют строки в блоках, процесс сортировки входит в фазу объединения (слияния). Во время фазы объединения приложение 108 электронной таблицы использует множественные потоки объединения для генерирования блока конечного результата. Блок конечного результата содержит каждую из строк в электронной таблице. Строки в блоке конечного результата упорядочены заданным образом. Каждым из потоков объединения является поток, который объединяет два исходных блока для генерирования блока результата. Каждый из исходных блоков потока объединения может быть или одним из сортированных блоков, сгенерированных потоком сортировки блока, или блоком результата, сгенерированным другим потоком объединения. Например, исходные блоки потока объединения могут быть сортированными блоками, сгенерированными потоками сортировки блоков. В другом примере исходные блоки потока объединения могут быть сортированным блоком, сгенерированным одним из потоков сортировки блока, и блоком результата, сгенерированным другим потоком объединения. В еще одном примере исходные блоки потока объединения могут быть блоками результата, сгенерированными другими потоками объединения.

[0034] После того, как блок конечного результата генерируется, приложение 108 электронной таблицы выводит данные результата для представления пользователю приложения 108 электронной таблицы. Данные результата зависят от порядка строк в блоке конечного результата.

[0035] В различных вариантах осуществления приложение 108 электронной таблицы выводит различные типы данных результата. Например, в некоторых вариантах осуществления приложение 108 электронной таблицы отображает сортированную версию электронной таблицы, в которой строки в электронной таблице упорядочены в соответствии с порядком строк в блоке конечного результата. Кроме того, в некоторых вариантах осуществления приложение 108 электронной таблицы генерирует и отображает сообщение, показывающее по меньшей мере некоторые строки в блоке конечного результата. Кроме того, в некоторых вариантах осуществления данные результата необязательно включают в себя все строки в электронной таблице. В случаях, когда данные результата используются другим процессом или поднаборы электронной таблицы являются предметом для дальнейшей сортировки, данные результата необязательно представляются пользователю.

[0036] Фиг. 2 является блок-схемой, иллюстрирующей примерный альтернативный вариант осуществления вычислительной системы 100. Как иллюстрировано в примере на фиг. 2, вычислительная система 100 содержит систему 102 хранения данных и систему 104 обработки, как в примерном варианте осуществления, иллюстрированном на фиг. 1. Однако в отличие от примерного варианта осуществления, иллюстрированного на фиг. 1, примерный альтернативный вариант осуществления вычислительной системы 100, иллюстрированный на фиг. 2, имеет интерфейс 200 сети вместо системы 106 отображения.

[0037] Система 200 интерфейса сети позволяет вычислительной системе 100 посылать и принимать данные от устройства 202 клиента через сеть 204. Сеть 204 является системой связи, содержащей вычислительные устройства и линии связи, которые облегчают связь между вычислительной системой 100 и устройством 202 клиента. В различных вариантах осуществления сеть 204 включает в себя различные типы вычислительных устройств. Например, сеть 204 может включать в себя маршрутизаторы, коммутаторы, мобильные точки доступа, мосты, концентраторы, устройства обнаружения вторжения, устройства хранения, автономные сервера, сверхкомпактные сервера (блейды), датчики, настольные компьютеры, межсетевые экраны, ноутбуки, переносные компьютеры, мобильные телефоны и другие типы вычислительных устройств. В различных вариантах осуществления сеть 204 включает в себя различные типы линий связи. Например, сеть 204 может включать в себя проводные и/или беспроводные линии связи. Кроме того, в различных вариантах осуществления сеть 204 реализуется в различных масштабах. Например, сеть 204 может быть реализована в качестве одной или более локальных сетей (сетей LAN), городских вычислительных сетей, подсетей, глобальных сетей (таких как Интернет) или может быть реализована в другом масштабе.

[0038] Устройство 202 клиента является вычислительным устройством. Например, устройство 202 клиента может быть персональным компьютером, используемым пользователем. Пользователь использует устройство 202 клиента для посылки запросов в вычислительную систему 100 и приема информации от вычислительной системы 100 через сеть 204. Таким образом, пользователь может использовать устройство 202 клиента для рассмотрения и манипулирования табличными данными посредством использования приложения 108 электронной таблицы. Например, вычислительная система 100 может посылать данные результата на устройство 202 клиента через сеть 204. В этом примере устройство 202 клиента сконфигурировано для обработки данных результата для отображения сортированной версии электронной таблицы пользователю устройства 202 клиента. Например, устройство 202 клиента может выдавать веб-страницу, содержащую данные результата, или взаимодействовать с приложением клиента для отображения данных результата.

[0039] Фиг. 3 является последовательностью операций, иллюстрирующей примерную операцию 300 для сортировки электронной таблицы. Как иллюстрировано в примере на фиг. 3, операция 300 начинается, когда приложение 108 электронной таблицы принимает команду (302) сортировки. Команда сортировки дает команду приложению 108 электронной таблицы начинать процесс сортировки в конкретной электронной таблице. Кроме того, команда сортировки может задавать релевантное свойство, отсортированную колонку в электронной таблице и отношение упорядочения. В некоторых вариантах осуществления пользователь приложения 108 электронной таблицы может выбирать электронную таблицу, релевантное свойство, отсортированную колонку и/или отношение упорядочения.

[0040] В различных вариантах осуществления приложение 108 электронной таблицы принимает команду сортировки различными способами. Например, в некоторых вариантах осуществления приложение 108 электронной таблицы принимает команду сортировки, когда пользователь приложения электронной таблицы выбирает конкретное пользовательское средство управления приложением 108 электронной таблицы. Кроме того, в некоторых вариантах осуществления приложение 108 электронной таблицы принимает команду сортировки, когда пользователь вводит конкретную команду клавиатуры. Кроме того, в некоторых вариантах осуществления приложение 108 электронной таблицы принимает команду сортировки от другого процесса, потока или приложения, работающего в вычислительной системе 100, устройстве 202 клиента или другом вычислительном устройстве.

[0041] Кроме того, в некоторых вариантах осуществления приложение 108 электронной таблицы начинает операцию 300 без приема явной команды сортировки от пользователя или другого процесса, потока или приложения. Например, в некоторых вариантах осуществления приложение 108 электронной таблицы может начинать операцию 300 автоматически на периодической основе или на основании расписания. Кроме того, в некоторых вариантах осуществления приложение 108 электронной таблицы может начинать операцию 300 автоматически, когда пользователь обновляет одну или более строк в электронной таблице. Кроме того, в некоторых вариантах осуществления, приложение 108 электронной таблицы начинает операцию 300 автоматически в ответ на обнаружение или прием события, указывающего, что изменение имело место в источнике данных, из которого выводится электронная таблица.

[0042] В ответ на прием команды сортировки или иного приема индикации для начала процесса сортировки в электронной таблице приложение 108 электронной таблицы определяет, превышает ли общее количество строк в электронной таблице нижний предел (304). В различных вариантах осуществления нижний предел имеет различные значения. Например, в некоторых вариантах осуществления нижним пределом является 255. В других вариантах осуществления нижним пределом является больше, чем 255, или меньше, чем 255. В некоторых вариантах осуществления приложение 108 электронной таблицы представляет пользовательский интерфейс, который позволяет административному пользователю устанавливать нижний предел. Административный пользователь может быть пользователем, который принимает данные результата, или другим пользователем.

[0043] Если количество строк в электронной таблице не превышает нижний предел ("НЕТ" из 304), приложение 108 электронной таблицы использует единственный поток для генерирования блока (306) конечного результата. Единственный поток генерирует блок конечного результата посредством сортировки строк в электронной таблице таким образом, чтобы строки в электронной таблице упорядочивались заданным образом. Использование единственного потока для сортировки строк может быть более эффективным, чем использование множественных потоков для сортировки строк, когда количество строк в электронной таблице относительно мало. Причина состоит в том, что могут быть вычислительные штрафы (например, задержки), ассоциированные со стартом или пробуждением потоков. Такие вычислительные штрафы могут только отрицательно воздействовать, когда имеется достаточное количество строк.

[0044] Если количество строк в электронной таблице превышает нижний предел ("ДА" из 304), приложение 108 электронной таблицы определяет подходящее количество блоков (308). В различных вариантах осуществления приложение 108 электронной таблицы определяет подходящее количество блоков различными способами. Например, в некоторых вариантах осуществления минимальный размер задания является минимальным количеством строк в блоке, нуждающимся в старте оправданного дополнительного потока сортировки блока. В некоторых случаях нижний предел равен минимальному размеру задания, умноженному на два. В этом примере, если количество строк в электронной таблице, разделенное на минимальный размер задания, меньше, чем или равно количеству блоков 110 обработки в системе 104 обработки, подходящее количество блоков равно количеству строк, разделенных на минимальный, округленный в меньшую сторону размер задания. Например, если имеется 300 строк, минимальный размер задания равен 128, и имеется восемь блоков обработки в системе 104 обработки, соответствующее количество блоков равно двум. Если количество строк в электронной таблице, разделенной на минимальный размер задания, больше, чем или равно количеству блоков 110 обработки в системе 104 обработки, соответствующее количество блоков равно количеству блоков 110 обработки. Например, если есть 30 000 строк, минимальный размер задания равен 128, и имеется восемь блоков обработки в системе 104 обработки, соответствующее количество блоков равно восьми. В некоторых вариантах осуществления приложение 108 электронной таблицы представляет пользовательский интерфейс, который позволяет административному пользователю устанавливать минимальный размер задания.

[0045] Затем приложение 108 электронной таблицы делит строки в электронной таблице на набор блоков (310). Количество блоков в наборе блоков равно соответствующему количеству блоков. Каждый блок в наборе блоков содержит приблизительно одинаковое количество строк.

[0046] В различных вариантах осуществления блоки реализованы различными способами. Например, в некоторых вариантах осуществления блоки реализуются в качестве структуры данных, которые содержат идентификаторы строк (например, строка "513", строка "234", строка "876" и т.д.). В таких вариантах осуществления вставка строк в блок содержит вставку идентификаторов строк в блок, и сортировка строк в блоке содержит перекомпоновку идентификаторов строк в блоке. В других вариантах осуществления блоки являются структурами данных, содержащими копии строк.

[0047] После деления строк в блоки приложение 108 электронной таблицы начинает фазу сортировки блока процесса сортировки. Во время фазы сортировки блока процесса сортировки приложение 108 электронной таблицы использует множественные потоки сортировки блока для сортировки строк в блоках (312). Количество потоков сортировки блока в наборе потоков сортировки блока равно количеству блоков в наборе блоков. Например, если количество блоков равно восьми, количество потоков сортировки блока равно восьми. В некоторых случаях каждый поток сортировки блока выполняется параллельно в отличном одном из блоков 110 обработки в системе 104 обработки. Приложение 108 электронной таблицы назначает один из блоков каждому из потоков сортировки блока. Потоки сортировки блока сортируют строки в блоках, назначенных потокам сортировки блока. В различных вариантах осуществления потоки сортировки блока используют различные алгоритмы для сортировки строк в блоках. Например, в различных вариантах осуществления потоки сортировки блока используют алгоритм быстрой сортировки (например, qsort), алгоритм пузырьковой сортировки, алгоритм сортировки объединением (слиянием) или другой алгоритм сортировки для сортировки строк в блоках.

[0048] В некоторое время после того, как приложение 108 электронной таблицы пробуждает набор потоков сортировки блока, приложение 108 электронной таблицы определяет, что потоки сортировки блока закончили сортировать каждый из блоков (314). В различных вариантах осуществления приложение 108 электронной таблицы определяет, что потоки сортировки блока закончили сортировать каждый из блоков различными способами. Например, в некоторых вариантах осуществления потоки сортировки блока выдают индикаторы завершения приложению 108 электронной таблицы, когда потоки сортировки блока закончили сортировать блоки. В других вариантах осуществления потоки сортировки блока сохраняют сортированные блоки в буфере. В таких вариантах осуществления приложение 108 электронной таблицы определяет, что потоки сортировки блока закончили сортировать блоки, когда буфер содержит сортированную версию каждого из блоков.

[0049] После того как потоки сортировки блока закончили сортировать блоки, фаза сортировки блока процесса сортировки заканчивается, и начинается фаза объединения из процесса сортировки. Во время фазы объединения процесса сортировки приложение 108 электронной таблицы генерирует дерево (316) потока. Деревом потока является двоичное дерево, в котором каждый уровень, кроме, возможно, последнего уровня, полностью заполнено. Двоичным деревом является структура данных дерева, в которой каждый узел имеет самое большее два дочерних узла.

[0050] Количество потоков объединения в дереве потоков равно количеству блоков минус один. Листовым потоком является поток объединения, не имеющий дочерних потоков в дереве потоков. Внутренним потоком является поток объединения, имеющий один или более дочерних потоков в дереве потоков. Неполным внутренним потоком является внутренний поток, имеющий только один дочерний поток в дереве потоков. Полным внутренним потоком является внутренний поток, имеющий два дочерних потока в дереве потоков. Корневым потоком является поток объединения, не имеющий родительских потоков в дереве потоков.

[0051] Как описано в другом месте этого документа, листовой поток функционирует для объединения (слияния) сортированных блоков, назначенных на листовой поток, таким образом генерируя блок результата. Блок результата содержит каждую из строк в назначенных блоках. Строки в блоке результата упорядочены заданным образом. Неполный внутренний поток функционирует для объединения блоков результата, сгенерированных его единственным дочерним процессом, с сортированным блоком, назначенным на неполный внутренний поток. Полный внутренний поток функционирует для объединения блоков результата, сгенерированных его дочерними потоками в большие блоки результата. В конечном счете, корневой поток генерирует блок конечного результата.

[0052] В различных вариантах осуществления приложение 108 электронной таблицы выполняет различные действия для генерирования дерева потоков. Например, в некоторых вариантах осуществления приложение 108 электронной таблицы генерирует дерево потоков посредством первой идентификации доступных потоков объединения и/или иллюстрации потоков объединения. В этом примере приложение 108 электронной таблицы затем генерирует структуру данных указателей, которая содержит элемент для каждого потока объединения. Элемент для потока объединения задает исходные указатели и указатель элемента назначения. Исходные указатели задают местоположения памяти, которые хранят блоки, которые поток объединения должен объединить. Указатель элемента назначения задает местоположение памяти, где поток объединения должен сохранить блок результата, сгенерированный потоком объединения. Структура данных указателя может быть множеством различных типов структур данных, включающих в себя множества, связанные списки, векторы, таблицы и так далее.

[0053] После генерирования дерева потоков или в качестве части генерирования дерева потока приложение 108 электронной таблицы назначает два из блоков на каждый листовой поток в дереве (318) потоков. В различных вариантах осуществления приложение 108 электронной таблицы назначает блоки на листовые потоки различными способами. Например, в вариантах осуществления, которые используют структуру данных указателя, описанную выше, приложение 108 электронной таблицы назначает блок на листовой поток, выдавая в элементе для листового потока исходный указатель на местоположение памяти блока. В другом примере приложение 108 электронной таблицы назначает блок на листовой поток, выдавая идентификатор блока в листовой поток в качестве параметра.

[0054] Кроме того, приложение 108 электронной таблицы определяет, имеется ли нечетное число блоков (320). Если имеется нечетное число блоков, дерево потоков содержит неполный внутренний поток. Следовательно, если имеется нечетное число блоков ("ДА" 320), приложение 108 электронной таблицы назначает один из блоков на неполный внутренний поток (322).

[0055] После назначения блоков неполному внутреннему потоку или определения того, что не имеется нечетного числа блоков ("НЕТ" 320), приложение 108 электронной таблицы использует потоки объединения для генерирования блока (324) конечного результата. Для использования потоков объединения для генерирования блока конечного результата приложение 108 электронной таблицы пробуждает потоки объединения. В различных вариантах осуществления приложение 108 электронной таблицы пробуждает потоки объединения различными способами. Например, в некоторых вариантах осуществления приложение 108 электронной таблицы пробуждает потоки объединения, предоставляя событие пробуждения потоку объединения. В других вариантах осуществления приложение 108 электронной таблицы запускает один или более методов интерфейса операционной системы для пробуждения потока объединения.

[0056] Затем приложение 108 электронной таблицы принимает индикацию завершения от корневого потока в дереве (326) потоков. Индикация завершения указывает, что корневой поток закончил генерирование блока конечного результата. Блок конечного результата содержит все строки в электронной таблице. Строки в блоке конечного результата упорядочены заданным образом.

[0057] После того как приложение 108 электронной таблицы принимает индикацию завершения от корневого потока или после того, как строки сортированы на этапе 306, приложение 108 электронной таблицы возвращает блок конечного результата (328). Затем приложение 108 электронной таблицы может выдавать данные результата, которые зависят от блока конечного результата.

[0058] Фиг. 4 является диаграммой, показывающей примерное дерево 400 потоков. Как иллюстрировано в примере на фиг. 4, дерево 400 потоков содержит поток 402, поток 404, поток 407, поток 408, поток 410 и поток 412. Поток 402, поток 404 и поток 406 являются внутренними потоками. Поток 402 и поток 404 являются полными внутренними потоками. Поток 406 является неполным внутренним потоком. Поток 408, поток 410 и поток 412 являются листовыми потоками.

[0059] Кроме того, пример фиг. 4 показывает, что блоки 414 и 416 назначены на поток 408, что блоки 418 и 420 назначены на поток 410, что блоки 422 и 424 назначены на поток 412, и что блок 426 назначен на поток 406. Другими словами, блоки 418 и 420 являются исходными блоками потока 408. Блоки 418 и 420 являются исходными блоками потока 410. Блоки 422 и 424 являются исходными блоками потока 412. Блок 426 является исходным блоком потока 406.

[0060] Поток 408 объединяет блоки 414 и 416 для генерирования блока результата. Поток 410 объединяет блоки 418 и 420 для генерирования блока результата. Поток 412 объединяет блоки 422 и 424 для генерирования блока результата. Поток 404 объединяет блоки результата, сгенерированные потоками 408 и 410, для генерирования блока результата. Другими словами, блоки результата, сгенерированные потоками 408 и 410, являются исходными блоками потока 404. Поток 406 объединяет блоки 426 и блок результата, сгенерированный потоком 412 для генерирования блока результата. Другими словами, блок результата, сгенерированный потоком 412, является исходным блоком потока 406. Поток 402 объединяет блоки результата, сгенерированные потоками 404 и 406, для генерирования блока конечного результата. Другими словами, блоки результата, сгенерированные потоками 404 и 406, являются исходными блоками потока 402.

[0061] Фиг. 5 является последовательностью операций, иллюстрирующей примерную операцию 500, выполняемую листовым потоком во время фазы объединения процесса сортировки. Хотя операция 500 объясняется относительно единственного листового потока, каждый листовой поток в дереве потоков может выполнять операцию 500. Как иллюстрировано в примере на фиг. 5, операция 500 начинается, когда листовой поток пробуждается приложением 108 (502) электронной таблицы. Пробуждение потока является процессом подготовки потока к запуску. В различных вариантах осуществления приложение 108 электронной таблицы пробуждает листовой поток различными способами. Например, в некоторых вариантах осуществления приложение 108 электронной таблицы поддерживает ссылки на спящие потоки, которые в состоянии выполнять операцию 500. В некоторых вариантах осуществления спящие потоки могут включать в себя потоки сортировки блока, используемые в фазе сортировки блока процесса сортировки. Другими словами, один из потоков сортировки блоков может работать в качестве листового потока. Для пробуждения листового потока приложение 108 электронной таблицы выдает событие пробуждения в поток, который может выполнять операцию 500, и предоставляет листовому потоку ссылку на первый блок, назначенный на этот листовой поток, и второй блок, назначенный на этот листовой поток.

[0062] После того как листовой поток пробуждается, этот листовой поток определяет, является ли наибольшая строка в первом блоке меньше, чем наименьшая строка во втором блоке (504). Так как строки в первом блоке упорядочены заданным образом, наибольшая строка в первом блоке является последней строкой в первом блоке. Так как строки во втором блоке упорядочены заданным образом, наименьшая строка во втором блоке является первой строкой во втором блоке. Если листовой поток определяет, что наибольшая строка в первом блоке является меньше, чем наименьшая строка во втором блоке, не происходит никакого наложения между первым блоком и вторым блоком, и нет никакой необходимости сравнивать индивидуальные строки в первом блоке и втором блоке. Вместо этого, если листовой поток определяет, что наибольшая строка в первом блоке является меньше, чем наименьшая строка во втором блоке ("ДА" 504), листовой поток вставляет первый блок в меньший конец блока результата и вставляет второй блок в больший конец блока результата (506). Таким образом, блок результата содержит все строки в первом блоке и втором блоке, и строки в блоке результата упорядочены заданным образом.

[0063] Если листовой поток определяет, что наибольшая строка в первом блоке не является меньше, чем наименьшая строка во втором блоке, листовой поток определяет, является ли наибольшая строка во втором блоке меньше, чем наименьшая строка в первом блоке (508). Так как строки во втором блоке упорядочены заданным образом, наибольшая строка во втором блоке является последней строкой во втором блоке. Так как строки в первом блоке упорядочены заданным образом, наименьшая строка в первом блоке является первой строкой в первом блоке. Если листовой поток определяет, что наибольшая строка во втором блоке является меньше, чем наименьшая строка в первом блоке ("ДА" 508), листовой поток вставляет второй блок в меньший конец блока результата и вставляет первый блок в больший конец блока результата (510). Таким образом, блок результата содержит все строки в первом блоке и втором блоке, и строки в блоке результата упорядочены заданным образом.

[0064] Если наибольшая строка в первом блоке является больше, чем наименьшая строка второго блока, и наибольшая строка во втором блоке является больше, чем наименьшая строка в первом блоке, имеется некоторое наложение между первым блоком и вторым блоком. Если листовой поток определяет, что наибольшая строка во втором блоке является не меньше, чем наименьшая строка в первом блоке ("НЕТ" 508), листовой поток определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (512). Строка является оставшейся строкой, когда строка уже не находится в блоке результата.

[0065] Если имеются одна или более оставшихся строк в первом блоке ("ДА" 512), листовой поток определяет, имеются ли какие-нибудь оставшиеся строки во втором блоке (514). Если нет никаких оставшихся строк во втором блоке, листовой поток уже вставил все строки во втором блоке в блок результата. Следовательно, если нет никаких оставшихся строк во втором блоке ("НЕТ" 514), листовой поток вставляет любые оставшиеся строки в первом блоке в блок результата после наибольшей строки в блоке результата (518). После вставки оставшихся строк в первом блоке в блок результата блок результата содержит все строки в первом блоке и втором блоке, и строки в блоке результата упорядочены заданным образом.

[0066] Если имеется одна или более оставшихся строк во втором блоке ("ДА" 514), листовой поток идентифицирует минимальную строку (516). Минимальная строка является наименьшей из оставшихся строк в первом блоке и втором блоке.

[0067] Как рассмотрено выше, в некоторых вариантах осуществления могут быть выбраны множественные колонки сортировки. Например, пользователь может указывать, что электронная таблица должна быть сначала сортирована по колонке "город" и затем по колонке "дата". Если имеется множество колонок сортировки, и если релевантные свойства в ячейках в наивысшей по рангу колонке сортировки из двух строк являются одинаковыми, минимальный поток объединения идентифицирует минимальную строку посредством сравнения релевантных свойств в ячейках в следующей наивысшей по рангу колонке сортировки этих двух строк. Если релевантные свойства ячеек в следующей наивысшей по рангу колонке сортировки являются одинаковыми, минимальный поток объединения идентифицирует минимальную строку посредством сравнения релевантных свойств в ячейках третьей, наивысшей по рангу колонки сортировки этих двух строк. Этот процесс сравнения продолжается до тех пор, пока не останется ни одной из колонок сортировки или пока минимальный поток объединения не идентифицирует одну из строк, которые меньше, чем другая строка. Если релевантные свойства ячеек во всех колонках сортировки этих двух строк равны, минимальный поток объединения может идентифицировать любую из строк в качестве минимальной строки.

[0068] Листовой поток вставляет минимальную строку в блок результата после наибольшей строки в блоке результата (520). После вставки минимальной строки в блок результата листовой поток снова определяет, имеются ли любые оставшиеся строки в первом блоке (512) и так далее.

[0069] Если нет оставшихся строк в первом блоке, листовой поток уже вставил все строки в первом блоке в блок результата. Следовательно, если нет оставшихся строк в первом блоке ("НЕТ" 512), листовой поток вставляет любые оставшиеся строки во втором блоке в блок результата после наибольшей строки в блоке результата (514). После вставки оставшихся строк во втором блоке в блок результата блок результата содержит все строки в первом блоке и втором блоке, и строки в блоке результата упорядочены заданным образом.

[0070] После выполнения любого из этапов 506, 510, 518 или 522 листовой поток определяет, является ли листовой поток корневым потоком (524). Если листовой поток является корневым потоком ("ДА" 524), листовой поток выдает индикацию завершения приложению 108 (526) электронной таблицы. Индикация завершения указывает, что листовой поток завершил объединение первого блока и второго блока. Если листовой поток не является корневым потоком ("НЕТ" 524), листовой поток выдает индикацию завершения родительскому потоку листового потока (528). После или доказательства индикации завершения приложению электронной таблицы или родительскому потоку листового потока листовой поток (530) переходит в режим сна.

[0071] Фиг. 6 является последовательностью операций, иллюстрирующей примерную операцию 600, выполненную неполным внутренним потоком. Операция 600 начинается, когда неполный внутренний поток разбужен приложением 108 (602) электронной таблицы. Приложение 108 электронной таблицы предоставляет неполному внутреннему потоку ссылку на первый блок и второй блок. Первым блоком является блок результата, сгенерированный дочерним потоком неполного внутреннего потока. Вторым блоком является блок, который был произведен одним из потоков сортировки блока во время фазы сортировки блока процесса сортировки. Неполный внутренний поток и дочерний поток работают одновременно на различных потоках блоков 110 обработки. Следовательно, дочерний поток генерирует первый блок, в то время как неполный внутренний поток выполняет операцию 600. В результате, могут быть случаи, когда нет оставшихся строк в первом блоке, но дочерний поток может позже вставить больше строк в первый блок.

[0072] После пробуждения неполный внутренний поток определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (604). Если имеются одна или более оставшихся строк в первом блоке ("ДА" 604), неполный внутренний поток определяет, имеются ли какие-нибудь оставшиеся строки во втором блоке (606).

[0073] Если нет оставшихся строк во втором блоке ("НЕТ" 606), неполный внутренний поток вставляет любые оставшиеся строки в первом блоке в блок результата после наибольшей строки в блоке результата (608). Так как дочерний поток генерирует первый блок, в то время как неполный внутренний поток выполняет операцию 600, дочерний поток может добавить строки в первый блок, в то время как неполный внутренний поток выполняет операцию 600. Неполному внутреннему потоку не гарантируют, что дочерний поток не будет добавлять дополнительных строк в первый блок до тех пор, пока дочерний поток не предоставит индикацию завершения неполному внутреннему потоку. Следовательно, после того, как неполный внутренний поток вставляет оставшиеся строки в первом блоке в блок результата, неполный внутренний поток снова определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (604), и так далее.

[0074] Если имеется одна или более оставшихся строк во втором блоке ("ДА" 606), неполный внутренний поток идентифицирует минимальную строку (610). Минимальной строкой является наименьшая оставшаяся строка или в первом блоке, или во втором блоке. Неполный внутренний поток затем вставляет минимальную строку в блок результата после наибольшей строки в блоке результата (612). После вставки минимальной строки в блок результата неполный внутренний поток снова определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (604) и так далее.

[0075] Если нет никаких оставшихся строк в первом блоке ("НЕТ" 612), неполный внутренний поток определяет, выполнен ли дочерний поток (614). Дочерний поток выполнен, когда дочерний поток предоставляет индикацию завершения неполному внутреннему потоку. Если дочерний поток еще не выполнен, дочерний поток может все еще продолжить вставлять строки в первый блок. Следовательно, если дочерний поток не выполнен ("НЕТ" 614), неполный внутренний поток ждет (616). В различных вариантах осуществления неполный внутренний поток ждет до тех пор, пока не произойдут различные события. Например, в некоторых вариантах осуществления неполный внутренний поток ждет до тех пор, пока не истечет таймер. В других вариантах осуществления неполный внутренний поток ждет до тех пор, пока не произойдет итоговое событие. Итоговое событие может быть вставкой строки в первый блок, индикацией завершения от дочернего потока или другим типом события. После того, как неполный внутренний поток завершает ожидание, неполный внутренний поток снова определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (604) и так далее.

[0076] Если дочерний поток выполнен ("ДА" 614), неполный внутренний поток вставляет любые оставшиеся строки во втором блоке в блок результата после наибольшей строки в блоке результата (618). Если нет оставшихся строк во втором блоке, когда выполнен дочерний поток, неполный внутренний поток не вставляет строки в блок результата на этапе 618.

[0077] После вставки оставшихся строк во втором блоке в блок результата неполный внутренний поток определяет, является ли неполный внутренний поток корневым потоком (620). Если неполным внутренним потоком является корневой поток ("ДА" 620), неполный внутренний поток предоставляет индикацию завершения приложению 108 (622) электронной таблицы. Если неполный внутренний поток не является корневым потоком ("НЕТ" 620), неполный внутренний поток выдает индикацию завершения в родительский поток неполного внутреннего потока (624). После или выдачи индикации завершения в приложение 108 электронной таблицы или родительскому потоку неполный внутренний поток переходит в режим сна (626).

[0078] Фиг. 7 является последовательностью операций, иллюстрирующей примерную операцию 700, выполняемую полным внутренним потоком. Хотя операция 700 объясняется относительно единственного полного внутреннего потока, каждый полный внутренний поток в дереве потоков может выполнять операцию 700. Как иллюстрировано в примере на фиг. 7, операция 700 начинается, когда полный внутренний поток пробуждается приложением 108 (702) электронной таблицы. Приложение 108 электронной таблицы выдает в полный внутренний поток ссылку на первый блок и второй блок. Первым блоком является блок результата, сгенерированный первым дочерним потоком полного внутреннего потока. Вторым блоком является блок результата, сгенерированный вторым дочерним потоком полного внутреннего потока. Полный внутренний поток, первый дочерний поток и второй дочерний поток работают одновременно на различных потоках блоков 110 обработки. Следовательно, первый дочерний поток генерирует первый блок, и второй дочерний поток генерирует второй блок, в то время как полный внутренний поток выполняет операцию 700. Кроме того, так как полный внутренней поток и первый дочерний поток работают одновременно, могут быть ситуации, когда первый блок не содержит оставшихся строк, но первый дочерний поток может позже вставить больше строк в первый блок. Аналогично, так как полный внутренний поток и второй дочерний поток работают одновременно, могут быть ситуации, когда второй блок не содержит оставшихся строк, но второй дочерний поток может позже вставить больше строк во второй блок.

[0079] После пробуждения полный внутренний поток определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (704). Если полный внутренний поток определяет, что есть одна или более оставшихся строк в первом блоке ("ДА" 704), полный внутренний поток определяет, имеются ли какие-нибудь оставшиеся строки во втором блоке (706).

[0080] Если нет оставшихся строк во втором блоке данных ("НЕТ" 706), полный внутренний поток определяет, выполнен ли второй дочерний поток (708). Второй дочерний поток выполнен, если второй дочерний поток выдает индикацию завершения в полный внутренний поток. Если второй дочерний поток не выполнен, второй дочерний поток может вставить дополнительные строки во второй блок. Некоторые из этих строк могут быть меньше, чем наименьшая строка в первом блоке. Следовательно, если полный внутренний поток определяет, что второй дочерний поток не выполнен ("НЕТ" 708), полный внутренний поток ждет (710). В различных вариантах осуществления полный внутренний поток ждет до тех пор, пока не произойдут различные события. Например, в некоторых вариантах осуществления полный внутренний поток ждет до тех пор, пока не истечет таймер. В других вариантах осуществления полный внутренний поток ждет до тех пор, пока полный внутренний поток не примет итоговое событие. Итоговое событие может указывать, что второй поток вставил строку во второй блок или что второй поток выполнен. После того, как полный внутренний поток закончил ждать, полный внутренний поток заново определяет, включает ли второй блок в себя какие-нибудь строки (706) и так далее.

[0081] Если второй дочерний поток выполнен, то второй дочерний поток не будет вставлять больше строк во второй блок и во втором блоке нет оставшихся строк. Следовательно, все оставшиеся строки в первом блоке больше, чем любая строка в блоке результата. Следовательно, если полный внутренний поток определяет, что выполнен второй дочерний поток ("ДА" 708), полный внутренний поток вставляет любые оставшиеся строки в первый блок в блок результата после наибольшей строки в блоке результата (712). После вставки оставшихся строк в первом блоке в блок результата полный внутренний поток заново определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (704) и так далее.

[0082] Если полный внутренний поток определяет, что имеется оставшаяся строка во втором блоке ("ДА" 706), полный внутренний поток идентифицирует минимальную строку (714). Минимальной строкой является наименьшая оставшаяся строка или в первом блоке, или во втором блоке. Полный внутренний поток затем вставляет минимальную строку в блок результата после наибольшей строки в блоке результата (716). После вставки минимальной строки в блок результата полный внутренний поток заново определяет, имеются ли какие-нибудь оставшиеся строки в первом блоке (704) и так далее.

[0083] Если нет оставшихся строк в первом блоке ("НЕТ" 704), полный внутренний поток определяет, выполнен ли первый дочерний поток (718). Первый дочерний поток выполнен, когда первый дочерний поток выдал индикацию завершения полному внутреннему потоку. Если первый дочерний поток еще не выполнен, первый дочерний поток может продолжить вставлять строки в первый блок. Следовательно, если первый дочерний поток не выполнен ("НЕТ" 718), полный внутренний поток ждет (720). В различных вариантах осуществления полный внутренний поток ждет до тех пор, пока не произойдут различные события. Например, в некоторых вариантах осуществления, полный внутренний поток ждет до тех пор, пока не истечет таймер. В других вариантах осуществления полный внутренний поток ждет до тех пор, пока не произойдет итоговое событие. Итоговое событие может быть вставкой строки в первый блок, индикацией завершения от первого дочернего потока или другим типом события.

[0084] Если первый дочерний поток выполнен ("ДА" 718), полный внутренний поток определяет, имеются ли какие-нибудь оставшиеся строки во втором блоке (722). Если имеются одна или более оставшихся строк во втором блоке ("ДА" 722), полный внутренний поток вставляет любые оставшиеся строки во втором блоке в блок результата после наибольшей строки в блоке результата (724). Полный внутренний поток может вставлять оставшиеся строки во втором блоке в блок результата, так как первый дочерний поток не будет добавлять больше строк в первый блок, и все строки в первом блоке были добавлены в блок результата. Следовательно, любые оставшиеся строки во втором блоке являются большими, чем наибольшая строка в блоке результата.

[0085] После вставки любых оставшихся строк во втором блоке в блок результата или после определения, что нет оставшихся строк во втором блоке ("НЕТ" 722), полный внутренний поток определяет, выполнен ли второй дочерний поток (726). Если полный внутренний поток определяет, что второй поток не выполнен ("НЕТ" 712), полный внутренний поток ждет (728). После того, как полный внутренний поток завершил ожидание, полный внутренний поток снова определяет, имеются ли какие-нибудь оставшиеся строки во втором блоке (722) и так далее.

[0086] Если полный внутренний поток определяет, что второй дочерний поток выполнен ("ДА" 726), полный внутренний поток определяет, является ли полный внутренний поток корневым потоком (730). Если полный внутренний поток является корневым потоком ("ДА" 730), полный внутренний поток выдает индикацию завершения приложению 108 (732) электронной таблицы. Если полный внутренний поток не является корневым потоком ("НЕТ" 730), полный внутренний поток выдает индикацию завершения в родительский поток полного внутреннего потока (734). После или выдачи индикации завершения в приложение электронной 108 таблицы или родительский поток полного внутреннего потока полный внутренний поток переходит в режим сна (736).

[0087] Фиг. 8 является последовательностью операций, иллюстрирующей примерную операцию 800, выполненную потоком управления памятью во время фазы объединения процесса обработки. Некоторые варианты осуществления используют способ управления памятью, который включает два буфера. В таких вариантах осуществления каждый из сортированных блоков, сгенерированных во время фазы сортировки блока, хранится в первом буфере. Например, блоки 414, 416, 418, 420, 422, 424 и 426, иллюстрированные в примере фиг. 4, хранятся в первом буфере. Когда листовые потоки генерируют блоки результата, эти листовые потоки считывают из первого буфера и сохраняют свои блоки результата во втором буфере. Например, потоки 408, 410 и 412, иллюстрированные в примере на фиг. 4, сохраняют свои блоки результата во втором буфере. Внутренние потоки в первом уровне выше листовых потоков считывают строки из второго буфера и сохраняют свои блоки результата обратно в первый буфер. Например, потоки 404 и 406, иллюстрированные в примере на фиг. 4, считывают из второго буфера и сохраняют свои блоки результата в первом буфере. Внутренние потоки во втором уровне выше листовых потоков считывают строки из первого буфера, и блоки результата сохраняют обратно во второй буфер. Например, поток 402, иллюстрированный в примере на фиг. 4, считывает из первого буфера и сохраняет его блоки результата во втором буфере. Это продолжается для прогрессивно более высоких уровней в иерархии потоков. При некоторых обстоятельствах этот способ управления памятью может быть более эффективным, чем распределение блоков памяти для индивидуальных блоков результата.

[0088] В некоторых вариантах осуществления, использующих этот способ управления памятью, приложение 108 электронной таблицы ждет, что блок конечного результата будет в первом буфере. Однако в некоторых случаях блок конечного результата находится во втором буфере, а не в первом буфере. Кроме того, в некоторых вариантах осуществления, использующих этот способ управления памятью, все потоки объединения в заданном уровне ожидают считывания из одного и того же буфера и сохраняют блоки результата в одном и том же буфере. Однако неполный внутренний поток считывает блок, произведенный листовыми потоками (то есть блок во втором буфере), и блок, сгенерированный во время фазы сортировки блока (то есть блок в первом буфере). Поток управления памятью выполняет операцию 800 для исправления этих проблем.

[0089] Как иллюстрировано в примере на фиг. 8, операция 800 начинается, когда поток управления памятью разбужен приложением (802) электронной таблицы. После пробуждения поток управления памятью определяет, имеется ли нечетное число сортированных блоков, сгенерированных во время фазы (804) сортировки блока процесса сортировки. Если имеется нечетное число блоков в первом буфере, иерархия потоков включает в себя неполный внутренний поток. Следовательно, если имеется нечетное число блоков в первом буфере ("ДА" 804), поток управления памятью копирует во второй буфер блок, назначенный на неполный внутренний поток (806). Таким образом, блок готов к использованию неполным внутренним потоком.

[0090] После копирования блока во второй буфер или после определения того, что нет нечетного числа блоков, сгенерированных в фазе сортировки блока процесса сортировки ("НЕТ" 804), поток управления памятью определяет, является ли блок конечного результата завершенным (808). Если блок конечного результата не является завершенным ("НЕТ" 808), поток управления памятью ждет (810). В различных вариантах осуществления поток управления памятью ждет до тех пор, пока не произойдут различные события. Например, в некоторых вариантах осуществления, поток управления памятью ждет до тех пор, пока не истечет таймер. В других вариантах осуществления поток управления памятью ждет до тех пор, пока корневой поток не обеспечит индикацию завершения приложению 108 электронной таблицы. После того, как поток управления памятью завершает ожидание, поток управления памятью снова определяет, является ли блок конечного результата завершенным (808).

[0091] Если блок конечного результата является завершенным ("ДА" 808), поток управления памятью определяет, находится ли блок конечного результата во втором буфере (812). Если блок конечного результата находится во втором буфере ("ДА" 812), поток управления памятью копирует блок конечного результата в первый буфер (814). После копирования блока конечного результата в первый буфер или после определения того, что блок конечного результата уже находится в первом буфере ("НЕТ" 812), поток управления памятью (816) переходит в режим сна.

[0092] Фиг. 9 является блок-схемой, иллюстрирующей примерное вычислительное устройство 900. В некоторых вариантах осуществления вычислительная система 100 реализуется, используя одно или более вычислительных устройств, таких как вычислительное устройство 900. Должно быть оценено, что в других вариантах осуществления вычислительная система 100 реализуется, используя вычислительные устройства, имеющие компоненты аппаратного обеспечения, отличные от иллюстрированных в примере на фиг. 9.

[0093] В различных вариантах осуществления вычислительные устройства реализуются по-разному. Например, в примере на фиг. 9 вычислительное устройство 900 содержит память 902, систему 904 обработки, вторичное устройство 906 хранения, карту 908 интерфейса сети, видеоинтерфейс 910, устройство 912 отображения, интерфейс 914 внешних компонентов, внешнее устройство 916 хранения, устройство 918 ввода, принтер 920 и носитель 922 связи. В других вариантах осуществления вычислительные устройства реализуются, используя больше или меньше компонентов аппаратного обеспечения. Например, в другом примерном варианте осуществления, вычислительное устройство не включает в себя видеоинтерфейс, устройство отображения, внешнее устройство хранения или устройство ввода.

[0094] Память 902 включает в себя один или более считываемых компьютером носителей данных, способных хранить данные и/или команды. Как используется в этом документе, считываемым компьютером носителем данных является устройство или продукт изготовления, который хранит данные и/или команды программного обеспечения, считываемые вычислительным устройством. В различных вариантах осуществления память 902 реализуется по-разному. Например, в различных вариантах осуществления память 902 реализуется, используя различные типы считываемых компьютером носителей данных. Примерные типы считываемых компьютером носителей данных включают в себя, но не ограничиваются ими, динамическую память произвольного доступа (DRAM), синхронную динамическую память произвольного доступа с двойной скоростью передачи данных (DDR SDRAM), DRAM с уменьшенным временем ожидания, DDR2 SDRAM, DDR3 SDRAM, RAM Rambus, полупроводниковую память, флэш-память, постоянное запоминающее устройство (ROM), электрически-стираемое программируемое ROM и другие типы устройств и/или продуктов изготовления, которые сохраняют данные.

[0095] Система 904 обработки включает в себя одну или более физических интегральных схем, которые выборочно выполняют команды программного обеспечения. В различных вариантах осуществления система 904 обработки реализуется различными способами. Например, в одном примерном варианте осуществления система 904 обработки реализуется в качестве одного или более ядер обработки. Например, в этом примерном варианте осуществления система 904 обработки может быть реализована в качестве одного или более микропроцессоров Intel Core 2. В другом примерном варианте осуществления система 904 обработки реализуется в качестве одного или более отдельных микропроцессоров. В еще одном примерном варианте осуществления система 904 обработки реализуется в качестве ASIC, которая предоставляет специальные функциональные возможности. В еще одном примерном варианте осуществления система 904 обработки предоставляет специальные функциональные возможности при использовании ASIC и посредством выполнения команд программного обеспечения.

[0096] В различных вариантах осуществления система 904 обработки выполняет команды программного обеспечения в различных наборах команд. Например, в различных вариантах осуществления система 904 обработки выполняет команды программного обеспечения в наборах команд, таких как набор команд x86, набор команд POWER, набор команд RISC, набор команд SPARC, набор команд IA-64, набор команд MIPS и/или другие наборы команд.

[0097] Вторичное устройство 906 хранения включает в себя один или более считываемых компьютером носителей данных. Вторичное устройство 906 хранения хранит данные и команды программного обеспечения, непосредственно не доступные системе 904 обработки. Другими словами, система 904 обработки выполняет операцию ввода/вывода для извлечения данных и/или команд программного обеспечения из вторичного устройства 906 хранения. В различных вариантах осуществления вторичное устройство 906 хранения реализовано различными типами считываемых компьютером носителей данных. Например, вторичное устройство 906 хранения может быть реализовано одним или более магнитными дисками, устройствами на магнитных лентах, дисками CD-ROM, дисками ROM DVD, дисками Blu-Ray, устройствами памяти полупроводника, накопителями Бернулли и/или другими типами считываемых компьютером носителей данных.

[0098] Карта 908 интерфейса сети позволяет вычислительному устройству 900 посылать данные и принимать данные от компьютерной сети связи. В различных вариантах осуществления карта 908 интерфейса сети реализуется по-разному. Например, в различных вариантах осуществления карта 908 интерфейса сети реализуется в качестве интерфейса Ethernet, кольцевой сети с маркерным доступом, волоконно-оптического интерфейса сети, беспроводного интерфейса сети (например, WiFi, WiMax и т.д.) или другого типа интерфейса сети.

[0099] Видеоинтерфейс 910 позволяет вычислительному устройству 900 выводить видеоинформацию в устройство 912 отображения. В различных вариантах осуществления видеоинтерфейс 910 реализуется по-разному. Например, в одном примерном варианте осуществления видеоинтерфейс 910 интегрируется в материнскую плату вычислительного устройства 900. В другом примерном варианте осуществления видеоинтерфейс 910 является видеокартой расширения. Примерные типы видеокарт расширения включают в себя графические карты Radeon, произведенные ATI Technologies, Inc Markham, Ontario, графические карты Geforce, произведенные Корпорацией Nvidia, Santa Clara, California, и другие типы графических карт.

[0100] В различных вариантах осуществления устройство 912 отображения реализуется в качестве различных типов устройств отображения. Примерные типы устройств отображения включают в себя, но не ограничиваются ими, дисплеи на электронно-лучевой трубке, панели отображения LCD, плазменные панели отображения, чувствительные к прикосновению панели отображения, экраны LED, проекторы и другие типы устройств отображения. В различных вариантах осуществления видеоинтерфейс 910 связывается с устройством 912 отображения различными способами. Например, в различных вариантах осуществления видеоинтерфейс 910 связывается с устройством 912 отображения с помощью разъема универсальной последовательной шины (USB), разъема VGA, разъема цифрового визуального интерфейса (DVI), разъема S-видео, разъема мультимедийного интерфейса высокого разрешения (HDMI), разъема DisplayPort или других типов разъемов.

[0101] Интерфейс 914 внешних компонентов позволяет вычислительному устройству 900 связываться с внешними устройствами. В различных вариантах осуществления интерфейс 914 внешних компонентов реализуется по-разному. Например, в одном примерном варианте осуществления интерфейс 914 внешних компонентов является интерфейсом USB. В других примерных вариантах осуществления вычислительное устройство 900 является интерфейсом FireWire, интерфейсом последовательного порта, интерфейсом параллельного порта, интерфейсом PS/2 и/или другим типом интерфейса, который позволяет вычислительному устройству 900 связываться с внешними компонентами.

[0102] В различных вариантах осуществления интерфейс 914 внешних компонентов позволяет вычислительному устройству 900 связываться с различными внешними компонентами. Например, в примере на фиг. 9 интерфейс 914 внешних компонентов позволяет вычислительному устройству 900 связываться с внешним устройством хранения 916, устройством 918 ввода и принтером 920. В других вариантах осуществления интерфейс 914 внешних компонентов позволяет вычислительному устройству 900 связываться с большим или меньшим количеством внешних компонентов. Другие примерные типы внешних компонентов включают в себя, но не ограничиваются ими, динамики, разъемы для заряда телефонов, модемы, установочные модули медиаплеера, другие вычислительные устройства, сканеры, цифровые камеры, устройства считывания отпечатков пальцев и другие устройства, которые могут быть связаны с вычислительным устройством 900.

[0103] Внешнее устройство 916 хранения является внешним компонентом, содержащим один или более считываемых компьютером носителей данных. Различные реализации вычислительного устройства 900 связываются с различными типами внешних устройств хранения. Примерные типы внешних устройств хранения включают в себя, но не ограничиваются ими, устройства на магнитной ленте, модули флэш-памяти, магнитные накопители, оптические накопители, блоки флэш-памяти, на дисках zip, оптические музыкальные проигрыватели и другие типы устройств, содержащих один или более считываемых компьютером носителей данных. Устройство ввода 918 является внешним компонентом, который обеспечивает пользовательский ввод в вычислительное устройство 900. Различные реализации вычислительного устройства 900 связываются с различными типами устройств ввода. Примерные типы устройств ввода включают в себя, но не ограничиваются ими, клавиатуры, мыши, трекболы, устройства ввода пером, вспомогательные клавиатуры, микрофоны, джойстики, реагирующие на прикосновение дисплеи, и другие типы устройств, которые предоставляют пользовательский ввод в вычислительное устройство 900. Принтер 920 является внешним устройством, которое печатает данные на бумаге. Различные реализации вычислительного устройства 900 связываются с различными типами принтеров. Примерные типы принтеров включают в себя, но не ограничиваются ими, лазерные принтеры, струйные принтеры, принтеры для печати фотографий, копировальные машины, факсы, принтеры квитанций, матричные принтеры или другие типы устройств, которые печатают данные на бумаге.

[0104] Носитель 922 связи предоставляет связь между компонентами аппаратного обеспечения вычислительного устройства 900. В различных вариантах осуществления носитель 922 связи предоставляет связь между различными компонентами вычислительного устройства 900. Например, в примере на фиг. 9 носитель 922 связи облегчает связь между памятью 902, системой 904 обработки, вторичным устройством 906 хранения, картой 908 интерфейса сети, видео 910 интерфейсом и интерфейсом 914 внешних компонентов. В различных реализациях вычислительного устройства 900 носитель 922 связи реализуется по-разному. Например, в различных реализациях вычислительного устройства 900 носитель 922 связи может быть реализован в качестве шины PCI, шины PCI Express, шины ускоренного графического порта (AGP), соединительного провода Infiniband, соединительного провода интерфейса для подключения внешних устройств, интерфейса ATA (ATA) соединительного провода параллельного ATA, оптоволоконного соединительного провода, шины USB, интерфейса малых вычислительных систем (SCSI) или другого типа носителя связи.

[0105] Память 902 хранит различные типы данных и/или команд программного обеспечения. Например, в примере на фиг. 9 память 902 хранит базовую систему ввода/вывода (BIOS) 924, операционную 926 систему, программное обеспечение 928 приложения и данные 930 программы. BIOS 924 включает в себя набор команд программного обеспечения, который при выполнении системой 904 обработки вынуждает вычислительное устройство 900 загружаться для работы. Операционная система 926 включает в себя набор команд программного обеспечения, который при выполнении системой 904 обработки вынуждает вычислительное устройство 900 предоставлять операционную систему, которая координирует действия и совместное использование ресурсов вычислительного устройства 900. Типы примерных операционных систем включают в себя, но не ограничиваются ими, Windows Microsoft (R), Linux, Unix, Apple OS X, Apple OS X iPhone, Palm webOS, Palm OS, Google Chrome OS, Google Android OS и так далее. Прикладное программное обеспечение 928 включает в себя набор команд программного обеспечения, который при выполнении системой 904 обработки вынуждает вычислительное устройство 900 предоставлять приложения пользователю вычислительного устройства 900. Данные программы 930 являются данными, генерируемыми и/или используемыми прикладным программным обеспечением 928.

[0106] Различные варианты осуществления, описанные выше, предоставляются только посредством иллюстрации и не должны рассматриваться как ограничивающие. Специалисты в данной области техники легко распознают различные модификации и изменения, которые могут быть применены без следующих примерных вариантов осуществления и приложений, иллюстрированных и описанных в настоящем описании. Например, операции, показанные на чертежах, являются просто примерами. В различных вариантах осуществления подобные операции могут включать в себя больше или меньше этапов, чем показаны на чертежах. Кроме того, в других вариантах осуществления аналогичные операции могут включать в себя этапы операций, показанные на чертежах в другом порядке.

Изобретение относится к способу, системе и компьютерному носителю данных для сортировки данных в электронной таблице. Технический результат заключается в ускорении сортировки данных в электронной таблице. Способ содержит разделение элементов данных в электронной таблице на множество блоков, использование множества потоков для сортировки элементов данных в этих блоках, после сортировки элементов данных в блоках использование посредством вычислительной системы множества потоков объединения для генерирования блока конечного результата, содержащего каждый из элементов данных в электронной таблице, каждый из потоков объединения является потоком, объединяющим два исходных блока для генерирования блока результата, каждый из исходных блоков является или одним из сортированных блоков или одним из блоков результата, сгенерированных другим потоком объединения, и отображение сортированной версии электронной таблицы, причем элементы данных в сортированной версии электронной таблицы упорядочены в соответствии с порядком элементов данных в блоке конечного результата. 3 н. и 12 з.п. ф-лы, 9 ил.

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. Считываемый компьютером носитель данных, имеющий считываемые компьютером команды, хранящиеся на нем, причем считываемые компьютером команды при выполнении одним или более блоками обработки в системе обработки вычислительной системы для сортировки данных в электронной таблице вынуждают вычислительную систему:
определять, превышает ли количество строк в сводной таблице нижний предел;
использовать единственный поток для генерирования блока конечного результата, когда количество строк в сводной таблице не превышает нижний предел, причем блок конечного результата содержит каждую из строк в сводной таблице, строки упорядочены заданным образом в блоке конечного результата;
выполнять следующие действия, когда количество строк в сводной таблице превышает нижний предел:
определять подходящее количество блоков на основании количества строк в сводной таблице и количества блоков обработки в системе обработки, разделять строки в сводной таблице на множество блоков, при этом количество блоков в упомянутом множестве блоков равно этому подходящему количеству блоков, причем количество строк в каждом из блоков приблизительно равно; использовать множество потоков сортировки блока для сортировки блоков таким образом, чтобы строки в блоках были упорядочены заданным образом;
генерировать дерево потоков, причем дерево потоков содержит множество потоков объединения;
назначать два из блоков на каждый листовой поток в дереве потоков; и пробуждать каждый поток объединения в наборе потоков объединения,
при этом каждый листовой поток в дереве потоков генерирует блок результата, который содержит каждую из строк в блоках, назначенных на листовой поток, причем строки в блоке результата, сгенерированном листовым потоком, упорядочены заданным образом, при этом каждый полный внутренний поток в дереве потоков генерирует блок результата, который содержит каждую из строк в блоках результата, сгенерированных дочерними потоками полного внутреннего потока, строки в блоке результата, сгенерированном полным внутренним потоком, упорядочены заданным образом;
причем блоком конечного результата является блок результата, сгенерированный корневым потоком в дереве потоков, при этом корневой поток является потоком, не имеющим родительских потоков в дереве потоков; и
отображать сортированную версию электронной таблицы, причем элементы данных в сортированной версии электронной таблицы упорядочены в соответствии с порядком элементов данных в блоке конечного результата.