Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.51 KB | None | 0 0
  1. n - число сортируемых структур
  2. B - число структур в одном блоке
  3. U - число различных значений целочисленного ключа (от 0 до U - 1)
  4.  
  5. counters = [0] * U
  6. for i in range(0, n, B):
  7.     data_block = get_block(i) # массив пар (ключ, структура) длины B
  8.     update_counters(data_block) # инкрементим счётчики числа ключей для B записей
  9.  
  10. current_write_indices = get_prefix_sums(counters) # опеределяем адреса во внешней памяти, куда попадут структуры с каждым типом ключа
  11. buffers = [[] for i in range(U)]
  12. for i in range(0, n, B):
  13.     data_block = get_block(i) # массив пар (ключ, структура) длины B
  14.     for (key, value) in data_block:
  15.        if len(buffers[key]) < B:
  16.            buffers[key].append((key, value)) # если место есть, сохраняем структуру в оперативной памяти
  17.        else: # len(buffers[key]) == B
  18.            write_block(buffers[key], current_write_indices[key]) # дампим ответ на диск
  19.            buffers[key] = [] # освобождаем память
  20.            current_write_indices[key] += B # сдвигаем курсор во внешней памяти
  21.  
  22. # в конце опустошаем буферы
  23. for key, buffer in enumerate(buffers):
  24.     if len(buffer) > 0:
  25.         write_block(buffer, current_write_indices[key])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement