Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- n - число сортируемых структур
- B - число структур в одном блоке
- U - число различных значений целочисленного ключа (от 0 до U - 1)
- counters = [0] * U
- for i in range(0, n, B):
- data_block = get_block(i) # массив пар (ключ, структура) длины B
- update_counters(data_block) # инкрементим счётчики числа ключей для B записей
- current_write_indices = get_prefix_sums(counters) # опеределяем адреса во внешней памяти, куда попадут структуры с каждым типом ключа
- buffers = [[] for i in range(U)]
- for i in range(0, n, B):
- data_block = get_block(i) # массив пар (ключ, структура) длины B
- for (key, value) in data_block:
- if len(buffers[key]) < B:
- buffers[key].append((key, value)) # если место есть, сохраняем структуру в оперативной памяти
- else: # len(buffers[key]) == B
- write_block(buffers[key], current_write_indices[key]) # дампим ответ на диск
- buffers[key] = [] # освобождаем память
- current_write_indices[key] += B # сдвигаем курсор во внешней памяти
- # в конце опустошаем буферы
- for key, buffer in enumerate(buffers):
- if len(buffer) > 0:
- write_block(buffer, current_write_indices[key])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement