algorithm - inteligencia - id3 ejemplo ppt

¿Cómo funciona el algoritmo de clasificación de fusión externa?

Question

Estoy tratando de entender cómo funciona el algoritmo de clasificación de combinación externa (vi algunas respuestas para la misma pregunta, pero no encontré lo que necesito). Estoy leyendo el libro "Analysis Of Algorithms" de Jeffrey McConnell y estoy tratando de implementar el algoritmo descrito allí.

Por ejemplo, tengo datos de entrada: 3,5,1,2,4,6,9,8,7 , y solo puedo cargar 4 números en la memoria.

Mi primer paso es leer el archivo de entrada en fragmentos de 4 números, ordenarlos en la memoria y escribir uno en el archivo A y al lado del archivo B.

Tengo:

A:[1,2,3,5][7]  
B:[4,6,8,9]

Ahora mi pregunta, ¿cómo puedo combinar fragmentos de estos archivos con los más grandes si no encajan en la memoria? Jeffrey McConnell escribió que debo leer los medios fragmentos y combinarlos con los siguientes archivos C y D.

Pero tengo la secuencia equivocada:

C:[1,2,4,6,3,8,5,9]
D:[7]

¿Alguien puede proporcionar un ejemplo con instrucciones paso a paso, por favor?

PD: entiendo cómo combinar número por número al leer un archivo, pero ¿cómo lo hago con búferes en memoria para reducir las operaciones de E / S?

Answer 1

En primer lugar, al clasificar los números en partes de 4 números, debe obtener 3 fragmentos.

A:[1,2,3,5]  
B:[4,6,8,9]
C:[7]

Luego leerá la mitad de cada archivo (ignore C ya que no encaja) y los fusionará. Entonces, cargarás en la memoria {[1, 2], [4, 6]}. Harás una combinación casual y escribirás el resultado en una nueva parte D:

Compare 1 and 4 -> D:[1]
Compare 2 and 4 -> D:[1, 2]

Ahora la parte de A que estaba en la memoria RAM terminó de fusionarse, por lo que ahora tendrá que llevar la segunda mitad de la memoria. Ahora su memoria tendrá {[3, 5], [4, 6]}.

Compare 3 and 4 -> D:[1, 2, 3]
Compare 5 and 4 -> D:[1, 2, 3, 4]
Compare 5 and 6 -> D:[1, 2, 3, 4, 5]

Todo el fragmento A se fusionó, por lo que ahora solo agregue el resto de B a D

D:[1,2,3,4,5,6,8,9]

Ahora tendría que hacer el mismo proceso con los trozos C y D. Recuerde que C podría tener más de un número en otro ejemplo. Al fusionar C y D, obtendrás un nuevo fragmento E que será el archivo ordenado final.

Además, tenga en cuenta que en un ejemplo más grande es posible que necesite más fases de fusión. Por ejemplo, si tuviera 20 números para ordenar, crearía 5 trozos de 4 números, y luego combinaría y fusionaría dos de ellos cada vez, dando como resultado 2 trozos de 8 números (más uno extra de 4 números), y luego fusione los nuevos fragmentos en uno de los 16 números y así sucesivamente.

Answer 2

La clasificación externa se usa generalmente cuando necesita ordenar archivos que son demasiado grandes para que quepan en la memoria.

El truco es dividir el archivo de entrada más grande en trozos ordenados k más pequeños y luego combinarlos en un archivo ordenado más grande. Para la fusión utiliza un montón min. k dependerá de tu umbral de memoria.

Lea una cierta cantidad de registros (dependiendo de su umbral de memoria) de cada fragmento y póngalos en una cola por trozo.

Extraiga el elemento que se encuentra más a la izquierda (este será el elemento más pequeño, ya que los elementos de la cola se ordenarán) de cada cola y lo empujan hacia el montón

Pop el elemento min del montón. Tenga en cuenta de qué cola vino

Vuelva a llenar la cola con el siguiente elemento de su parte correspondiente que no está en la cola

Extraiga el elemento más a la izquierda de la cola y empújelo al montón

Escribe el elemento min en el archivo de salida

Continúa los 4 pasos anteriores hasta que el montón esté vacío

Código de ejemplo de Python (no se fusiona en su lugar)

import os
import heapq
import itertools
import linecache
from collections import deque
import sys


