Многопоточная сортировка элементов данных в электронных таблицах

Многопоточная сортировка элементов данных в электронных таблицах

Иллюстрации

Показать все

Реферат

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

[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 электронной таблиц