Мои данные:
- Это файл размером 71 МБ с 1,5 миллионами строк.
- Имеет 6 полей
- Все шесть полей объединяются, чтобы сформировать уникальный ключ - вот что мне нужно отсортировать.
Сортировать заявление:
sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6 -o output.csv input.csv
Эта проблема:
- Если я сортирую без ключей, это займет 30 секунд.
- Если я разбираюсь с ключами, это занимает 660 секунд.
- Мне нужно сортировать по ключам, чтобы сохранить это универсальным и полезным для других файлов, которые также имеют неключевые поля. Время 30 секунд хорошо, но 660 - убийца.
Более подробная информация, используя время Unix:
- сортировать input.csv -o output.csv = 28 секунд
- sort -t ',' -k1 input.csv -o output.csv = 28 секунд
- sort -t ',' -k1,1 input.csv -o output.csv = 64 секунды
- sort -t ',' -k1,1 -k2,2 input.csv -o output.csv = 194 секунды
- sort -t ',' -k1,1 -k2,2 -k3,3 input.csv -o output.csv = 328 секунд
- sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 input.csv -o output.csv = 483 секунды
- sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 input.csv -o output.csv = 561 секунда
- sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6 input.csv -o output.csv = 660 секунд
Я мог бы теоретически переместить временный каталог в SSD и / или разбить файл на 4 части, отсортировать их по отдельности (параллельно), затем объединить результаты и т.д. Но я надеюсь на что-то более простое, поскольку похоже, что сортировка - это просто выбор плохого алгоритма.
Какие-либо предложения?
Улучшения тестирования с использованием размера буфера:
- С двумя ключами я получил улучшение на 5% при 8, 20, 24 МБ и лучшую производительность при улучшении на 8% с 16 МБ, но на 6% хуже с 128 МБ
- С 6 клавишами я получил улучшение на 5% с 8, 20, 24 МБ и лучшую производительность на 9% с 16 МБ.
Улучшения тестирования с использованием порядка словаря (только 1 прогон каждого):
- sort -d --buffer-size = 8M -t ',' -k1,1 -k2,2 input.csv -o output.csv = 235 секунд (на 21% хуже)
- sort -d --buffer-size = 8M -t ',' -k1,1 -k2,2 input.csv -o ouput.csv = 232 секунды (на 21% хуже)
- Вывод: есть смысл, что это замедлит процесс, а не будет полезным
Тестирование с другой файловой системой на SSD - я не могу сделать это на этом сервере сейчас.
Тестирование с кодом для объединения смежных ключей:
def consolidate_keys(key_fields, key_types):
""" Inputs:
- key_fields - a list of numbers in quotes: ['1','2','3']
- key_types - a list of types of the key_fields: ['integer','string','integer']
Outputs:
- key_fields - a consolidated list: ['1,2','3']
- key_types - a list of types of the consolidated list: ['string','integer']
"""
assert(len(key_fields) == len(key_types))
def get_min(val):
vals = val.split(',')
assert(len(vals) <= 2)
return vals[0]
def get_max(val):
vals = val.split(',')
assert(len(vals) <= 2)
return vals[len(vals)-1]
i = 0
while True:
try:
if ( (int(get_max(key_fields[i])) + 1) == int(key_fields[i+1])
and key_types[i] == key_types[i+1]):
key_fields[i] = '%s,%s' % (get_min(key_fields[i]), key_fields[i+1])
key_types[i] = key_types[i]
key_fields.pop(i+1)
key_types.pop(i+1)
continue
i = i+1
except IndexError:
break # last entry
return key_fields, key_types
Хотя этот код является лишь обходным путем, который будет применяться только к случаям, в которых у меня есть непрерывный набор ключей - он ускоряет код на 95% в моем худшем случае.