def external_sort(input_directory, input_file_name, output_file_name):
    with open(os.path.expanduser(input_directory + ''/'' + output_file_name), ''w+'') as f:
        heap = []
        pages = {}
        next_line_numbers = {}
        has_more_items = {}
        chunk_file_paths, max_chunk_size = create_sorted_chunks(input_directory, input_file_name)
        max_page_size = max_chunk_size // 10
        for chunk_file_path in chunk_file_paths:
            pages[chunk_file_path] = populate_page(chunk_file_path, max_page_size)
            next_line_numbers[chunk_file_path] = len(pages[chunk_file_path])
            has_more_items[chunk_file_path] = True
        for chunk_file_path in chunk_file_paths:
            heapq.heappush(heap, pages[chunk_file_path].popleft())
        while heap:
            item, chunk_file_path = heapq.heappop(heap)
            f.write(str(item)+''/n'')
            if has_more_items[chunk_file_path]:
                has_more_items[chunk_file_path] = append_next(pages, chunk_file_path, next_line_numbers[chunk_file_path])
                next_line_numbers[chunk_file_path] += 1
            if pages[chunk_file_path]:
                heapq.heappush(heap, pages[chunk_file_path].popleft())
    for chunk_file_path in chunk_file_paths:
        os.remove(chunk_file_path)


def populate_page(chunk_file_path, max_page_size):
    chunk = deque()
    with open(chunk_file_path, ''r'') as f:
        for line in itertools.islice(f, 0, max_page_size):
            chunk.append((int(line), chunk_file_path))
    return chunk


def append_next(chunks, chunk_file_path, line_number):
    chunk = chunks[chunk_file_path]
    item = linecache.getline(chunk_file_path, line_number)
    if item and len(item) > 0:
        chunk.append((int(item), chunk_file_path))
        has_more = True
    else:
        has_more = False
    return has_more


def create_sorted_chunks(input_file_directory, input_file_name):
    input_file_path = os.path.expanduser(input_file_directory + ''/'' + input_file_name)
    suffix = 1
    begin, end, tot = 0, 0, 0
    chunk_file_paths = []
    with open(input_file_path, ''r'') as f:
        for line in f.readlines():
            tot += 1
    end = tot//10
    while suffix <= 10:
        buffer = []
        chunk_file_name = ''temp'' + str(suffix) + ''.txt''
        chunk_file_path = os.path.expanduser(input_file_directory + ''/'' + chunk_file_name)
        if not os.path.isfile(chunk_file_path):
            with open(os.path.expanduser(input_file_path), ''r'') as f:
                for line in itertools.islice(f, begin, end):
                    buffer.append(int(line))
                create_chunk(chunk_file_path, buffer)
        suffix += 1
        begin = end
        end += tot//10
        chunk_file_paths.append(chunk_file_path)
    return chunk_file_paths, tot//10


def create_chunk(chunk_file_path, buffer):
    buffer.sort()
    with open(chunk_file_path, ''w+'') as f:
        for i in buffer:
            f.write(str(i) + ''/n'')


if __name__ == ''__main__'':
    external_sort(sys.argv[1], sys.argv[2], sys.argv[3])

Answer 3

Recorrerás los archivos al mismo tiempo.

Simplemente comience desde el principio de cada archivo y continúe seleccionando el elemento del archivo que no sea mayor (es decir, más pequeño o igual) que el otro, envíe ese elemento al nuevo archivo y aumente el iterador.

Desde su última declaración, no está claro si usted ya sabe hacerlo o no, pero esto es todo lo que necesita hacer, porque:

• Solo necesitaría tener un número en la memoria para cada uno de los archivos y, por supuesto, cualquier índice y otras variables que presumiblemente se ignoran para el propósito de este ejercicio.

• Solo necesita leer cada archivo una vez, ya que puede mantenerlos abiertos en la posición correcta durante este proceso, por lo que no necesita volver a leer todo el archivo para llegar a la posición correcta.

Entonces, para

A:[1,2,3,5]
B:[4,6,8,9]

Comenzarías con el primer elemento de cada archivo: 1 y 4 .

El 1 es más pequeño, por lo que lo envía al nuevo archivo y pasa al 2 .

2 es más pequeño que 4 , por lo que usted genera eso y pasa a 3 .

3 es más pequeño que 4 , por lo que usted genera eso y pasa a 5 .

4 es más pequeño que 5 , por lo que usted genera eso y pasa a 6 .

5 es más pequeño que 6 , por lo que genera eso y luego llega al final de A.

Ahora solo saca el resto de B: 6, 8, 9 .

Esto te da [1,2,3,4,5,6,8,9] .

Answer 4

Supongo que después de tanto tiempo debes tener una respuesta. Pero todavía estoy proporcionando algunos enlaces de ejemplo para ayudar a alguien que haga esta pregunta.

NOTA: Antes de mirar en este enlace, debería tener una idea acerca de la estructura de datos de Heap. Eche un vistazo al Ejemplo de clasificación bidireccional y el Ejemplo de clasificación externa de múltiples vías y obtendrá una idea completa de la implementación de un algoritmo de clasificación externo