| dbo:abstract
|
- Externes Sortieren beschreibt Sortieralgorithmen, welche auf sehr große Datenmengen ausgelegt sind. Algorithmen, die auf großen Datenmengen arbeiten, die nicht in den Hauptspeicher passen, werden allgemein als External-Memory-Algorithmen bezeichnet.In der Analyse klassischer Sortieralgorithmen (z. B. Quicksort) wird meist keine Speicherhierarchie bzw. der Zugriff auf Daten auf unterschiedlich schnellen Datenträgern berücksichtigt.Allerdings ist der Aufbau und die Hierarchie des Speichers sowie der Umgang der Algorithmen mit diesem für die Performance beim Sortieren von großen Datenmengen entscheidend. (de)
- Ekstera Ordigo estas ĝenerala nomo por kiuj povas prilabori grandajn kvantojn da datenoj. Ekstera ordigo necesas kiam la ĉefmemoro de komputilo ne povas enteni la tutajn ordigotajn datenojn kaj sekve oni devas uzi alian pli malrapidan klason de memoro (ofte fiksita disko).
* Ekzemplo de ekstera ordigo estas la algoritmo pri kunfanda ordigo.
* Alia ekzemplo estas la algoritmo pri ekvilibra kunfanda ordigo, kiu estas plibonigo de la antaŭa. (eo)
- External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive. Thus, external sorting algorithms are external memory algorithms and thus applicable in the external memory model of computation. External sorting algorithms generally fall into two types, distribution sorting, which resembles quicksort, and external merge sort, which resembles merge sort. The latter typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file. (en)
- Ordenamiento externo es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso. Un ejemplo de ordenamiento externo es el algoritmo de ordenamiento por mezcla. Supongamos que 900 MB de información deben ser ordenados utilizando únicamente 100 MB de RAM. 1.
* Léanse 100MB de información en la memoria principal y ordenense utilizando un algoritmo tradicional (típicamente quicksort). 2.
* Escríbase la información ordenada en el disco. 3.
* Repítanse los pasos 1 y 2 hasta que toda la información esté ordenada en pedazos de 100 MB. Ahora se deben mezclar todos los pedazos ordenados. 4.
* Léanse los primeros 10MB de cada pedazo ordenado a la memoria principal (total de 90 MB) y destínense los 10 MB restantes para el buffer de salida. 5.
* Ordénense los nueve pedazos mezclándolos y grábese el resultado en el buffer de salida. Si el buffer de salida está lleno, escríbase al archivo destino final. Si cualquiera de los 9 buffers leídos queda vacío, se llena con los siguientes 10 MB de su pedazo original de 100 MB o se marca este como completado si ya no hay registros remanentes. Otro ejemplo es el algoritmo de ordenamiento por mezcla equilibrada, que es una optimización del anterior. (es)
- Un algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur. Recourir à la mémoire externe permet d'arriver à trier des volumes de données plus importants mais induit de nouvelles difficultés, le temps d'accès aux données étant beaucoup plus long. Aller chercher chaque valeur sur le disque lorsque l'on en a besoin serait trop lent ; en pratique, les approches qui fonctionnent travaillent successivement sur différentes parties des données chargées temporairement dans la mémoire principale. Les algorithmes de tri externe sont donc typiquement des variantes du tri fusion, qui s'adapte bien à ces contraintes : l'entrée est divisée en sous-ensembles pouvant être chargés un à un en mémoire, triés puis réécris dans des fichiers temporaires qui sont ensuite fusionnés. (fr)
- Sortowanie zewnętrzne, sortowanie plików (ang. external sort) – rodzaj algorytmów sortowania, które są stosowane, kiedy z pewnych względów nie jest możliwe jednoczesne umieszczenie wszystkich elementów zbioru sortowanego w pamięci operacyjnej. (pl)
- Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть когда применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и т. п. Наиболее часто внешняя сортировка используется в СУБД. Основным понятием при использовании внешней сортировки является понятие отрезка. Отрезком длины является последовательность записей , ,…,, в которой все записи упорядочены по некоторому ключу. Максимальное количество отрезков в файле (все элементы не упорядочены). Минимальное количество отрезков 1 (все элементы упорядочены). Например, в некотором файле А есть одномерный массив: 12 35 65 0 24 36 3 5 84 90 6 2 30 Поделим массив на отрезки: 12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30 Можно сказать, что массив в файле А состоит из 5 отрезков. Например, в некотором файле B есть одномерный массив: 1 2 3 4 5 6 7 8 9 10 Поделим массив на отрезки: | 1 2 3 4 5 6 7 8 9 10 | Можно сказать, что массив в файле B состоит из 1 отрезка. Например, в некотором файле А есть одномерный массив: 20 17 16 14 13 10 9 8 6 4 3 2 0 Поделим массив на отрезки: | 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 | Можно сказать, что массив в файле А состоит из 13 отрезков. Идея большинства методов заключается в расчленении данных на ряд последовательностей, помещающихся в оперативную память. Далее применяется один из методов внутренней сортировки, после чего последовательности сливаются. Чем больше объём оперативной памяти, тем длиннее будут последовательности и, следовательно, тем меньшим окажется их количество, что увеличит скорость сортировки. Если же объём оперативной памяти мал, то можно разделить исходные данные на несколько последовательностей, после чего непосредственно использовать процедуру слияния. Основные методы сортировок: 1.
* Естественная сортировка (метод естественного слияния) 2.
* Сортировка методом двухпутевого сбалансированного слияния 3. 1.
* Сортировка методом n-путевого слияния. 4.
* Многофазная сортировка (Фибоначчиевая) (ru)
- 外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的（通常是硬盘）上。外排序通常采用的是一种“排序-”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。 (zh)
- Зовнішнє сортування — це клас алгоритмів сортування, який може обробляти величезну кількість даних. Зовнішнє сортування потрібне, коли сортовані дані не входять у обчислювального пристрою (RAM), а замість цього вони повинні знаходитися в повільній , як правило, на . Зовнішнє сортування зазвичай використовує гібридну стратегію сортування-злиття. У фазі сортування, шматки даних, достатньо малих для розміщення в основній пам'яті, прочитуються, сортуються та виводяться до тимчасового файлу. У фазі злиття сортовані субфайли об'єднуються в один великий файл. (uk)
|
| rdfs:comment
|
- Externes Sortieren beschreibt Sortieralgorithmen, welche auf sehr große Datenmengen ausgelegt sind. Algorithmen, die auf großen Datenmengen arbeiten, die nicht in den Hauptspeicher passen, werden allgemein als External-Memory-Algorithmen bezeichnet.In der Analyse klassischer Sortieralgorithmen (z. B. Quicksort) wird meist keine Speicherhierarchie bzw. der Zugriff auf Daten auf unterschiedlich schnellen Datenträgern berücksichtigt.Allerdings ist der Aufbau und die Hierarchie des Speichers sowie der Umgang der Algorithmen mit diesem für die Performance beim Sortieren von großen Datenmengen entscheidend. (de)
- Ekstera Ordigo estas ĝenerala nomo por kiuj povas prilabori grandajn kvantojn da datenoj. Ekstera ordigo necesas kiam la ĉefmemoro de komputilo ne povas enteni la tutajn ordigotajn datenojn kaj sekve oni devas uzi alian pli malrapidan klason de memoro (ofte fiksita disko).
* Ekzemplo de ekstera ordigo estas la algoritmo pri kunfanda ordigo.
* Alia ekzemplo estas la algoritmo pri ekvilibra kunfanda ordigo, kiu estas plibonigo de la antaŭa. (eo)
- Sortowanie zewnętrzne, sortowanie plików (ang. external sort) – rodzaj algorytmów sortowania, które są stosowane, kiedy z pewnych względów nie jest możliwe jednoczesne umieszczenie wszystkich elementów zbioru sortowanego w pamięci operacyjnej. (pl)
- 外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的（通常是硬盘）上。外排序通常采用的是一种“排序-”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。 (zh)
- Зовнішнє сортування — це клас алгоритмів сортування, який може обробляти величезну кількість даних. Зовнішнє сортування потрібне, коли сортовані дані не входять у обчислювального пристрою (RAM), а замість цього вони повинні знаходитися в повільній , як правило, на . Зовнішнє сортування зазвичай використовує гібридну стратегію сортування-злиття. У фазі сортування, шматки даних, достатньо малих для розміщення в основній пам'яті, прочитуються, сортуються та виводяться до тимчасового файлу. У фазі злиття сортовані субфайли об'єднуються в один великий файл. (uk)
- External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive. Thus, external sorting algorithms are external memory algorithms and thus applicable in the external memory model of computation. (en)
- Ordenamiento externo es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso. Un ejemplo de ordenamiento externo es el algoritmo de ordenamiento por mezcla. Supongamos que 900 MB de información deben ser ordenados utilizando únicamente 100 MB de RAM. (es)
- Un algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur. (fr)
- Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть когда применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и т. п. Например, в некотором файле А есть одномерный массив: 12 35 65 0 24 36 3 5 84 90 6 2 30 Поделим массив на отрезки: 12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30 Можно сказать, что массив в файле А состоит из 5 отрезков. (ru)
|
